퀵 정렬(Quick Sort)과 듀얼 피봇 퀵 정렬(Dual Pivot Quick Sort)

퀵 정렬의 개념

임의의 피봇(pivot)을 기준으로 해당 피봇 값보다 작은 데이터는 피봇의 왼쪽에, 큰 데이터는 피봇의 오른쪽에 배치한 뒤, 왼쪽 부분과 오른쪽 부분을 다시 퀵 정렬 방법으로 정렬하는 알고리즘

전체 데이터를 2개의 부분으로 분할한 뒤, 각각의 부분을 다시 퀵정렬하는 전형적인 분할-정복 알고리즘

원리

quick_sort(int[] list, int left, int right) {
    if (left < right) {
        int pivot = partition(list, left, right);
        quick_sort(list, left, pivot-1);
        quick_sort(list, pivot+1, right);
    }
}

피봇을 기준으로 분할하기

퀵 정렬 구현의 핵심은 위 알고리즘의 partition()부분인 전체 배열을 피봇을 기준으로 두 부분으로 분할하는 것이다. 분할의 원리는 다음과 같다.

1. 배열의 임의의 원소를 pivot, 가장 첫번째 원소를 low, 가장 마지막 원소를 high이라고 지정한다.
2. low 값이 pivot 보다 작을 동안 low 인덱스를 증가시킨다. 반복문이 계속될 때까지 조건에 부합하는 원소들은 pivot의 왼쪽 부분 리스트가 된다.
3. high 값이 pivot 보다 클 동안 high 인덱스를 감소시킨다. 반복문이 계속될 때까지 조건에 부합하는 원소들은 pivot의 오른쪽 부분 리스트가 된다.
4. 2와 3의 반복문을 탈출하여 도달한 위치는 각각 low 값이 pivot 보다 크고, high 값이 pivot 보다 작은 경우이므로, 이 때 멈춘 두 원소 자리를 교환한다.
5. low와 high의 위치가 엇갈리지 않을 때까지 2~3의 과정을 반복한다.
6. low와 high의 위치가 엇갈리는 때 high와 pivot의 자리를 교환한다. 최종적으로 pivot의 위치를 기준으로 왼쪽에는 pivot보다 작은 원소들이, 오른쪽에는 pivot보다 큰 원소들이 위치하게 된다.

퀵 정렬 시간 복잡도

• 분할 n개의 원소를 가진 배열을 정렬한다고 하면, 배열은 각 단계에서 partition()을 거칠 때마다 n/2, n/4, n/8 …, n/(2^k) 의 크기로 분할된다. 이 과정은 배열의 원소 개수가 1개가 될 때까지 반복되므로 n/(2^k) = 1일 때까지 반복된다. 따라서 k = log n만큼의 연산이 수행된다.
• 원소 교환 각 왼쪽 부분와 오른쪽 부분에서는 교환을 위해 거의 부분의 모든 원소들을 확인해야 하므로 각 부분의 원소 개수만큼(n) 연산이 수행된다.

위 계산 결과 최종적으로 평균 O(n log n)의 시간복잡도를 보이게 된다.

하지만 매번 단 하나의 원소를 가진 부분와 나머지 원소들을 가진 부분으로 나뉘는 경우 등, 배열의 초기값이나 피봇의 선택 방법에 따라 최악의 경우 O(n^2)의 시간 복잡도를 보일 수 있다.

구현

class QuickSort {
    static int left;     // 왼쪽 커서
    static int right;    // 오른쪽 커서
    static int pivot;    // 피봇

    // 원소 교환
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 분할
    static void partition(int[] arr, int low, int high) {
        left = low;                     // 왼쪽 커서
        right = high;                   // 오른쪽 커서
        pivot = arr[(left+right)/2];    // 피봇

        do {
            while(arr[left] < pivot) left++;
            while(arr[right] > pivot) right--;
            if (left <= right) swap(arr, left++, right--);
        } while(left <= right);
    }

    // 퀵 정렬
    static void quickSort(int[] arr, int low, int high) {
        partition(arr, low, high);
        if (low < right) quickSort(arr, low, right);
        if (left < high) quickSort(arr, left, high);
    }
}

듀얼 피봇 퀵 정렬(Dual Pivot Quick Sort)

피봇 1개를 기준으로 삼아 정렬하는 퀵 정렬에서 나아가 피봇 2개를 기준으로 정렬하는 알고리즘

임의의 피봇 2개를 기준으로 pivot1 보다 작은 부분, pivot1 ~ pivot2 사이의 부분, pivot2 보다 큰 부분으로 나눈 뒤 각 부분을 다시 듀얼 피봇 퀵 정렬 방법으로 정렬한다.

pivot2는 항상 pivot1보다 크도록 설정해야함을 주의한다.

듀얼 피봇 퀵 정렬 시간 복잡도

퀵 정렬과 달리 3부분으로 나누기때문에 Θ(nlog3n)정도의 연산이 기대된다. 하지만 최악의 경우에는 퀵 정렬과 같이 O(n^2)의 시간 복잡도를 피할 수 없다.