Quick Sort [퀵정렬]

Quick Sort는 Merge Sort와 같이 분할정복을 이용한 정렬법이지만, 공간을 n만큼 더 사용하는 merge sort와 달리 in-place sort 입니다.

pivotpoint가 항상 맨 앞일 때를 가정한 코드는 다음과 같습니다.

int partition(int S[], int low, int high){
    int pivotpoint = low;
    int j=low;
    for(int i=low+1; i<=high; i++){
        if(S[i]<S[pivotpoint]){
            j++;
            exchange(S[i],S[j]);
        }
    }
    exchange(S[pivotpoint],S[j]);
    return j;
}

void quickSort(int S[], int low, int high){
    if(low<high){
        int pivotpoint = partition(S,low,high);
        quickSort(S,low,pivotpoint-1);
        quickSort(S,pivotpoint+1,high);
    }
}

여기서 exchange 함수는 두 값을 바꾸는 함수입니다. 따로 적어두진 않았습니다.

 

merge sort와의 공통점은 앞서 말했다시피 분할정복을 이용한 정렬법이라는 것이고, 차이점은 in-place sort이며 pivot이 존재합니다.

pivot은 분할을 하는 기준으로, pivot을 기준으로 작은 값들과 큰 값들로 나누어 분할합니다.

 

큰 덩어리를 특정 값 기준으로 작은 값, 큰 값으로 나누다보면 마지막엔 2개의 값씩 비교하게 되므로, 최종적으로 정렬이 완료됩니다.

 

다음은 WorstCase Time Complexity(최악의 경우 시간 복잡도)를 구하는 과정입니다.

따라서 Quick Sort의 WorstCase Time Complexity는 n^2입니다.

그러면 n^2가 보장되는 더 쉬운 알고리즘인 bubbleSort나 insertionSort를 사용하지, quickSort를 왜 사용할까요?

 

AverageCase Time Complexity(평균 시간 복잡도)를 구해보겠습니다.

따라서 quickSort의 AverageCase time Complexity는 𝜃(nlg(n))입니다.