2. [CS] O(n log n) 정렬 - 퀵 정렬(Quick sort)

서론

이전에 IntroSort에 대한 설명글에서 퀵 정렬(Quick sort)에 대한 슈도코드와 간략한 설명을 다루었다. 이번 글에서는 퀵 정렬에 대한 구체적인 동작 방식과 효율성에 대해서 알아보도록 하자.

퀵 정렬(Quick sort)

퀵 정렬은 분할 정복(Divide and Conquer) 방식의 정렬 알고리즘이다. 기준이 되는 피벗(Pivot)을 하나 선택하고, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할해가며 정렬을 수행한다. 평균적으로 매우 빠르며($O(n log n)$), 제자리 정렬(추가적인 임시 배열을 사용하지 않음)이기 때문에 공간 효율성도 좋다.

Quick sort 과정 (namu wiki)

 

분할 정복

퀵 정렬은 앞서 설명했듯이 분할 정복을 사용해서 피벗을 기준으로 피벗보다 큰쪽, 피벗보다 작은쪽으로 배열을 분할하여 분할 정복이 진행된다.

log n (https://www.cs.cornell.edu/courses/cs3110/2011sp/Lectures/lec19-master/master.htm)

따라서 배열의 분할이 계속해서 $\frac{n}{2}$로 맞아떨어질 경우 같은 $O(n log n)$ 정렬 알고리즘중에서 월등한 시간복잡도를 가진다. (그래도 $O(n log n)$ 라는 한계가 있긴 함.)

피벗 선택

다만 퀵 정렬은 피벗의 선택 방법에 따라 시간 복잡도가 매우 떨어질 수 있다. 앞서 피벗을 선택하고 피벗을 기준으로 배열을 나눠 분할 정복을 시도한다고 했는데 만약 피벗으로 최댓값이나 최소값을 선택하고 그것이 반복된다면 시간복잡도가 $O(n^2)$으로 감소하게 된다.

최악의 경우

그러면 피벗을 무슨 기준으로 선택해야 할까? 여러 가지 기법들이 있는데 대표적인 게 피벗을 랜덤으로 선택(Random quick sort)하거나 N개의 원소를 골라서 중간값을 피벗으로 선택(Median of Three)하는 것으로 최악의 경우를 줄일 수 있다. 하지만 이 방법들을 사용하더라도 최악의 경우가 발생할 수 있기 때문에 퀵 정렬은 이전 글에서 설명한 인트로 소트등 하이브리드 정렬을 통해 $(O(nlogn)$의 시간복잡도를 보장하는 방식으로 주로 사용된다(C/C++, Unreal).

구현 예시

1. 피벗 선택

int pivot = arr[(i + j) / 2];

• 구간의 중간 값을 피벗으로 선택
• 성능 개선을 위해 다양한 방식이 가능 (예: median-of-three)

2. 양쪽 포인터 설정 및 분할

int i = left, j = right;

• i: 왼쪽에서 오른쪽으로 스캔
• j: 오른쪽에서 왼쪽으로 스캔

while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;

• 왼쪽에서 피벗보다 크거나 같은 수
• 오른쪽에서 피벗보다 작거나 같은 수를 찾는다

3. 값 교환 & 인덱스 갱신

if (i <= j) swap(arr[i++], arr[j--]);

• i <= j일 때만 교환: 양쪽을 정확히 분할
• 교환 후 각각 다음 인덱스로 이동

4. 재귀 호출 (Divide)

if (left < j) QuickSort(arr, left, j);
if (i < right) QuickSort(arr, i, right);

• 왼쪽 구간과 오른쪽 구간으로 재귀적으로 다시 퀵 정렬 수행
• 이 과정에서 점점 작은 문제로 나뉘고, 결국 정렬 완료됨

전체 코드

#include <bits/stdc++.h>
using namespace std;

void QuickSort(vector<int>& arr, int left, int right)
{
	int i = left, j = right;
	int pivot = arr[(i + j) / 2];

	do
	{
		while (arr[i] < pivot)i++;
		while (arr[j] > pivot)j--;

		if (i < j) swap(arr[i++], arr[j--]);
		else if (i == j) i++, j--;
	} while (i <= j);
	
	if (left < j) QuickSort(arr, left, j);
	if (i < right) QuickSort(arr, i, right);
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	vector<int> arr = { 38, 27, 43, 3, 9, 82, 10 };
	QuickSort(arr, 0, arr.size() - 1);

	for (auto i : arr)cout << i << ' ';
}