퀵 정렬 (Quick Sort)

들어가는 말

퀵 정렬은 배열에서 먼저 기준이 되는 값인 피벗(Pivot)을 하나 선택한다.
피벗을 기준으로 값을 재배치해 한쪽에는 피벗보다 작은 값들이, 다른 한쪽에는 피벗보다 큰 값들이 모이게 한다.
이후 나뉜 각 구간에 같은 과정을 반복하면 전체 배열이 정렬된다.
병합 정렬처럼 큰 문제를 작은 문제로 나누어 해결한다는 점에서 퀵 정렬도 분할 정복 알고리즘에 속한다.
평균 시간 복잡도는 O(n log n)이고 별도의 임시 배열이 필요하지 않아 실용적으로 빠르다.
다만 피벗 선택이 계속 불균형하면 최악의 경우 O(n²)까지 느려질 수 있으며, 이를 줄이기 위한 여러 피벗 선택 방법이 있다.

정렬 과정 살펴보기

7 2 8 4 9 1 5 3을 오름차순으로 정렬해 보자.

첫 번째 분할

처음 정렬할 구간은 배열 전체인 7 2 8 4 9 1 5 3이다.
가운데 인덱스 3에 있는 값 4를 피벗으로 선택한다.
왼쪽 포인터는 피벗 이상인 값을 찾고, 오른쪽 포인터는 피벗 이하인 값을 찾아 서로 교환한다.

단계	왼쪽 포인터	왼쪽 포인터의 값	오른쪽 포인터	오른쪽 포인터의 값	배열 상태
초기 상태	0	7	7	3	7 2 8 4 9 1 5 3
7과 3 교환	1	2	6	5	3 2 8 4 9 1 5 7
포인터 이동	2	8	5	1	3 2 8 4 9 1 5 7
8과 1 교환	3	4	4	9	3 2 1 4 9 8 5 7
포인터 이동	3	4	3	4	3 2 1 4 9 8 5 7
분할 완료	3	4	3	4	3 2 1 4 9 8 5 7

분할이 끝나면 피벗 4 이하인 값은 왼쪽 구간에, 피벗 4 이상인 값은 오른쪽 구간에 모인다.

왼쪽 구간 분할

왼쪽 구간 3 2 1 4의 가운데 인덱스 1에 있는 값 2를 피벗으로 선택한다.

단계	왼쪽 포인터	왼쪽 포인터의 값	오른쪽 포인터	오른쪽 포인터의 값	배열 상태
초기 상태	0	3	3	4	3 2 1 4
포인터 이동	0	3	2	1	3 2 1 4
3과 1 교환	1	2	1	2	1 2 3 4
분할 완료	1	2	1	2	1 2 3 4

분할이 끝나면 피벗 2 이하인 값은 왼쪽 구간에, 피벗 2 이상인 값은 오른쪽 구간에 모인다.

사람이라면 지금 정렬이 완료되었다는 것을 알고 멈출 수 있지만, 컴퓨터는 그렇지 않다.
컴퓨터는 각 구간에 원소가 하나만 남을 때까지 피벗을 선택해 분할하는 과정을 반복한다.
따라서 1 2와 3 4 구간에도 같은 과정을 반복한다.

오른쪽 구간 분할

오른쪽 구간 9 8 5 7의 가운데 인덱스 5에 있는 값 8을 피벗으로 선택한다.

단계	왼쪽 포인터	왼쪽 포인터의 값	오른쪽 포인터	오른쪽 포인터의 값	배열 상태
초기 상태	4	9	7	7	9 8 5 7
9과 7 교환	5	8	6	5	7 8 5 9
8과 5 교환	6	8	5	5	7 5 8 9
분할 완료	6	8	5	5	7 5 8 9

분할이 끝나면 피벗 8 이하인 값은 왼쪽 구간에, 피벗 8 이상인 값은 오른쪽 구간에 모인다.
이 구현에서는 분할 과정에서 피벗 값도 다른 값과 교환될 수 있으므로, 피벗의 최종 위치가 처음 선택한 위치와 달라질 수 있다.
이후 7 5와 8 9 구간에도 같은 과정을 반복한다.

분할 과정 요약

순서	호출 구간	피벗	호출 시 배열 상태	분할 후 배열 상태
1	7 2 8 4 9 1 5 3	인덱스 3의 4	7 2 8 4 9 1 5 3	3 2 1 4 9 8 5 7
2	3 2 1 4	인덱스 1의 2	3 2 1 4 9 8 5 7	1 2 3 4 9 8 5 7
3	1 2	인덱스 0의 1	1 2 3 4 9 8 5 7	1 2 3 4 9 8 5 7
4	3 4	인덱스 2의 3	1 2 3 4 9 8 5 7	1 2 3 4 9 8 5 7
5	9 8 5 7	인덱스 5의 8	1 2 3 4 9 8 5 7	1 2 3 4 7 5 8 9
6	7 5	인덱스 4의 7	1 2 3 4 7 5 8 9	1 2 3 4 5 7 8 9
7	8 9	인덱스 6의 8	1 2 3 4 5 7 8 9	1 2 3 4 5 7 8 9

시간 복잡도

퀵 정렬의 시간 복잡도는 피벗이 배열을 얼마나 균등하게 나누는지에 따라 달라진다.
한 번의 분할에서는 현재 구간의 원소를 피벗과 비교하고 재배치하므로 구간의 원소 수에 비례하는 O(n)의 시간이 든다.
피벗이 배열을 비슷한 크기의 두 구간으로 나누면 한쪽 부분 구간의 크기는 n, n / 2, n / 4처럼 줄어들어 분할 단계는 약 log₂ n개가 된다.
따라서 피벗이 배열을 균등하게 나누는 최선의 경우와 평균적으로 한쪽에 치우치지 않는 경우의 시간 복잡도는 O(n log n)이다.

반면 피벗이 계속 최솟값이나 최댓값으로 선택되면 부분 구간의 크기가 n - 1, n - 2, n - 3처럼 줄어든다.
이 경우 분할 단계가 n에 비례하므로 최악의 경우 시간 복잡도는 O(n²)이다.
이처럼 피벗이 한쪽으로 치우치는 문제를 줄이는 방법으로는 무작위 피벗 선택(Random Pivot), 세 원소의 중앙값 선택(Median-of-Three), 중앙값의 중앙값 선택(Median-of-Medians) 등이 있다.

소스 코드

#include <stdio.h>

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high)
{
    int pivot = arr[(low + high) / 2];
    int left = low;
    int right = high;

    while (1)
    {
        while (arr[left] < pivot)
            left++;

        while (arr[right] > pivot)
            right--;

        if (left >= right)
            return right;

        swap(&arr[left], &arr[right]);
        left++;
        right--;
    }
}

void quick_sort(int arr[], int low, int high)
{
    if (low >= high)
        return;

    int split_index = partition(arr, low, high);

    quick_sort(arr, low, split_index);
    quick_sort(arr, split_index + 1, high);
}

int main(void)
{
    int arr[] = { 7, 2, 8, 4, 9, 1, 5, 3 };
    int size = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, 0, size - 1);

    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]); // Result: 1 2 3 4 5 7 8 9

    return 0;
}

구현 설명

quick_sort는 현재 정렬할 구간의 시작 인덱스 low와 마지막 인덱스 high를 매개변수로 받는다.
low >= high라면 구간에 원소가 하나 이하이고 이미 정렬된 상태라서 재귀 호출을 종료한다.
원소가 둘 이상이면 partition을 호출해 분할 경계를 split_index에 저장한다.
그런 다음 low부터 split_index까지의 왼쪽 구간과 split_index + 1부터 high까지의 오른쪽 구간을 각각 재귀적으로 정렬한다.

partition은 현재 구간의 가운데 값인 arr[(low + high) / 2]를 피벗으로 선택한다.
left는 구간의 시작인 low에서, right는 구간의 끝인 high에서 출발한다.
left는 피벗 이상인 값을 만날 때까지 오른쪽으로 이동하고, right는 피벗 이하인 값을 만날 때까지 왼쪽으로 이동한다.

두 포인터가 교차하지 않았고 서로 다른 위치를 가리킨다면, 각 포인터가 찾은 값이 피벗을 기준으로 서로 반대쪽 영역에 있으므로 두 값을 교환한다.
포인터가 교차하거나 같은 위치에서 만나면 분할이 끝나며, right는 두 부분 구간의 경계가 된다.
이 시점에 right 이하에는 피벗 이하인 값만 있고, right + 1 이상에는 피벗 이상인 값만 있다.

partition이 경계인 right를 반환하면, quick_sort는 이를 기준으로 나뉜 왼쪽과 오른쪽 부분 구간에 같은 과정을 재귀적으로 적용한다.
부분 구간의 원소가 하나 이하가 되면 재귀 호출이 종료되며, 이 과정이 모두 끝나면 전체 배열이 정렬된다.