§ 1 · 피벗 양쪽으로파티셔닝
퀵소트(Quicksort)는 평균 시나리오에 특히 효율적인 매우 빠른 정렬 알고리즘이다. 그 핵심은 파티셔닝(partitioning)이다.
배열을 파티셔닝한다는 것은, 무작위 값 하나(피벗, pivot)를 골라, 피벗보다 작은 값은 모두 왼쪽에·큰 값은 모두 오른쪽에 오게 하는 것이다.
① 가장 오른쪽 값을 피벗으로 정한다. 왼쪽 끝과 (피벗 제외) 오른쪽 끝에 포인터를 둔다.
② 왼쪽 포인터는 피벗 이상의 값을 만날 때까지 오른쪽으로 이동한다.
③ 오른쪽 포인터는 피벗 이하의 값을 만날 때까지 왼쪽으로 이동한다.
④ 두 포인터가 가리키는 값을 교환한다. 포인터가 만나거나 엇갈릴 때까지 ②~④ 반복.
⑤ 마지막으로 피벗을 왼쪽 포인터가 가리키는 값과 교환한다.
파티션이 끝나면 피벗은 배열 내 올바른 위치에 자리 잡는다. 양쪽의 다른 값들은 아직 정렬되지 않았더라도.
§ 2 · 분할 정복퀵소트
퀵소트는 파티션에 크게 의존한다. ① 배열을 파티셔닝한다(피벗이 제자리에). ② 피벗 왼쪽·오른쪽 하위 배열을 각각 자체 배열로 보고 ①②를 재귀적으로 반복한다. ③ 요소가 0개나 1개인 하위 배열은 기저 사례 — 아무것도 하지 않는다.
def quicksort!(left_index, right_index) # 기저 사례: 요소 0개 또는 1개 if right_index - left_index <= 0 return end pivot_position = partition!(left_index, right_index) quicksort!(left_index, pivot_position - 1) # 왼쪽 재귀 quicksort!(pivot_position + 1, right_index) # 오른쪽 재귀 end
§ 3 · N log N퀵소트의 효율성
단일 파티션은 N개 비교와 약 N/4개 교환 — 상수를 무시하면 O(N)이다. 그런데 퀵소트는 다양한 크기의 하위 배열에서 많은 파티션을 수행한다.
| N | log N | N · log N |
|---|---|---|
| 4 | 2 | 8 |
| 8 | 3 | 24 |
| 16 | 4 | 64 |
§ 4 · 한쪽 끝의 피벗최악의 시나리오
퀵소트의 최악은 피벗이 항상 하위 배열의 정중앙이 아니라 한쪽 끝에 끝나는 경우다 — 완벽한 오름차순 또는 내림차순 배열이 그렇다. 그러면 파티션이 큰 하위 배열에서 계속 수행되어 N + (N-1) + … + 2 ≈ N²/2 단계, 즉 O(N²)다.
| 최상 | 평균 | 최악 | |
|---|---|---|---|
| 삽입 정렬 | O(N) | O(N²) | O(N²) |
| 퀵소트 | O(N log N) | O(N log N) | O(N²) |
§ 5 · 정렬 없이 찾기퀵셀렉트
배열에서 "10번째로 작은 값"이나 중앙값만 알고 싶다면? 전체를 정렬할 필요는 없다. 퀵셀렉트(Quickselect)는 퀵소트와 이진 탐색의 하이브리드다.
파티션 후 피벗은 제자리에 간다. 그 위치를 보고, 찾는 값이 있을 절반에만 집중해 파티셔닝을 계속한다. 매번 한쪽 절반만 다루므로 — 퀵소트가 양쪽 모두를 다뤄 O(N log N)인 것과 달리 — 퀵셀렉트는 N + N/2 + N/4 + … ≈ 2N, 즉 O(N)이다.
def quickselect!(kth_lowest_value, left_index, right_index) if right_index - left_index <= 0 return @array[left_index] end pivot_position = partition!(left_index, right_index) if kth_lowest_value < pivot_position quickselect!(kth_lowest_value, left_index, pivot_position - 1) elsif kth_lowest_value > pivot_position quickselect!(kth_lowest_value, pivot_position + 1, right_index) else return @array[pivot_position] end end
§ 6 · 정리이 장이 남긴 것
퀵소트와 퀵셀렉트는 까다로운 문제에 아름답고 효율적인 해법을 주는 재귀 알고리즘이다. 명확하지 않지만 잘 설계된 알고리즘이 성능을 어떻게 끌어올리는지 보여준다. 알고리즘만 재귀적인 것이 아니다 — 다음 장부터 만날 연결 리스트, 이진 트리, 그래프 같은 자료구조도 재귀적이다.