분할정복을 활용한 Quick Sort 구현 (C++)

분할 정복을 활용한 Quick Sort 구현

접근법

Quick Sort는 분할 정복을 활용한 대표적인 정렬 알고리즘입니다. 그래서 Quick Sort를 직접 구현해 보는 것은 분할 정복을 이해하는데 많은 도움이 될 수 있습니다. Quick Sort의 원리는 다음과 같습니다. Quick Sort를 구현하기 위해서는 left, right, pivot을 설정해야 합니다. left는 배열의 첫 원소를 가리키고, right는 배열의 마지막 원소를 가리킵니다. pivot은 Quick Sort를 구현하는 방법에 따라 다르긴 하지만, 여기서는 배열의 중앙값을 가리킵니다.

• 배열의 중앙값을 pivot으로 정한다.
• left가 right보다 작거나 같다면 아래의 행동을 반복한다.
  • left는 가장 왼쪽에서 오른쪽 방향으로 pivot 보다 크거나 같은 수를 탐색할 때까지 이동한다.
  • right는 가장 오른쪽에서 왼쪽 방향으로 pivot 보다 작거나 같은 수를 탐색할 때까지 이동한다.
  • left <= right 라면 둘을 swap 하고 left는 오른쪽으로 right는 왼쪽으로 한 칸씩 이동한다.

위 과정을 거친다면 start 부터 right 범위까지는 pivot보다 작은 수들이, left부터 right범위 까지는 , pivot 오른쪽에는 pivot 보다 큰 수들이 모이게 됩니다. 그래서 이들을 대상으로 다시 Quick Sort를 호출하여 계속 정렬해 나갑니다.

 

Quick Sort의 시간복잡도는 탐색 대상이 되는 전체 노드 개수 \(N\)과 탐색 횟수에 해당하는 재귀 호출의 깊이에 비례합니다. 재귀 호출의 깊이는 mid 값이 항상 대상 배열의 중앙값이라면 \(\mbox{log}N\)이지만 최악의 경우(이미 정렬이 되어있는 경우)\(N\)이 될 수도 있습니다. 따라서 Quick sort의 시간 복잡도는 평균적으로는 \(\theta(N\mbox{log}N)\)이지만 최악의 경우 \(O(N^2)\)가 됩니다. 하지만 무작위로 데이터가 주어졌는데 정렬되어 있을 경우는 \(2/n!\)일 확률이기 때문에 \(O(N^2)\)성능이 나올 가능성이 낮습니다. 그래서 최악의 경우 \(O(N^2)\) 시간 복잡도이지만, 일반적으로는 \(\theta(N\mbox{log}N)\)성능을 보여 다른 정렬 알고리즘보다는 빠르다는 특징이 있습니다.

구현

아래와 같이 코드로 구현할 수 있습니다. BOJ11004번 문제를 통해서 정확성 및 성능 테스트를 진행하였습니다.

#include <iostream>
#include <array>

#define endl '\n'
using namespace std;
const int MAX_LEN = 5'000'000;
void Swap(array<int, MAX_LEN>& arr, const int left, const int right)
{
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

void QuickSort(array<int, MAX_LEN>& arr, const int start, const int end)
{
    if (end - start <= 0) return;

    int left = start; 
    int right = end;
    int mid = (start + end) / 2;
    int pivot = arr[mid];

    // 엇갈릴때 까지 실행. (같은 곳을 가리키고 있더라도) 
    while (left <= right)
    {
        while (pivot > arr[left]) left++;
        while (pivot < arr[right]) right--;

        if (left <= right)
        {
            Swap(arr, left, right);
            left++;
            right--;
        }
    }

    QuickSort(arr, start, right);
    QuickSort(arr, left, end);
}

int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N, K; // N(1 ≤ N ≤ 5,000,000), K (1 ≤ K ≤ N)
    cin >> N >> K;

    array<int, MAX_LEN> arr;
    for (int i = 0; i < N; ++i)
    {
        cin >> arr[i];
    }

    QuickSort(arr, 0, N - 1);

    cout << arr[K-1];

    return 0;
}