퀵 정렬(Quick Sort) 구현

08 Apr 2018

Reading time ~2 minutes

퀵 정렬

이 정렬은 정렬 중에서도 가장 빠른 정렬 알고리즘이다.(이름값 함)

퀵 정렬의 과정은 아래와 같다.

정렬해야 하는 임의의 배열 arr이 있고, 이 배열의 길이가 length라고 하자.
Partition(low,high)이란 함수가 있다. 이 함수의 역할은 다음과 같다.
- 오름차순 정렬을 한다고 가정했을 때 arr[low](혹은 arr[(low+high)/2])를 기준으로 이 값보다 작은 원소는 이 배열의 왼쪽에, 큰 원소는 이 배열의 오른쪽에 두는 작업을 수행하고, 이 기준값이 존재하는 인덱스 값(즉, 배열의 위치 인덱스)을 반환한다.
- 쉽게 말해 Partition 함수는 arr[low~high]의 원소 중 하나를 임의로 선택해 그 값을 기준으로 이보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 둬서 기준값의 위치 인덱스를 반환하는 함수인 것이다.
이번엔 QuickSort(low, high)를 정의해보자.
- Partition(low,high)의 반환값을 j라고 해보자. j보다 앞쪽에 있는 배열의 원소들과, j보다 뒤쪽에 있는 배열의 원소들을 이용해 배열을 더 이상 쪼갤 수 없을 때까지 분할 정복한다. 즉,QuickSort(low, j-1)와 QuickSort(j+1, high)을 low >= high 일 때까지 수행한다.

Complexity

시간 복잡도: O(NlogN) 이지만 최악의 경우 O(N^2)이다. 합병 정렬과 시간복잡도가 같지만, 평균적으로 더 빠른 속도를 지닌다.
공간 복잡도: O(N)

구현

#include <iostream>

using namespace std;

int a[] = {1,2,5,6,3,4,8,7,9,99999999};

int Partition(int m, int p)
{
    int v = a[m];
    // j가 p+1부터 시작하는 이유는 가장 처음에 v와 비교할 때 j를 감소시키고 시작하기 때문이다.
    // i도 마찬가지라서, a[m+1]부터 비교하게 된다.
    int i = m, j = p+1;

    // i와 j가 교차될 때까지 진행한다.
    while(i < j)
    {
        // 오른쪽으로 이동하며 기준보다 큰 a[i]를 찾는다.(a[i]가 v보다 작을 때만 이동 시키므로, 큰 a[i]를 찾겠다는 의미이다.)
        while(a[++i] < v);
        // 왼쪽으로 이동하며 기준보다 작은 a[j]를 찾는다.(a[j]가 v보다 클 경우에만 이동 시키므로, 작은 a[j]를 찾겠다는 의미이다.)
        while(a[--j] > v);

        if(i < j)
            swap(a[i], a[j]); // 기준보다 작은 원소를 왼쪽에, 기준보다 큰 원소를 오른쪽에 밀어넣는다.
    }
    // a[j]는 a[m](기준)보다 무조건 작은 값이고, a[j] 뒤에는 반드시 a[m]보다 큰 값을 가지고 있다. 때문에 중간 값인 a[m]을 a[j]와 바꿔준다.
    swap(a[m], a[j]);

    return j;
}
void QuickSort(int p, int q)
{
    if(p < q)
    {
        int j = Partition(p, q);
        QuickSort(p, j-1);
        QuickSort(j+1, q);
    }
}
int main()
{
    QuickSort(0, 8);
    for(int i=0;i<9;i++)
        cout<<a[i]<<" ";
    cout<<endl;

    return 0;
}

소스코드에 대한 상세 설명은 주석을 참고. 여기서 배열 a의 맨 마지막 부분에 매우 큰 값을 넣은 이유는, while(a[++i] < v);와 while(a[--j] > v);가 무한 루프에 빠지지 않게 하기 위해서다. while문 조건에 && i<j 같은 조건을 넣을 수도 있지만, 배열의 맨 마지막 부분에 큰 값을 두는 것이 더 효율적이다.

공간 복잡도가 개선된 퀵 정렬(스택 사용)

퀵 정렬에서 공간 복잡도를 더 개선할 수 있는 방법이 있다. 정복하는 순서를 분할된 배열 중 더 작은 크기의 배열을 먼저 정복하는 것이다. 자세한 설명은 코드의 주석을 보자.

void QuickSort(int p, int q)
{
    stack<int> s;
    do
    {
        // p와 q가 교차될 때까지 진행한다.
        while(p < q)
        {
            int j = Partition(p, q);
            // 분할된 두개의 리스트중에서, 더 작은 놈을 먼저 정렬한다.
            if((j-p) < (q-j)) // 앞의 리스트가 더 작을 경우
            {
                // 나중에 쓰일 p, q값을 stack에 넣어 미룬다.
                s.push(j+1);
                s.push(q);
                q = j-1;
            }
            else // 뒤의 리스트가 더 작을 경우
            {
                s.push(p);
                s.push(j-1);
                p = j+1;
            }
        }
        if(s.empty()) // 뒤로 미뤄둔 것들이 더이상 없을 경우, 종료한다.
            return;

        q = s.top();
        s.pop();

        p = s.top();
        s.pop();
    }while(true);
}

algorithm