Quick Sort에서 pivot 설정하기

#algorithm

퀵정렬에서 피벗을 효율적으로 설정하기

2024년 12월 27일

퀵정렬의 피벗

퀵정렬은 매우 높은 성능을 내지만 피벗의 위치에 따라 성능 차이가 많이 발생한다. 퀵졍렬의 방식을 간단히 나타내면 아래와 같다.

리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

백준 11004 문제를 퀵정렬를 이용해서 푸는데 피벗을 마지막 원소로 했더니 50% 가량에서 계속 시간초과가 발생했다.

위 문제는 각종 언어에서 제공해주는 정렬 함수를 사용하면 손쉽게 바로 풀리지만 퀵정렬를 직접 구현해서 풀고 싶었는데 계속해서 시간초과가 발생했다.

인터넷에서 나오는 퀵정렬 예제에서는 피벗을 마지막 원소에 두는 경우가 많은데 이를 이용할 경우 백준 11004 문제에서는 시간초과가 발생한다.

피벗을 중간 원소로 설정하면 해결이 되는데 왜 피벗을 마지막 원소로 두면 안되는걸까.

피벗을 마지막 원소로 하는 코드 (로무토 분할)

int partition(vector<int>& v, int low, int high) {
    int pivot = v[high];
    
    int i = low - 1;
    for(int j=low; j<=high; j++) {
        if(v[j] < pivot){
            i++;
            swap(v[i], v[j]);
        }
    }
    swap(v[i+1], v[high]);
    
    return i+1;
}

피벗을 중간 원소로 하는 코드 (호어 분할)

int partition(vector<int>& v, int low, int high) {
    int m = (low + high) / 2;
    swap(v, low ,m); // 중앙값을 1번째 요소로 이동
    
    int pivot = v[low];
    
    int i = low+1, j = high;
    
    while(i<=j){
        while(j>=low+1 && pivot <v[j]) j--;
        while(i<= high && pivot > v[i]) i++;
        if(i<j){
            swap(v, i++, j--);
        }else {
            break;
        }
    }
    
    v[low] = v[j];
    v[j] = pivot;
    return j; 
}

퀵정렬은 일반적으로 재귀함수로 구현을 하는데 피벗을 마지막 원소로 선택하는 경우 리스트가 사전에 정렬된 경우 시간복잡도가 O(n^2)으로 떨어진다.

퀵정렬의 시간복잡도는 O(nlogn) ~ O(n^2)으로 O(n^2)가 될 경우를 최대한 피해야 된다.

퀵정렬 partition 함수를 사용하는데 리스트의 양 끝 원소를 피벗으로 설정할 경우 분배에 비균형이 생긴다.

피벗을 중간 원소로 선택하는 경우 배열이 더 균형있게 나누어져 재귀 호출이 깊어지는 것을 방지할 수 있어 O(nlogn)에 근접하도록 도와준다.

Median of Three

위의 내용에서 성능을 더욱 높이는 방법이 존재하는데 Median of Three 방식이다. 실제로 많은 라이브러리에서 해당 방식을 이용한다고 한다(위키피셜).

Median of Three를 단계별로 간단히 나타내면 아래와 같다.

맨 앞, 중간, 맨 뒤 원소를 사전 정렬한다.
세 값 중에서 중간 값을 피벗으로 설정한다.
다음 과정은 일반적인 퀵정렬과 동일하게 진행한다.

Median of Three를 구현할 때 조금 더 신경 써야 할 점은 선정된 피벗을 앞에서 두 번째 원소나 뒤에서 두 번째 원소랑 swap을 하고 비교 연산으로 넘어가야 한다. 그러면 양 끝과 피벗은 이미 정렬이 된 상태이므로 나머지 부분만 정렬하면 된다.

또한 백준 11004 문제는 퀵정렬을 이용해도 분할 방식을 로무토 방식을 이용하면 90% 가량에서 시간초과가 발생한다. 호어 분할로 바꾸니 정상적으로 성공했다.