[알고리즘 알아보기] QuickSort

개요

QuickSort는 Tony Hoare가 1959년에 고안한 알고리즘입니다.

QuickSort는 대규모로 분포된 랜덤 데이터에서 MergeSort, HeapSort보다 빠를 수 있습니다.

 

평균적으로 O(nlogn)의 복잡도이며 최악의 경우에는 O(n^2)의 복잡도를 가집니다.

Divide And Conquer(이하 D&C)를 기반으로 이루어집니다.

퀵소트 이전과 이후

 

---

Quicksort의 특징

Quicksort는 pivot을 중심으로 두 개의 하위 배열로 분할해 다시 Quicksort를 실행하는 재귀적인 정렬을 실행합니다.

그리고 재귀로 인해 쌓이는 스택메모리를 제외하면 배열 자체는 그대로 사용하기 때문에 CPU캐시 히트율이 높은 방식이라고 볼 수 있습니다.

 

이후 진행과정을 보면 아시겠지만 Quicksort는 불안정 정렬이기 때문에 같은 값에 대해 정렬 전과 같은 순서를 보장하지 않습니다.

---

Quicksort 알고리즘

Quicksort를 하는 방법은 피벗을 고르는 방식에 따라 갈립니다.

이번에는 lomuto, hoare, 방법에 대해 알아보겠습니다.

---

lomuto

전체 배열에서 마지막 인덱스를 피벗으로 사용합니다.

그리고 두개의 포인터를 이동시키며 swap합니다.

int LomutoPartition(vector<int>& values, int left, int right)
{
    int pivot = values[right];
    int smaller = left - 1;

    for (int current = left; current < right; ++current)
    {
        if (values[current] <= pivot)
        {
            ++smaller;
            swap(values[smaller], values[current]);
        }
    }

    swap(values[smaller + 1], values[right]);
    return smaller + 1;
}

void QuickSortLomuto(vector<int>& values, int left, int right)
{
    if (left >= right)
        return;

    int pivot = LomutoPartition(values, left, right);
    QuickSortLomuto(values, left, pivot - 1);
    QuickSortLomuto(values, pivot + 1, right);
}

기본적으로 우측 포인터는 이동하며, pivot보다 작은 경우 좌측 포인터와 교환하며 진행합니다.

이후 피벗을 위치시킨 뒤 하위 배열에 대해 재귀를 실시합니다.

---

hoare

hoare방식은 두개의 포인터가 양끝에서 움직입니다.

기본적으로 왼쪽의 포인터 i는 pivot보다 큰 값을 찾으려고 움직이며, 오른쪽의 포인터 j는 pivot보다 작은 값을 찾으려고 움직입니다. 그리고 교환합니다.

int HoarePartition(vector<int>& values, int left, int right)
{
    int pivot = values[left + (right - left) / 2];
    int i = left - 1;
    int j = right + 1;

    while (true)
    {
        do
        {
            ++i;
        } while (values[i] < pivot);

        do
        {
            --j;
        } while (values[j] > pivot);

        if (i >= j)
            return j;

        swap(values[i], values[j]);
    }
}

void QuickSortHoare(vector<int>& values, int left, int right)
{
    if (left >= right)
        return;

    int pivot = HoarePartition(values, left, right);
    QuickSortHoare(values, left, pivot);
    QuickSortHoare(values, pivot + 1, right);
}

이 방법에 차이가 있다면,  pivot의 위치가 딱히 고정될 필요가 없다는 것입니다.

---

추가적으로 3-way partition방법도 있습니다. 이는 피벗을 처음 선정할 때 배열의 맨 왼쪽, 맨 오른쪽 그리고 중간 인덱스의 값 중 중간 값을 피벗으로 설정하는 방법입니다.

 

이는 퀵소트가 이미 정렬된 경우 맨 마지막 혹은 맨 처음을 피벗으로 설정하면 하위 배열의 크기가 커지기 때문에, 하위 배열의 크기를 줄이기 위한 시도라고 볼 수 있습니다.

 

---

사진에 부여된 인덱스를 퀵소트를 통해 정렬해보았습니다.

 

           Name  |     Average  |        Min   |        Max   |      Call |
---------------------------------------------------------------------------
Lomuto QuickSort |  14636.8910 | 13787.4000 | 17482.0000 |      100
Hoare QuickSort |  13303.0910 | 12559.3000 | 15168.7000 |      100

또한 Lomuto 방식과 Hoare방식으로 랜덤한 데이터를 통해 성능을 측정해보았습니다.

Hoare방식이 양쪽의 원소를 교환하기 때문에 더욱 효율적인 것으로 볼 수 있습니다.