퀵 정렬 (Quick Sort)

• 분할 정복 알고리즘이지만 사실은 정복하고 분할한다.

• 입력의 크기가 클 경우 가장 좋은 성능을 보이는 정렬 알고리즘이다.

  • 생물 정보 공학(Bioinformatics)에서 특정 유전자를 찾을 때 접미 배열(Suffix Array)와 함께 사용된다고 한다.

• 피벗(pivot) 숫자를 기준으로 피벗보다 작은 숫자를 왼쪽으로, 큰 숫자를 오른쪽으로 이동시킨 다음 피벗을 사이에 놓고 분할하는 방식이다.

  • 피벗은 부분문제에 포함되지 않는다.

  pseudo code

  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);
    }
  }

  • 11, 9, 2, 12, 8, 15, 18, 10의 정렬 예제

    • 피벗을 (right - left) / 2로 잡았다.

    • 먼저 피벗을 맨 왼쪽의 값과 바꾼다.

    • 반복문

      • high는 left + 1부터 시작하여 피벗의 값보다 큰 값이 나올 때까지 우측으로 이동한다.

        • 피벗의 값과 같은 값은 패스하는데, 이는 부분문제에서 해결 가능하기 때문이다.

      • low는 right부터 시작하여 피벗의 값보다 작은 값이 나올 때까지 좌측으로 이동한다.

      • 인덱스 low가 high보다 낮으면 정복이 끝났으므로 피벗과 low를 교체하고 부분문제로 분할한다.

      • 그렇지 않으면 low의 값과 high의 값을 바꾼다.

      

시간 복잡도

• 최악 경우 시간 복잡도는 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);
}

합병 정렬 (Merge Sort)

• 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘

• 연결 리스트에 있는 데이터를 정렬할 때 퀵 정렬이나 힙 정렬보다 훨씬 효율적이라고 한다.

  pseudo code

  MergeSort(int arr[], int p, int q)
  {
    if (p < q)
    {
      int k = (p + q) / 2;
      MergeSort(arr, p, k);
      MergeSort(arr, k + 1, q);
      arr[p] ~ arr[k]와 arr[k + 1] ~ arr[q]를 합병한다.
    }
  }

  

시간 복잡도

• 분할하는 부분

  • 배열의 중간 인덱스 계산과 재귀 호출 2번으로 O(1) 시간이 걸린다.

• 합병하는 부분

  • 두 정렬된 배열 A, B의 크기가 각각 n과 m이고 이를 합병하여 새로운 배열 C를 만드는 부분

    • (n + m - 1)번의 비교를 통해 배열 C를 채우므로 시간 복잡도는 O(n + m)이다.

  • 층 별 비교

    • 각 층에서 수행되는 비교 횟수는 분할된 크기 * 분할된 개수로, 항상 O(n)이다.

    • 층 수는 log₂n이다.

    • 즉, 모든 층에서 수행되는 비교 횟수는 O(nlog₂n)이다.

  • 각 층에서 비교 후에 새로운 배열로 이동시키는 과정의 시간복잡도는 O(nlog₂n)이다.

• 모두 더하면 O(nlog₂n)이다.

공간 복잡도

• 입력과 같은 크기의 공간이 별도로 필요하므로 O(n)이다.

C++ 코드

#include <iostream>
#include <vector>

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

void Merge(std::vector<int>& arr, int low, int mid, int high)
{
    int i = low;
    int j = mid + 1;
    int temp_idx = low;
    static std::vector<int> temp(arr);

    while ((i <= mid) && (j <= high))
    {
        if (arr[i] < arr[j])
            temp[temp_idx++] = arr[i++];
        else
            temp[temp_idx++] = arr[j++];
    }
    while (i <= mid)
        temp[temp_idx++] = arr[i++];
    while (j <= high)
        temp[temp_idx++] = arr[j++];

    while (low <= high)
    {
        arr[low] = temp[low];
        low++;
    }
}

void MergeSort(std::vector<int>& arr, int low, int high)
{
    if (low == high)
        return ;

    int mid = (low + high) / 2;

    MergeSort(arr, low, mid);
    MergeSort(arr, mid + 1, high);
    Merge(arr, low, mid, high);
}

int main()
{
    using namespace std;

    vector<int> arr = { 37, 10, 22, 30, 35, 13, 25, 24 };

    PrintElements(arr);
    MergeSort(arr, 0, arr.size() - 1);
    PrintElements(arr);
}

/* stdout
37 10 22 30 35 13 25 24 
10 13 22 24 25 30 35 37
*/

참고

• 알기쉬운 알고리즘 (양성봉 저, 생능 출판)