퀵 정렬 (Quick Sort)

퀵 정렬 (Quick Sort)

• 분할 정복 알고리즘이지만 사실은 정복하고 분할한다.
• 입력의 크기가 클 경우 가장 좋은 성능을 보이는 정렬 알고리즘이다.
  • 생물 정보 공학(Bioinformatics)에서 특정 유전자를 찾을 때 접미 배열(Suffix Array)와 함께 사용된다고 한다.
• 피벗(pivot) 숫자를 기준으로 피벗보다 작은 숫자를 왼쪽으로, 큰 숫자를 오른쪽으로 이동시킨 다음 피벗을 사이에 놓고 분할하는 방식이다.
  • 피벗은 부분문제에 포함되지 않는다.
  pseudo code
  • 11, 9, 2, 12, 8, 15, 18, 10의 정렬 예제
    • 피벗을 (right - left) / 2로 잡았다.
    • 먼저 피벗을 맨 왼쪽의 값과 바꾼다.
    • 반복문
      • high는 left + 1부터 시작하여 피벗의 값보다 큰 값이 나올 때까지 우측으로 이동한다.
        • 피벗의 값과 같은 값은 패스하는데, 이는 부분문제에서 해결 가능하기 때문이다.
      • low는 right부터 시작하여 피벗의 값보다 작은 값이 나올 때까지 좌측으로 이동한다.
      • 인덱스 low가 high보다 낮으면 정복이 끝났으므로 피벗과 low를 교체하고 부분문제로 분할한다.
      • 그렇지 않으면 low의 값과 high의 값을 바꾼다.
      
• QuickSort(int *arr, int left, int right) { if (left < right) { 피벗을 arr[left] ~ arr[right] 중에 선택한다. 피벗을 arr[left]와 자리를 바꾼다. 피벗보다 작은 숫자의 인덱스를 low, 피벗보다 큰 숫자의 인덱스를 high라고 하자. low = right, high = left + 1부터 시작하여 가운데쪽으로 이동하며 검사한다. arr[low]와 arr[high]를 비교하여 작은 수는 arr[left + 1] ~ arr[p]로, 큰 숫자는 arr[p + 1] ~ arr[right]로 서로 맞교환해가며 진행한다. low < high일 때는 정복이 끝난 것이므로 arr[left]와 arr[low]의 값을 바꾼 뒤 분할한다. QuickSort(arr, left, p - 1); QuickSort(arr, p + 1, right); } }

---

시간 복잡도

• 최악 경우 시간 복잡도는 O(n²)이다.
  • 예를 들면 피벗이 계속해서 가장 작은 값만 선택될 경우, 부분문제로 들어가도 입력의 크기만 1씩 줄어들 뿐 문제가 분할되지 않는다.
  • 입력의 크기가 n일 때 비교하는 횟수를 보면 (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2 = O(n²) 이다.
• 최선의 경우 시간 복잡도는 O(nlog₂n)이다.
  • 피벗이 계속해서 입력의 중앙값으로 선택되면, 항상 1/2로 분할되고 층마다 n번씩 비교를 하게된다.
  • 총 비교 횟수 = 층 수 * 각 층마다의 비교 횟수 = log₂n * O(n) = O(nlog₂n)

---

피벗 선정 방법

• 랜덤하게 선정하는 방법
• 3 숫자의 중앙값으로 선정하는 방법
  • 가장 왼쪽, 중앙, 가장 오른쪽의 값 중에 2번째의 값으로 피벗을 설정한다.

---

성능 관련 팁

• 입력의 크기가 매우 클 경우, 삽입 정렬을 같이 사용한다.
  • 입력의 크기가 작으면 퀵 정렬은 재귀 호출이기에 삽입 정렬보다 느리므로, 이 점을 보완한다.

---

코드

#include <iostream>
#include <vector>

void PrintArr(const std::vector<int>& arr)
{
    for (auto& e : arr)
        std::cout << e << ' ';
    std::cout << std::endl;
}

void QuickSort(std::vector<int>& arr, int left, int right)
{
    if (left >= right)
        return ;

    int    pivot = (left + right) / 2;
    int    high = left + 1;
    int    low = right;

    std::swap(arr[pivot], arr[left]);
    while (high <= low)
    {
        while ((high <= right) && (arr[high] <= arr[left]))
            high++;
        while ((low > left) && (arr[low] >= arr[left]))
            low--;
        if ((high > right) || (low == left) || (high >= low))
            break;
        std::swap(arr[high], arr[low]);
    }
    std::swap(arr[left], arr[low]);

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

int main()
{
    std::vector<int> arr{ 11, 9, 2, 12, 8, 15, 18, 10 };

    PrintArr(arr);
    QuickSort(arr, 0, arr.size() - 1);
    PrintArr(arr);
}