퀵 정렬 (Quick sort)

분할정복법과 퀵 정렬 (Quick sort)

퀵 정렬은 합병 정렬과 마찬가지로 분할정복법을 사용하지만 그 방법에 있어서 차이가 있습니다.
퀵 정렬에서는 정렬할 데이터가 주어지면 하나의 값을 기준값(pivot)으로 사용하여 정렬을 합니다. 어떤 값을 기준값으로 설정하는지가 퀵정렬의 성능을 좌우합니다.

분할정복법 3단계를 바탕으로 퀵정렬의 과정을 알아보겠습니다.

1. 분할 : 하나의 값을 기준값(pivot)으로 설정 한 후 데이터들을 기준값보다 큰 값과 작은값으로 분류한다.
2. 정복 : 분할한 양쪽을 각각 재귀로 퀵 정렬한다.
3. 합병 : 이미 분할 과정에서 정렬이 완료되었기 때문에 따로 과정이 없다.

퀵 정렬 의사 코드

의사 코드는 다음과 같습니다.

quickSort(A[], p, r) {
    if(p<r) then{
        q = partition(A, p, r);    // 분할
        quickSort(A, p, q-1);    // 왼쪽 부분배열 정렬
        quickSort(A, q+1, r);    // 오른쪽 부분배열 정렬
    }
}

partition(A[], p, r) {
    배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고
    A[r]이 자리한 위치를 return
}

배열 A의 인덱스 p에서 r사이에 있는 데이터를 정렬합니다. 조건문으로 p가 r보다 작은 경우에만 알고리즘이 실행되도록 합니다. 다음으로 partion 함수는 기준값(pivot)을 기준으로 전체 데이터를 나눠주고 피봇 인덱스를 반환하는 역할을 합니다. 따라서, q는 피봇이 됩니다.

[p, q-1] 은 배열의 왼쪽 부분, 작은 값이고
[q+1, r] 까지는 배열의 오른쪽 부분, 큰 값입니다.
재귀적으로 quickSort 함수를 호출해 정렬합니다.

위의 그림에서 기준값(pivot)으로 인덱스의 마지막 값을 사용하고 있습니다. 위의 그림 기준에서 현재 인덱스 j의 값이 기준값보다 크다면 j를 증가시켜 다음값으로 넘어갑니다.
그러나 인덱스 j의 값이 기준값보다 작다면 앞쪽으로 보내야하는데, 이때 i값을 1 증가 시킨 후 그 값과 교환합니다.

위의 과정은 기준값을 마지막 인덱스의 값인 15로 설정하고 i와 j를 증가시키면서 정렬하는 과정을 보여줍니다. 모든 정렬이 완료되면 인덱스 i+1의 값과 기준값의 위치를 변경합니다.

Partition(A, p, r){
    x<-A[r];
    i<-p-1;
    for j<-p to r-1
    if A[j] <= x then
        i<-i+1;
        exchange A[i] and A[j];
    exchange A[i+1] and A[r];
    return i+1;
}

Partition 함수를 더 자세한 의사 코드로 나타냈습니다. 앞서 설명한 위치 변환과 인덱스 증가로 정렬을 완료하고 마지막으로 기준값(pivot)의 인덱스를 리턴합니다.

퀵 정렬 c++ 코드

이제 의사 코드를 바탕으로 c++ 코드를 작성하면 다음과 갖습니다. (의사 코드와는 완전히 일치하지는 않습니다.)

#include <iostream>

#define ITEM_SIZE 10

using namespace std;

void print_arr(int a[], int size) {
    for (int i = 0; i < size; i++) {
        cout << a[i] << ' ';
    }
    cout << '\n';
}

int partition(int a[], int left, int right) {
    int pivot = right;
    int i = left - 1;
    int j = left;
    int tmp;

    if (left < right) {
        while (j < right) {
            if (a[j] < a[pivot]) {
                tmp = a[j];
                a[j] = a[i + 1];
                a[i + 1] = tmp;
                i++;
            }
            j++;
        }
        tmp = a[pivot];
        a[pivot] = a[i + 1];
        a[i + 1] = tmp;
    }
    pivot = i + 1;

    return pivot;
}

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

int main() {
    int a[ITEM_SIZE] = { 15, 2, 24, 18, 7, 13, 12, 4, 21, 9 };
    print_arr(a, ITEM_SIZE);
    quick_sort(a, 0, ITEM_SIZE - 1);
    print_arr(a, ITEM_SIZE);
    return 0;
}

퀵 정렬 시간 복잡도

퀵 정렬에서의 시간 복잡도는 파티션(분할) 하는데 모든 데이터를 한번씩 비교하면 되므로 n이 됩니다. 정확하게 말하자면 데이터의 개수가 n개일때, n-1 번의 비교가 이루어집니다.

합병 정렬보다는 시간 복잡도를 구하는게 조금 더 복잡한데, 합병 정렬은 항상 2개로 나뉘는것과 달리 퀵 정렬은 항상 양쪽이 고르게 나누어지지 않기 때문입니다.

먼저 최악의 경우부터 생각해보면 모든 배열이 정렬되어있을 때, 기준값이 최대/최소 값일 때, 최악의 시간 복잡도가 발생합니다. 분할은 0개와 나머지 전체로 나누어지므로 결국 데이터는 아무변화가 없고 똑같은 루틴이 반복되기 때문에 시간 복잡도는 **O(n^2)**가 됩니다.

반대로 최선의 경우는 항상 절반으로 분할되는 경우로, 이 때는 합병 정렬과 동일한 시간인 **O(nlogn)**의 시간을 같습니다.

퀵 정렬은 다른 정렬 알고리즘보다 대체로 빠르기 때문에 퀵 정렬 이라는 이름이 붙었습니다. 그렇지만 최악의 경우에는 O(n^2)의 느린 속도를 보여줬는데 왜 퀵 정렬이 다른 알고리즘 보다 빠른 걸가요?

최선의 경우와 최악의 경우는 극단적인 케이스라서 실제적으로 일어나기 어려운 상황입니다.

현식적으로 가정했을 때, n개의 데이터가 항상 9:1로 분할 된다고 하면 한 단계 당 분할되는 시간을 구하면 항상 n이므로 전체 비교 연산은 트리의 깊이 * n 입니다.
트리는 대칭적이지 않으므로 가장 깊은 오른쪽 경로(최악의 경우)를 예로 들면 (9/10)^k * n = 1이 됩니다.
따라서 시간 복잡도 k = log9/10(n)이 됩니다.

이 예가 의미하는 것은 퀵 정렬의 성능은 파티션이 얼마나 밸런스있게 나뉘냐에 결정된다는 것입니다. 극단적인 경우만 아니라면 퀵 정렬의 시간 복잡도는 nlogn 이 되므로 실제로 상당히 빠른 정렬 방법이 됩니다.

출처 : 2015 봄학기 알고리즘 - 부경대 권오흠 교수님