[Programming/Algorithm] 퀵 정렬(Quick Sort)

병합 정렬과 마찬가지로 '분할 정복(divide and conquer)'에 근거하여 만들어진 정렬 방법이다. 실제로 퀵 정렬 역시 정렬 대상을 반씩 줄여나가는 과정을 포함한다.

퀵 정렬은 그 이름이 의미하듯이 평균적으로 매우 빠른 정렬의 속도를 보이는 알고리즘이다.

퀵 정렬의 대상

위 그림에서는 퀵 정렬의 대상이 되는 배열을 보이고 있다. 

• left : 정렬대상의 가장 왼쪽 지점을 가리키는 이름
• right : 정렬대상의 가장 오른쪽 지점을 가리키는 이름

피벗(pivot)의 사전적 의미는 다음과 같다.

pivot : 중심점, 중심축의 의미

즉 피벗은 정렬을 진행하는데 필요한 일종의 '기준'이라 할 수 있따. 때문에 정렬의 진해을 위해서는 피벗이라는 것을 진행해야 한다.

• low : 피벗을 제외한 가장 왼쪽에 위치한 지점을 가리키는 이름
• high : 피벗을 제외한 가장 오른쪽에 위치한 지점을 가리키는 이름

결과적으로 right와 high는 같은 위치를 가리킨다. 하지만 피벗을 가장 왼쪽 데이터가 아닌 가장 오른쪽 데이터로 결정한다면 이야기는 달라진다.

퀵 정렬의 기본 1/5

위 그림에서 보이듯이 low는 오른쪽으로, high는 왼쪽으로 이동시킨다. 이때 이동의 기준은 다음과 같다.

• low의 오른쪽 방향 이동 : 피벗보다 큰 값을 만날 때까지
• high의 왼쪽 방향 이동 : 피벗보다 작은 값을 만날 때까지

물론 이는 오름차순 정렬의 경우를 대상으로 한 설명이다. 따라서 이를 일반화하면 다음과 같이 정리해야 한다.

• low의 오른쪽 방향 이동 : 피벗보다 정렬의 우선순위가 낮은 데이터를 만날 때까지
• high의 왼쪽 방향 이동 : 피벗보다 정렬의 우선순위가 높은 데이터를 만날 때까지

여기서 low와 high의 이동은 완전히 별개이다. 서로 사이 좋게 한 칸씩 왼쪽으로, 그리고 오른쪽으로 이동을 한다거나 할 필요가 없다.

그리하여 위 그림의 상황에서 low는 7이 저장된 위치에 머물고, high는 4가 저장된 위치에 머물게 된다. 이렇게 해서 low와 high는 각각 7과 4를 가리키게 되는데, 이때 이 둘이 가리키는 데이터를 서로 교환하여 다음의 상태가 되게 한다.

퀵 정렬의 기본 2/5

7과 4의 교환 후에도 계속해서 low는 오른쪽으로, high는 왼쪽으로 이동한다. 마찬가지로 low는 피벗보다 큰 값을 찾고, high는 피벗보다 작은 값을 찾는다. 따라서 low와 high는 각각 9와 2를 가리키게 되고, 이번에도 이 둘을 교환하여 다음 그림의 상태가 되게 한다.

퀵 정렬의 기본 3/5

교환 후에도 low는 피벗보다 큰 값을 찾을 때까지 오른쪽으로, high는 피벗보다 작은 값을 찾을 때까지 왼쪽으로 이동해 나간다. 그러면 결국에는 다음과 같이 low와 high가 가리키는 위치가 교차되는 상황이 발생한다.

퀵 정렬의 기본 4/5

이때는 low와 high가 가리키는 값을 교환하지 않는다. 이 상황은 low와 high의 이동 및 교환의 과정이 완료되었음을 의미하기 때문이다. 따라서 이번에는 다음 그림에서 보이듯이 피벗과 high가 가리키는 데이터를 셔로 교환하여 다음 그림의 상태가 되게 한다.

퀵 정렬의 기본 5/5

피벗이었던 5가 제 위치를 찾아 정렬되었다. 즉, 피벗의 왼편에는 피벗보다 작은 값들이 위치하고, 피벗의 오른편에는 피벗보다 큰 값들이 위치하고 있다. 지금까지의 설명이 퀵 정렬의 핵심연산이라 할 수 있다. 

이제 다음 단계는 다음과 같이 진행되어야 함을 알 수 있다.

퀵 정렬의 재귀적 구성

위 그림에서 보이듯이, 제자리를 찾은 5를 기준으로 왼쪽 영역과 오른쪽 영역을 대상으로 위에서 설명한 과정을 반복하게 된다. 그러면 왼쪽 영역의 피벗인 2와 오른쪽 영역의 피벗인 9가 제 자리를 찾을 것이다. 그리고 또 이어서, 제자리를 찾은 2를 기준으로 나뉘는 왼쪽 영역과 오른쪽 영역을 대상으로 제 자리를 찾은 9의 왼쪽과 오른쪽 영역을 대상으로, 퀵 정렬의 기본과정을 반복해 나간다.

그렇다면 이 과정은 언제까지 진행이 되어야 할까? left와 right가 각각 정렬대상의 시작과 끝을 의미하므로 다음 상황에 놓이게 될 때 더 이상 정렬할 대상이 없다는 의미가 된다.

left > right   // left와 right가 교차되는 상황.

#include <iostream>

using std::cout;
using std::cin;
using std::endl;


void Swap(int arr[], int idx1, int idx2) {
    int tmp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = tmp;
}


int Partition(int arr[], int left, int right) {
    int pivot = arr[left];
    int low = left + 1;
    int high = right;

    while (low <= high) {
        while (pivot >= arr[low] && low <= right) {
            low++;
        }
        while (pivot <= arr[high] && high >= (left+1)) {
            high--;
        }
        if (low <= high) {
            Swap(arr, low, high);
        }
    }
        
    Swap(arr, left, high);
    return high;
}


void QuickSort(int arr[], int left, int right) {
    if (left < right) {
        int pivot = Partition(arr, left, right);

        QuickSort(arr, left, pivot - 1);
        QuickSort(arr, pivot + 1, right);
    }
}


int main() {
    int arr[] = { 3, 2, 4, 1, 7, 6, 5 };
    //int arr[] = { 5, 5, 5, 5 };

    int n = sizeof(arr) / sizeof(int);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;

    QuickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;

    return 0;
}


/* 결과

3 2 4 1 7 6 5
1 2 3 4 5 6 7

*/

Partition 함수가 반환하는 값은 제 자리를 찾은 피벗의 인덱스 값이다. 그리고 이 값을 기준으로 정렬의 대상은 왼쪽 영역과 오른쪽 영역으로 나뉘게 된다. 때문에 함수의 이름이 Partition이라 해도 무리가 없다. 참고로 Partition은 퀵 정렬의 교과서적인 이름이다.

그리고 만약 다음과 같이 정의가 되어있었다면, 코드의 버그로 인해서 Partition 함수를 빠져 나오지 못할 것이다. 문제가 될 수 있는 부분은 다음과 같다.

int Partition(int arr[], int left, int right) {
  ...
  while(low <= high) {   // 항상 '참'일 수밖에 없는 상황이므로 무한루프
  {
    while(pivot > arr[low]) {   // 문제가 되는 부분
      low++;
    }
    
    while(pivot < arr[high]) {   // 문제가 되는 부분
      high--;
    }
    ...
  }
  ...
}

만약 5가 네 개인 배열을 정렬한다면 언제나 다음 식이 성립한다.

// [5, 5, 5, 5]

pivot == arr[low] == arr[high]

때문에 문제가 되는 지점의 while 조건은 항상 '거짓'이 되어 low는 증가의 기회를, high는 감소의 기회를 얻지 못한다. 따라서 바깥쪽의 while문을 빠져 나가지 못하는 문제가 발생한다. 때문에 다음과 같이 변경되어야 한다.

int Partition(int arr[], int left, int right) {
  ...
  while(low <= high) {   
  {
    while(pivot >= arr[low] && low <= right) {  
      low++;
    }
    
    while(pivot <= arr[high] && high >= (left + 1)) {  
      high--;
    }
    ...
  }
  ...
}

우선 > 연산자와 < 연산자를 각각 >= 연산자와 <= 연산자로 바꿔 놓았다. 때문에 5가 네 개 저장된 상황에서도 이 두 연산의 결과는 '참'이 되어 low와 high는 각각 증가와 감소의 기회를 얻고, 이로 인해서 low와 high는 결국 역전이 된다. 하지만 이것이 수정의 전부라면 low와 high가 배열의 정렬 범위를 넘어서는 문제가 발생한다. 따라서 경계검사를 위한 연산을 다음과 같이 추가한 것이다.

while(... && low <= right) {  
  low++;
}
    
while(... && high >= (left + 1)) {  
  high--;
}

위의 코드에서 left에 1을 더하여 high와 경계검사를 진행한 이유는 가장 왼쪽에 위치하는 피벗을 제외시키기 위함이다. 퀵 정렬을 구현하는데 있어서 너무도 쉽게 놓치는 부분이다. 때문에 [5, 5, 5, 5] 와 같은 배열을 대상으로 퀵 정렬을 진행하면 오류를 보이는 경우가 많다.

---

피벗(Pivot)의 선택

위의 내용에서는 가장 왼쪽에 위치한 데이터를 피벗으로 결정하였따. 하지만 전체 데이터를 기준으로 중간에 해당하는 값을 피벗으로 결정할 때 좋은 성능을 보인다. 그 이유는 다음과 같다.

피벗이 중간에 해당하는 값일 경우, 정렬대상은 균등하게 나뉜다.

아래의 예를 한번 살펴보자. 다음의 순서대로 저장되어 있는 배열이 있다고 가정해보자.

퀵 정렬 최악의 경우

그리고 피벗은 가장 왼쪽에 위치한 데이터로 결정한다고 더불어 가정하자. 그럼 위의 배열은 결코 둘로 나뉘지 않는다. 즉 1에서부터 시작해서 9의 앞에 있는 8까지 순서대로 피벗이 되어 정렬의 과정을 거치게 된다.

반면 다음과 같이 저장되어 있는 배열의 경우에는 그나마 적절한 분배가 이뤄져서 총 5개의 피벗이 정렬과정에서 선택된다.

퀵 정렬 괜찮은 경우

정렬의 과정에서 선택되는 피벗의 수는 앞서 정의한 Partition 함수의 호출횟수를 의미한다. 그리고 Partition 함수의 호출횟수가 많다는 것은 그만큼 데이터의 비교 및 이동의 횟수가 증가함을 뜻한다. 즉 좋은 성능을 보이려면 최대한 중간 값에 가까운 피벗이 지속적으로 선택되어야 한다. 그리고 이를 위해서 다음과 같은 방법이 사용된다.

정렬대상에서 세 개의 데이터를 추출한다. 그리고 그 중에서 중간 값에 해당하는 것을 피벗으로 선택한다.

단순히 생각해도 이 방법을 사용하면 중간에 가까운 값을 선택할 확률이 높아짐을 알 수 있다. 물론 이런 과정을 거치려면 그에 따른 연산이 필요하지만, 그래도 특정 위치의 값을 무조건 피벗으로 결정하는 것보다 좋은 성능을 보인다고 알려져 있다.

참고로 세 개의 데이터를 충출하는 방법에도 여러 가지가 있다. 단순히 맨 앞에 위치한 세 개의 데이터를 추출하는 방법도 있고, 조금 더 신경을 써서 가장 왼쪽과 가장 오른쪽, 그리고 중간에 위치한 데이터를 추출하는 방법도 있다. 중간 값에 가까운 피벗을 선택하는 방법은 지극히 상식적인 수준에서 결정된다.

다음의 예제는 적절한 중앙값을 선택했을 때와 그렇지 않았을 때를 비교하는 코드이다.

#include <iostream>

using std::cout;
using std::cin;
using std::endl;


void Swap(int arr[], int idx1, int idx2) {
    int tmp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = tmp;
}


int MedianOfThree(int arr[], int left, int right) {
    // index array
    int samples[3] = { left, (left + right) / 2, right };

    if (arr[samples[0]] > arr[samples[1]]) {
        Swap(samples, 0, 1);
    }
    if (arr[samples[1]] > arr[samples[2]]) {
        Swap(samples, 1, 2);
    }
    if (arr[samples[0]] > arr[samples[1]]) {
        Swap(samples, 0, 1);
    }

    return samples[1];
}


int Partition(int arr[], int left, int right) {
    //int pivot = arr[left];
    int pIdx = MedianOfThree(arr, left, right); // 중앙 값의 pivot 선택
    int pivot = arr[pIdx];

    int low = left + 1;
    int high = right;

    // 피벗을 가장 왼쪽으로 이동
    Swap(arr, left, pIdx);

    cout << "pivot: " << pivot << endl;

    while (low <= high) {
        while (pivot >= arr[low] && low <= right) {
            low++;
        }
        while (pivot <= arr[high] && high >= (left+1)) {
            high--;
        }
        if (low <= high) {
            Swap(arr, low, high);
        }
    }
        
    Swap(arr, left, high);
    return high;
}


void QuickSort(int arr[], int left, int right) {
    if (left < right) {
        int pivot = Partition(arr, left, right);

        QuickSort(arr, left, pivot - 1);
        QuickSort(arr, pivot + 1, right);
    }
}


int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };

    int n = sizeof(arr) / sizeof(int);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;

    QuickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;

    return 0;
}


/* 결과

// MedianOfThree 함수를 적용하여 적절한 중앙값을 이용했을 때
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
pivot: 8
pivot: 4
pivot: 2
pivot: 6
pivot: 12
pivot: 10
pivot: 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

// 무조건 left 인덱스를 이용했을 때
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
pivot: 1
pivot: 2
pivot: 3
pivot: 4
pivot: 5
pivot: 6
pivot: 7
pivot: 8
pivot: 9
pivot: 10
pivot: 11
pivot: 12
pivot: 13
pivot: 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

*/

결과를 보다시피 MedianOfThree 함수를 적용했을 때 정렬 연산이 절반으로 줄어든 것을 볼 수 있다.

int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };

이것은 최악의 상황을 연출한 것이다. 앞서 가장 왼쪽에 위치한 값을 무조건 피벗으로 결정하도록 구현했기 때문이다. 실제 실행결과를 보면 총 14개의 피벗이 선택되었음을 확인할 수 있다.

int MedianOfThree(int arr[], int left, int right) {
    // index array
    int samples[3] = { left, (left + right) / 2, right };

    if (arr[samples[0]] > arr[samples[1]]) {
        Swap(samples, 0, 1);
    }
    if (arr[samples[1]] > arr[samples[2]]) {
        Swap(samples, 1, 2);
    }
    if (arr[samples[0]] > arr[samples[1]]) {
        Swap(samples, 0, 1);
    }

    return samples[1];
}

위의 함수는 중간 값을 갖는 요소의 인덱스 값을 반환한다. 참고로 위의 함수에는 총 세 개의 if문이 포함되어 있는데, 이는 버블 정렬을 위한 것이다. 세 개의 데이터를 정렬하기 위해서는 세 개의 if문이면 충분하기 때문에 굳이 for문을 사용하지 않았다.

중간 값을 구하는 것이 해결되었으니 이것을 토대로 퀵 정렬을 진행할 수 있도록 해야한다. 이것은 다음과 같이 정리할 수 있다.

"피벗을 선택했다면, 이를 가장 왼쪽에 있는 데이터와 교환한다. 즉 피벗을 가장 왼쪽으로 이동시킨다."

위의 퀵 정렬 코드는 피벗이 가장 왼쪽에 위치하는 상황에서 동작한다. 따라서 다음과 같이 코드를 추가 및 변경해야한다.

int pIdx = MedianOfThree(arr, left, right);
int pivot = arr[pIdx];
...

// 피벗을 가장 왼쪽으로 이동
Swap(arr, left, pIdx);

이렇게 구현을 완료하고 배열을 대상으로 정렬을 진행하면, 선택되는 피벗의 수가 반으로 줄은 것을 확인할 수 있다.

---

퀵 정렬(Quick Sort) : 성능평가

퀵 정렬의 비교연산 횟수를 위해 다음의 그림을 살펴보자.

위 그림에서 보이듯이 피벗이 결정되면 low는 오른쪽으로 high는 왼쪽으로 이동을 시작한다. 그리고 그 이동은 low와 high가 역절될 때까지 진행된다. 그런데 이동의 과정에서 피벗과의 비교를 매번 수반하므로, 하나의 피벗이 제 자리를 찾아가는 과정에서 발생하는 비교연산의 횟수는, 데이터의 수에 해당하는 n이라 할 수 있다.

물론 피벗으로 인해 n보다 하나 적은 수의 비교연산이 이뤄지지만 이는 무시할 수 있따. 그리고 이러한 비교연산의 횟수는 다음과 같이 정렬의 범위가 분할된 상태에서도 마찬가지이다.

위 그림에서와 같이 반으로 나뉜 상태에서 각각의 low와 high가 각각의 방향으로 이동을 하는데, 이때에도 비교연산이 진행이 되니, 비교연산의 횟수는 데이터의 수에 해당하는 n이라 할 수 있다. 물론 피벗과 이미 자리를 잡은 숫자 5로 인해서, 이는 실제 비교연산의 횟수와 차이가 있지만, 데이터의 수가 많은 경우를 가정하여 이 역시 무시할 수 있따.

그럼 이제 분할이 몇 단계에 걸쳐서 이뤄지는가에 관심을 두어야 한다. 이를 위해서 총 31개의 데이터를 대상으로 퀵 정렬을 진행한다고 가정해보자. 피벗이 항상 중간 값으로 결정되는 이상적인 경우를 가정하면, 처음에 15개씩 둘로 나뉠 것이며, 이어서 이들 각각은 다시 7개씩 둘로 나뉠 것이다. 즉 이러한 나뉨의 과정은 다음과 같이 진행이 된다.

• 31개의 데이터는 15개씩 둘로 나뉘어 총 2 조각이 된다.    -> 1차 나뉨.
• 이어서 각각 7개씩 둘로 나뉘어 총 4 조각이 된다.    -> 2차 나뉨.
• 이어서 각각 3개씩 둘로 나뉘어 총 8 조각이 된다.    -> 3차 나뉨.
• 이어서 각각 1개씩 둘로 나뉘어 총 16 조각이 된다.    -> 4차 나뉨.

둘로 나뉘는 횟수를 k라 할 때, 데이터의 수 n과의 관계는 다음과 같다.

k = log2n

따라서 퀵 정렬에서의 비교연산 횟수는 nlog2n이고, 이로 인해 비교연산의 빅-오는 다음과 같다고 결론 내릴 수 있다.

O(nlog2n)

그런데 이런 결론을 보고 아니라고 생각할 수도 있다. 왜냐하면 위의 결론은 최악의 경우가 아닌 최선의 경우라서 말이다. 하지만 퀵 정렬의 경우에는 약간의 예외를 둔다. 이유는 위에서 말한 것처럼 '중간에 가까운 피벗을 선택하는 방법'을 적용함으로써, 늘 최선의 경우를 보이는 것은 아니지만 최선의 경우에 가까운 성능을 평균적으로 보이기 때문이다. 따라서 이는 최선의 경우가 아닌 평균의 경우에 대한 빅-오로 보기도 한다.

그렇다면 최악의 경우에 대한 빅-오를 계산해보자. 위의 그림 중 배열의 상태가 [1(pivot), 2, 3 , 4, 5, ...] 이렇게 된 배열이 있다. 이 상태는 데이터들이 이미 정렬되어 있는 상태인데다가 피벗이 가장 작은 값으로 결정되는 상황에서는, 둘로 나뉘는 횟수 k와 데이터의 수 n과의 관계가 다음과 같다.

k = n

따라서 최악의 경우의 비교연산 횟수에 대한 빅-오는 다음과 같다.

O(n2)

이는 단순한 정렬 알고리즘에서나 볼 수 있는 빅-오이다. 하지만 이 결과를 기준으로 퀵 정렬을 평가하지 않는다. 실제로 퀵 정렬은 O(nlog2n)의 복잡도를 갖는 다른 정렬 알고리즘과 비교했을 때에도 평균적으로 제일 빠른 것으로 알려져 있다. 그리고 그 이유를 퀵 정렬의 데이터 이동횟수가 상대적으로 적고, 병합 정렬과 같이 별도의 메모리 공간을 요구하지 않는다는 사실에서 찾을 수 있다.

정리하면, 퀵 정렬은 시간 복잡도가 O(nlog2n)인 알고리즘이다. 하지만 데이터의 이동이 데이터의 비교에 비해 현저히 적게 일어나고, 별도의 메모리 공간을 요구하지 않으므로 동일한 빅-오를 갖는 다른 정렬 알고리즘 중에서 평균적으로 가장 빠른 정렬속도를 보이는 알고리즘이다.