[알고리즘] 정렬(sort)

주요 Sorting Algorithm을 정리해보자.

 

Selection Sort - O(N²)

 전체 배열에서 가장 큰 수를 찾고 뽑아서 처음이나 끝에 정렬하는 방법

 

Bubble Sort - O(N²)

 앞에서부터 인접한 두 원소를 보면서 앞의 원소가 뒤의 원소보다 클 경우 자리를 바꾸는 것을 반복하면 자연스럽게 제일 큰 것부터 오른쪽에 쌓음.

 

---

 

 Merge sort - O(NlogN)

• 분할 정복 알고리즘의 하나 이다.
  - 분할 정복(divide and conquer) 방법
  문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
  분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
• 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계 이다.
• 말이 어려울 수 있는데 그냥 나눴다가 정렬하면서 합치는 것
• 추가적인 공간(Overhead) 필요! O(N)
• Stable sort임!
  리스트를 정렬했을 때
  (1) list=[1, 3, 4, 5, 7(1), 7(2), 9] - Stable
  (2) list=[1, 3, 4, 5, 7(2), 7(1), 9] - Unstable

 

---

 

Quick Sort - O(NlogN)이지만, 최악의 경우 O(N²). 단, 평균적으로는 Merge Sort보다 빠름.

• In-Place Sort임 - 추가적인 공간이 필요X, 따라서 cache hit rate가 높아서 속도가 빠름
• Unstable sort - 중복된 값들의 순서가 변할 수 있음.

<과정>

1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
   - 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
   - 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
   - 리스트의 크기가 0이나 1이 될 때까지 반복한다.

---

 

Counting Sort - O(N+K) : 수의 범위인 K가 작을 때 사용하면 좋음.

•  숫자를 세서 배열에 횟수를 저장하고 정렬하는 방법.
• 수의 범위인 K가 작을 때 매우 효율적. 만약 수의 범위가 10억이면 10억 크기의 배열이 필요한데, 메모리 제한이 512MB인 경우 int기준 대략 1.2억 배열밖에 잡지 못함. 주의할 것
• 코드가 매우 간단하다!!

 

---

 

Radix Sort - O(D(N+K)), D는 자릿수의 최대 개수, K는 수의 범위(리스트의 개수)

• 자릿수를 이용한 정렬.
• 1의 자릿수를 기준으로 해당 인덱스와 자릿수를 맞춰서 먼저 배열에 넣음. 정렬함.
• 10의 자릿수를 기준으로 해당 인덱스와 자릿수를 맞춰서 배열에 넣음. 정렬함.
• 쭉 반복하면, 정렬됨..!
• 시간복잡도는 자릿수의 최대 개수가 D개라고 할 때 D번에 걸쳐서 카운팅 소트를 하는 것과 상황이 같다. 그러면 리스트의 개수를 K개라고 할 때 엄밀하게 말하면 시간복잡도는 O(D(N+K))이지만 보통 리스트의 개수는 N에 비해 무시가 가능할 정도로 작음

 

---

 

Comparison Sort vs Non-Comparison Sort

 

<Comparison Sort>

• Bubble Sort
• Merge Sort
• Quick Sort

<Non-Comparison Sort>

• Counting Sort
• Radix Sort

 

 

뭐 이외에도 진짜 많은 정렬 알고리즘들이 있다.

라이브러리도 확인해볼 것!

 

STL Sort는 Quick Sort 기반이다. 만약 리스트가 불균등하게 쪼개지는 상황이 반복되면서 재귀 깊이가 너무 깊어지면 O(NlogN)이 보장되는 다른 정렬알고리즘으로 대체되어 정렬한다. 그래서 STL Sort는 최악의 경우에도 O(NlogN)으로 처리되어 마음 편히 사용할 수 있다. 

위의 알고리즘을 Introspective Sort라고 하는데,

Introspective Sort는 알고리즘 수업때 직접 구현해본 경험이 있다.

Quick Sort로 진행하다가 재귀 깊이가 깊어질 경우 Heap Sort를 사용해서 처리되도록 하였다.

 

다만 주의할 점은 STL Sort는 Stable하지 않다는 것이다. 따라서 Stable하도록 정렬이 필요하다면, Stable_sort를 사용하면 된다.

또한 pair, tuple에는 이미 대소 관계가 우리에게 익숙한대로 먼저 제일 앞의 원소의 대소를 비교하고, 값이 같으면 그 다음 원소의 대소를 비교하는 방식으로 정해져있다. 예를 들어 pair에서 {2, 5} < {3, -2}고 tuple에서 {2, 1, 0} > {2, -2, 6}이다. 그래서 좌표를 정렬하거나 기타 여러 속성이 있는 원소를 정렬할 때 별도로 구조체를 둘 필요가 없고 pair나 tuple 등을 이용하면 된다.