[알고리즘] 퀵 정렬 (Quick Sort)

 🔎 퀵 정렬이란?

퀵 정렬은 분할 정복 알고리즘으로 분류되지만, 사실은 정복 후 분할하는 과정이다.

또한, 부분 문제의 수는 2개로, 각 부분 문제의 크기는 일정하지 않다.

 

💡 정렬 과정

퀵 정렬은 피봇(pivot)이라고 하는 배열의 한 원소(숫자)를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고, 피봇을 그 가운데 위치시킨다. 

그다음 분할된 부분 문제들에 대해서도 똑같은 과정을 순환적으로 반복한다.

 

⚠️ 주의할 점

이때 피봇은 분할된 왼편이나 오른편, 그 어느 부분에도 해당되지 않는다. 

 

🔽 그림으로 이해하기

위 그림을 보면 60이 피봇으로 선정되어, 60보다 작은 숫자들은 왼편으로, 60보다 큰 숫자들은 오른편으로 이동하였다.

 

이제 퀵 정렬 알고리즘에 대해 알아보자

🔎 퀵 정렬 알고리즘

QuickSort(A, left, right)
입력: 배열 A[left] ~ A[right]
출력: 정렬된 배열 A[left] ~ A[right]
if (left < right) {
	피봇을 A[left] ~ A[right] 중에서 선택하고, 피봇을 A[left]와 자리를 바꾼 후, 
    	피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자들은 A[left] ~ A[p-1]로 옮기고, 
    	피봇보다 큰 숫자들은 A[p+1] ~ A[right]로 옮기며, 피봇은 A[p]에 놓는다.
    	QuickSort(A, left, p-1)		// 피봇보다 작은 그룹
    	QuickSort(A, p+1, right)	// 피봇보다 큰 그룹
}

• Line 4 : 
  • 배열 A의 가장 왼쪽 원소와 오른쪽 원소의 인덱스를 비교하여 오른쪽 인덱스가 더 큰 경우만 다음을 수행하도록 한다.
  • 만약 `left == right` 이라면 더 이상 분할할 수 없는 크기, 즉 원소의 개수가 1이므로 그대로 호출을 마친다.
• Line 5~7 : 
  • 피봇을 정하여 배열의 가장 왼편, 즉 `A[left]` 에 위치시킨다.
  • 배열 `A[left+1] ~ A[right]`의 원소들을 피봇과 각각 비교하여 두 그룹으로 분할하고, 피봇을 그 가운데 위치시킨다.
    • `A[left] ~ A[p-1]` : 피봇보다 작은 그룹
    • `A[p+1] ~ A[right]` : 피봇보다 큰 그룹
    • `A[p]` : 피봇의 위치
• Line 8~9 :
  • 분할된 두 그룹을 각각 순환 호출한다.

🔽 예제로 알아보기

`QuickSort(A, 0, 11)` 을 호출하였다.

`A[6]=8`을 피봇이라고 하자.

피봇을 가장 왼쪽으로 이동시킨다.

그다음 피봇보다 큰 수와 작은 수를 위와 같이 이동시킨다.

마지막으로 피봇을 `A[4]`로 옮기기 위해 `A[0]`과 교환한다.

`A[4]`로 이동시키는 이유는 `A[4]`의 숫자 2가 피봇인 8보다 작으면서 가장 오른쪽에 위치하고 있기 때문이다.

 

이후, `QuickSort(A,0,4-1)= QuickSort(A,0,3)`과 `QuickSort(A,4+1,11)= QuickSort(A,5,11)`이 호출되고 이후 배열이 크기가 1이 될 때까지 위 과정이 반복된다.

 🔎 퀵 정렬의 성능

퀵 정렬의 성능은 피봇 선택이 좌우한다.

✅ 최악의 경우

피봇으로 가장 작은 숫자, 또는 가장 큰 숫자가 선택되면 분할이 한 부분으로 치우치게 된다.

 

🔽 피봇으로 '가장 작은 숫자'가 선택되는 경우를 알아보자.

• 피봇이 1일 때 : 8회 비교
• 피봇이 9일 때 : 7회 비교
• 피봇이 11일 때 : 6회 비교

따라서 총 비교 횟수는 $8+7+6+⋯+1=36$이다.

만약 입력 크기가 `n`이라면, 퀵 정렬의 최악 경우 시간 복잡도는 $(n-1)+(n-2)+(n-3)+⋯+2+1= \frac {n(n-1)}{2}=O(n^2)$이다.

 

✅ 최선의 경우

그렇다면, 최선의 경우는 어떤 분할일까?

'균형'을 이루면서 분할될 때, 즉 항상 $1/2$씩 분할되는 경우가 최선의 경우가 될 것이다.

 

피봇이 입력을 2등분으로 분할하는 경우는 입력의 중앙값이 피봇으로 선정되는 경우이다.

 

🔽 중앙값이 피봇으로 선정되는 경우

각 층에서는 각각의 원소가 각 부분의 피봇과 1회씩 비교된다.

따라서 비교 횟수는 $O(n)$이다.

그러므로 총 비교 횟수는 $O(n) ⨉$(층수)$=O(n)⨉(\log_{2}{n})$이다.

 

층 수가 $\log_{2}{n}$인 이유는 $\frac{n}{2^k}=1$ 일 때 $k=log_{2}{n}$이기 때문이다.

 

결과적으로 퀵 정렬의 최선 경우 시간복잡도는 $O(n\log_{2}{n})$이다.

 

✅ 평균 경우

피봇을 항상 랜덤하게 선정한다고 가정하면, 퀵 정렬의 평균 경우 시간복잡도를 계산할 수 있다.

이때의 시간복잡도 역시 최선 경우와 동일하게 $O(n\log_{2}{n})$ 이다.

 

🔎 피봇 선정 방법

피봇을 선정하는 일반적인 방법은 다음과 같다.

• 랜덤 하게 선정하는 방법
• 3 숫자의 중앙값으로 선정하는 방법 (Median of Three) : 가장 왼쪽 숫자, 중간 숫자, 가장 오른쪽 숫자 중에서 중아값으로 피봇 선정

31, 1, 26 중에서 중앙값인 26을 피봇으로 선정한다.

• 중앙값들 중의 중앙값 (Median of Medians) : 입력을 3 등분하여 각 부분에서 3 숫자의 중앙값을 찾아서 3개의 중앙값에서 중앙값을 피봇으로 선정

✅ 퀵 정렬과 삽입 정렬의 혼합 사용

입력의 크기가 매우 클 때, 퀵 정렬의 성능을 향상하기 위해 삽입 정렬을 동시에 사용하기도 한다.

입력의 크기가 작을 때에는 퀵 정렬이 삽입 정렬보다 빠르지만은 않기 때문에, 입력이 크기가 작아지면(예: 입력 크기가 25~50이 되면) 분할을 중단하고 삽입 정렬을 수행하는 것이다.

 

🔎 활용

퀵 정렬은 입력의 크기가 클 때 좋은 성능을 보인다.

생물 정보 공학(Bioinformatics)에서 특정 유전자를 효율적으로 찾는 데 접미 배열(suffix array)과 함께 퀵 정렬이 활용된다.

 

🔎 퀵 정렬 구현

C++을 사용하여 퀵 정렬을 구현하였다.

#include <iostream>
#include <vector>
#include <random>

using namespace std;

void QuickSort(vector<int> &arr, int left, int right)
{
    // 재귀 종료 조건 (배열 크기가 1인 경우)
    if (left >= right)
        return;

    // 랜덤 pivot 선택
    random_device rd;                                // 하드웨어 엔트로피 기반 난수 생성
    mt19937 gen(rd());                               // Mersenne Twister 엔진 사용
    uniform_int_distribution<int> dist(left, right); // 균등 분포
    int pivotIndex = dist(gen);

    // 피봇을 배열의 왼쪽으로 이동
    swap(arr[pivotIndex], arr[left]);
    int pivot = arr[left];
    int leftPartition = left + 1;
    int rightPartition = right;

    // 배열을 순회하며 비교
    while (leftPartition < rightPartition)
    {
        if (arr.at(leftPartition) > pivot && arr.at(rightPartition) < pivot)
        {
            swap(arr[leftPartition], arr[rightPartition]);
            leftPartition++;
            rightPartition--;
        }
        else if (arr.at(leftPartition) < pivot && arr.at(rightPartition) < pivot)
        {
            leftPartition++;
        }
        else if (arr.at(leftPartition) > pivot && arr.at(rightPartition) > pivot)
        {
            rightPartition--;
        }
        else
        {
            leftPartition++;
            rightPartition--;
        }
    }

    if (arr[rightPartition] <= pivot)
    {
        swap(arr[rightPartition], arr[left]);
        pivotIndex = rightPartition;
    }
    else
    {
        swap(arr[rightPartition - 1], arr[left]);
        pivotIndex = rightPartition - 1;
    }

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

int main()
{
    // 배열 A
    vector<int> arr = {6, 3, 11, 9, 12, 2, 8, 15, 18, 10, 7, 14};

    // 정렬 전 출력
    cout << "정렬 전 : ";
    for (int v : arr)
    {
        cout << v << " ";
    }
    cout << endl;

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

    // 정렬 후 출력
    cout << "정렬 후 : ";
    for (int v : arr)
    {
        cout << v << " ";
    }
    cout << endl;

    return 0;
}

 

📌 결과 출력

정렬 전 : 6 3 11 9 12 2 8 15 18 10 7 14 
정렬 후 : 2 3 6 7 8 9 10 11 12 14 15 18