[Sorting] 3. Quick Sort

Quick Sort

Space-Complexity = In-place sort : O(1)의 보조 메모리를 사용한다.

Time-Complexity = O(n log n)

Sorting기법 중 가장 빠르다고 해서 quick이라는 이름이 붙여졌다. 하지만 Worst Case에서는 시간복잡도가 O(n^2)가 나올 수도 있다. 하지만 constant factor가 작아서 속도가 빠르다. 

원리

Quick Sort 역시 Divide and Conquer 전략을 사용하여 Sorting이 이루어진다. Divide 과정에서 pivot이라는 개념이 사용된다. 입력된 배열에 대해 오름차순으로 정렬한다고 하면 이 pivot을 기준으로 좌측은 pivot으로 설정된 값보다 작은 값이 위치하고, 우측은 큰 값이 위치하도록 partition 된다. 이렇게 나뉜 좌, 우측 각각의 배열을 다시 재귀적으로 Quick Sort를 시키면 또 partition 과정이 적용된다.이 때 한 가지 주의할 점은 partition 과정에서 pivot으로 설정된 값은 다음 재귀과정에 포함시키지 않아야 한다. 이미 partition 과정에서 정렬된 자신의 위치를 찾았기 때문이다.

Worst Case

그렇다면 어떤 경우가 Worst Case일까? Quick Sort로 오름차순 정렬을 한다고 하자. 그렇다면 Worst Case는 partition 과정에서 pivot value가 항상 배열 내에서 가장 작은 값 또는 가장 큰 값으로 설정되었을 때이다. 매 partition마다 unbalanced partition이 이뤄지고 이렇게 partition이 되면 비교 횟수는 원소 n개에 대해서 n번, (n-1)번, (n-2)번 … 이 되므로 시간 복잡도는 O(n^2)이 된다.

Pivot value

자연스럽게 Best-Case는 두 개의 subproblems의 크기가 동일한 경우가 된다. 즉 partition 과정에서 반반씩 나뉘게 되는 경우인 것이다. 그렇다면 Partition 과정에서 pivot을 어떻게 정할 것인가가 중요해진다. 어떻게 정할하면 정확히 반반의 partition이 아니더라도 balanced-partitioning 즉, 균형 잡힌 분할을 할 수 있을까? 배열의 맨 뒤 또는 맨 앞에 있는 원소로 설정하는가? Random으로 설정하는 것은 어떨까? 특정 위치의 원소를 pivot으로 설정하지 않고 배열 내의 원소 중 임의의 원소를 pivot으로 설정하면 입력에 관계없이 일정한 수준의 성능을 얻을 수 있다. 또 악의적인 입력에 대해 성능 저하를 막을 수 있다.

Partition

정작 중요한 Partition은 어떻게 이루어지는가에 대한 이야기를 하지 않았다. 가장 마지막 원소를 pivot으로 설정했다고 가정하자. 이 pivot의 값을 기준으로 좌측에는 작은 값 우측에는 큰 값이 오도록 해야 하는데, 일단 pivot은 움직이지 말자. 첫번째 원소부터 비교하는데 만약 그 값이 pivot보다 작다면 그대로 두고 크다면 맨 마지막에서 그 앞의 원소와 자리를 바꿔준다. 즉 pivot value의 index가 k라면 k-1번째와 바꿔주는 것이다. 이 모든 원소에 대해 실행하고 마지막 과정에서 작은 값들이 채워지는 인덱스를 가리키고 있는 값에 1을 더한 index 값과 pivot 값을 바꿔준다. 즉, 최종적으로 결정될 pivot의 인덱스를 i라고 했을 때, 0부터 i-1까지는 pivot보다 작은 값이 될 것이고 i+1부터 k까지는 pivot 값보다 큰 값이 될 것이다.

c code> 

//Quick Sort
void quick_sort(int * arr, int left, int right) {
    if(left >= right) return;
    
    int pivotPos = partition(arr, left, right);
    quick_sort(arr, left, pivotPos-1);
    quick_sort(arr, pivotPos+1, right);
}

//Partitioning!
int partition(int * arr, int left, int right) {
    
    if(arr == NULL || left < 0) return -1;
    
    int pivotValue = arr[right];
    int endOfLowBlock = left - 1;
    
    for(int tempPos = left; tempPos < right; tempPos++) {
        if(pivotValue > arr[tempPos]) {
            swapValue(&arr[tempPos], &arr[++endOfLowBlock]);
        }
    }
    swapValue(&arr[right], &arr[++endOfLowBlock]);
    
    return endOfLowBlock;
}

//util - swap
void swapValue(int * a, int * b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}