빠른 정렬 - 분할 정복, 시간 복잡도

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

빠른 정렬

병합 정렬과 반대로 분할하는 과정에서 정렬된다. 배열의 원소 중 하나를 기준으로 하여 다른 원소들과 비교해 자리를 교환하며 정렬한다. 

시간 복잡도

수행시간은 문제를 두 개의 부분 문제로 나누는 과정에 의해 지배된다. 병합 과정과 달리 분할된 부분 문제가 비슷한 크기로 나눠진다는 보장이 없다. 기준 원소가 최소값 혹은 최대값인 경우에 부분 문제의 크기가 하나씩만 줄어들 수도 있다. 이런 최악의 경우 O(n^2)의 시간 복잡도를 가진다.

 

평균적으로 부분 문제가 절반에 가깝게 나눠질 때 병합 정렬과 같은 O(nlgn)의 시간 복잡도를 가진다. 이런 경우는 단지 나눌 때 정렬하는지, 합칠 때 정렬하는지의 차이라고 볼 수 있다.

C++ 코드

빠른 정렬은 다양한 형태로 구현될 수 있는데 핵심은 배열의 원소 중 하나를 기준으로 정하고 그 보다 작은 값을 앞으로, 큰 값을 뒤로 이동시키며 정렬한다는 점이다. 이를 생각하면서 다음 두 가지 구현을 살펴보자.

 

첫 번째 구현은 배열의 첫 원소를 기준 원소로 하고 배열에서 기준 원소보다 작은 값을 찾을 때마다 head 포인터를 뒤로 이동시킨다. 모든 원소를 확인했다면 기준 원소와 head 원소를 바꾼다. 결국 기준 원소는 그보다 작은 원소들의 바로 뒤에 위치한다. 그 후 기준 원소 전과 후의 배열에 대해 각각 동일한 작업을 재귀적으로 반복한다.

 

핵심은 head 포인터가 배열에서 기준 원소보다 작은 값의 개수만큼 이동한다는 것 (그 뒤에 기준 원소를 위치시켜야 하므로) 이고 따라서 매번 과정이 끝나면 기준 원소의 배열내 위치가 특정되며 이 위치의 양쪽에 있는 두 배열에 대해 같은 과정을 재귀적으로 실시한다는 것이다.

 

vector<int> arr;

void swap(int a, int b){
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

void quickSort1(int lo, int hi) {
    if (hi <= lo) return;

    int pivotItem = arr[lo], head = lo; 

    for (int i = lo + 1; i <= hi; ++i) {
        if (arr[i] < pivotItem) {
        	// 기준 원소보다 작은 값의 개수만큼 head 를 뒤로 이동
            ++head;
            // 기준 원소보다 작은 값들을 모두 앞쪽으로 옮긴다.
            // 결국 이 작은 값들이 마지막 head 보다 앞에 위치하게 되고,
            swap(i, head);
        }
    }
    // 마지막으로 head 와 기준 원소의 위치만 바꾸면 
    // 기준 원소의 위치는 특정되고 그보다 작은 값들은 모두 그 앞에 있다.
    swap(lo, head);

    quickSort1(lo, head - 1);
    quickSort1(head + 1, hi);
}

 

두 번째 구현도 문제의 맨 앞 원소가 기준이 된다. 구현 형태가 꽤 다르지만 역시 기준 원소가 위치할 인덱스를 찾는다는 점은 같다.

 

기준 원소를 제외한 맨 앞 원소를 가리키는 head 포인터와 맨 뒤 원소를 가리키는 tail 포인터를 사용한다. head 가 가리키는 원소는 기준 원소보다 작아야 다음 인덱스를 가리키도록 한다. 즉, head 가 기준 원소보다 큰 원소를 가리키도록 인덱스를 증가한다. 마찬가지로 tail 이 기준 원소보다 작은 원소를 가리키도록 인덱스를 감소한다.

 

두 포인터를 조정하다가 교차되는 순간이 왔을 때 tail 의 위치가 기준 원소의 자리가 된다. 자세한 구현은 코드의 주석으로 확인해보자.

 

vector<int> arr;

void swap(int a, int b){
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

void quickSort2(int lo, int hi) {
    if (hi <= lo) return;

    int pivot = arr[lo];
    int head = lo + 1, tail = hi;

    while (head < tail) {
    	// head 의 원소가 기준 원소보다 큰 인덱스를 찾는다. (작을 때 포인터 이동)
        while (arr[head] < pivot && head < hi) ++head;
        // tail 의 원소가 기준 원소보다 작은 인덱스를 찾는다. (클 때 포인터 이동)
        while (pivot < arr[tail]) --tail;

		// head, tail 이 교차되지 않았다면 둘을 교환한다.
        // 그럼 작은값(tail 이 찾은 값)이 앞으로, 큰값(head 가 찾은 값) 이 뒤로
        // 옮겨지므로 다시 위의 두 while 문을 통해 교차되는 순간을 찾을 수 있다.
        if (head < tail) swap(head, tail);
        // 교차되는 순간의 tail 위치가 기준 원소의 정렬된 위치이다.
        else swap(lo, tail);
    }

    quickSort2(lo, tail - 1);
    quickSort2(tail + 1, hi);
}