[Algorithm] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

출처

퀵 정렬(Quick Sort)는 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬로 분할 정복(divide and conquer) 알고리즘을 기반으로 동작합니다.
분할 정복 알고리즘은 큰 문제를 작은 하위 문제로 나누고 각 하위 문제를 해결한 다음 그 결과를 결합하여 원래 문제를 해결하는 방식으로 진행합니다.
다만 동일하게 분할 정복 알고리즘을 활용하는 병합 정렬과는 다르게 분할되는 배열이 불균등합니다.
때문에 정렬 이후 데이터의 순서가 정렬 이전 원래 순서와 같음을 보장하지 못하는 불안정 정렬에 속합니다.

1. 주어진 배열에서 임의의 한 원소를 고릅니다. 이렇게 고른 원소를 피벗(Pivot)이라 부릅니다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눕니다. 배열을 둘로 나누는 분할을 마친 뒤 피벗은 더 이상 움직이지 않습니다.
3. 분할된 두 개의 배열에 대해 재귀적으로 이 과정을 반복합니다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복됩니다.

예제

먼저 다음과 같이 정렬되지 않은 배열이 있다고 가정하겠습니다.

위 배열을 오름차순으로 정렬하기 위한 선택 정렬 알고리즘은 다음과 같이 동작합니다.

먼저 피벗으로 사용할 요소를 선택합니다. 피벗은 어떤 요소든 될 수 있으며 해당 예제에서는 마지막 요소를 피벗으로 사용합니다.

그 후 피벗보다 작은 요소는 왼쪽으로 정렬하고 피벗보다 큰 요소는 오른쪽으로 정렬합니다.
피벗 요소는 첫 번째 인덱스로 시작하는 모든 요소와 비교됩니다.
요소가 피벗 요소보다 크면 두 번째 포인터가 추가되고 다른 요소와 비교할 때 피벗의 값보다 작은 요소가 발견되면 더 작은 요소가 이전에 식별된 더 큰 요소로 교체됩니다.
마지막에서 다음 요소까지 계속되고 마지막에는 피벗 요소가 두 번째 포인터로 대체됩니다.

값 2, 1, 3은 피벗의 값인 4보다 작기 때문에 피벗의 왼쪽에 정렬됩니다.
현재로서 왼쪽에 정렬된 요소의 순서는 상관 없고 피벗보다 작은 값이여야 합니다.
오른쪽에 정렬된 모든 요소도 순서에 상관없이 피벗보다 큰 값이여야 합니다.

최초 정렬이 끝난 후 피벗의 위치가 변경되었습니다. 해당 배열을 피벗의 위치를 기준으로 두개의 하위 배열로 나눈 후 각각의 배열데 대한 피벗을 개별적으로 선택합니다.
모든 요소가 피벗보다 작도록 하위 목록을 정렬합니다.
해당 과정을 각 하위 배열이 하나의 요소로만 구성될 때까지 위의 동작을 반복합니다.

출처

시간 복잡도

퀵 정렬의 시간 복잡도는 평균적으로 O(n log n)입니다.
매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작합니다.
평균적으로 퀵 정렬은 배열을 평균적으로 중간 요소를 피벗으로 선택하고 분할하므로 분할된 하위 배열의 크기가 균등하게 나눠지며 재귀 호출 횟수가 최소화됩니다.
하지만 배열이 이미 오름차순, 내림차순으로 정렬되어 있거나 피벗이 배열의 최대 또는 최소 요소로 선택되었을 때는 배열이 제대로 분할되지 않고 하나의 하위 배열이 매우 큰 경우 발생합니다. 이런 최악의 경우 시간 복잡도는 O(n^2)의 시간 복잡도를 가질 수 있습니다.

코드

package io.github.ones1kk.study.sorting;

public class QuickSort {

    public static void leftPivotQuickSort(int[] a) {
        l_pivot_sort(a, 0, a.length - 1);
    }

    public static void rightPivotQuickSort(int[] a) {
        r_pivot_sort(a, 0, a.length - 1);
    }

    public static void midPivotQuickSort(int[] a) {
        m_pivot_sort(a, 0, a.length - 1);
    }

    private static void l_pivot_sort(int[] a, int lo, int hi) {

        if (lo >= hi) {
            return;
        }

        int pivot = leftPartition(a, lo, hi);

        l_pivot_sort(a, lo, pivot - 1);
        l_pivot_sort(a, pivot + 1, hi);
    }

    private static int leftPartition(int[] a, int left, int right) {

        int lo = left;
        int hi = right;
        int pivot = a[left];

        while (lo < hi) {

            while (a[hi] > pivot && lo < hi) {
                hi--;
            }

            while (a[lo] <= pivot && lo < hi) {
                lo++;
            }

            swap(a, lo, hi);
        }

        swap(a, left, lo);

        return lo;
    }

    private static void r_pivot_sort(int[] a, int lo, int hi) {

        if (lo >= hi) {
            return;
        }

        int pivot = rightPartition(a, lo, hi);

        r_pivot_sort(a, lo, pivot - 1);
        r_pivot_sort(a, pivot + 1, hi);
    }

    private static int rightPartition(int[] a, int left, int right) {

        int lo = left;
        int hi = right;
        int pivot = a[right];

        while (lo < hi) {
            while (a[lo] < pivot && lo < hi) {
                lo++;
            }

            while (a[hi] >= pivot && lo < hi) {
                hi--;
            }


            swap(a, lo, hi);
        }

        swap(a, right, hi);

        return hi;
    }

    private static void m_pivot_sort(int[] a, int lo, int hi) {

        if (lo >= hi) {
            return;
        }

        int pivot = midPartition(a, lo, hi);

        m_pivot_sort(a, lo, pivot);
        m_pivot_sort(a, pivot + 1, hi);
    }

    private static int midPartition(int[] a, int left, int right) {


        int lo = left - 1;
        int hi = right + 1;
        int pivot = a[(left + right) / 2];

        while (true) {

            do {
                lo++;
            } while (a[lo] < pivot);

            do {
                hi--;
            } while (a[hi] > pivot && lo <= hi);

            if (lo >= hi) {
                return hi;
            }

            swap(a, lo, hi);
        }

    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}

좀 더 자세한 코드는 이 곳에서 확인 가능합니다.

오탈자 및 오류 내용을 댓글 또는 메일로 알려주시면, 검토 후 조치하겠습니다.