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

2. 퀵 정렬 ; Quick Sort

2.1 개념

분할 정복 알고리즘을 이용한 정렬 방법 중 하나로, 병합 정렬과 마찬가지로 전체 집합을 작은 크기의 부분집합으로 나누어 정렬을 수행한 뒤 다시 합치는 정렬 방법을 의미한다. 병합 정렬의 핵심 연산은 병합인 데 비해 퀵 정렬의 핵심 연산은 분할이다. 퀵 정렬은 다음과 같은 단계로 진행된다.

 

1. 분할(Divide) : 정렬할 집합을 기준값을 중심으로 두 부분집합으로 분할

2. 정복(Conquer) : 부분집합 내에서 기준값의 정렬 위치 선정

 

이 때 사용하는 기준값을 피봇(Pivot) 이라고 하는데, 첫 번째 원소 / 마지막 원소 / 가운데 원소 등 임의의 순서의 값을 정하면 된다. 이렇게 정한 기준값을 중심으로 왼쪽(L)과 오른쪽(R) 부분집합으로 나누어 정렬한다. 퀵 정렬은 다음과 같이 동작한다.

 

1. 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피봇보다 크거나 같은 원소를 찾아 L로 표시한다. 단, L은 R과 만나면 더 이상 오른쪽으로 이동하지 못하고 멈춘다.
2. 오른쪽 끝에서 왼쪽으로 움직이면서 피봇보다 작은 원소를 찾아 R로 표시한다. 단, R은 L과 만나면 더 이상 왼쪽으로 이동하지 못하고 멈춘다.
3. 1과 2에서 찾은 L 원소와 R 원소가 있을 경우 값을 비교한 후 서로 교환하고 L과 R의 현재 위치에서 1과 2 작업을 다시 수행한다.
4. 1 ~ 2를 수행하면서 L과 R이 같은 원소에서 만나 멈춘 경우 피봇과 R의 원소의 값을 비교한 뒤 서로 교환한다. 교환된 자리를 피봇 위치로 확정하고 현재 단계의 퀵 정렬을 끝낸다.
5. 피봇의 확정된 위치를 기준으로 만들어진 새로운 왼쪽 부분집합과 오른쪽 부분집합에 대해서 1~3(4)의 퀵 정렬을 순환적으로 반복 수행하되, 모든 부분집합의 크기가 1 이하가 되면 전체 퀵 정렬을 종료한다.

 

그림과 함께 이해해보도록 하자.

정렬되지 않은 집합 A는 다음과 같이 구성되어있다.

A = { 3, 8, 7, 2, 5, 1, 4, 6 }

집합 A를 오름차순으로 정렬한다고 가정을 해보자. 퀵 정렬하는 과정은 아래 그림과 같다. 이 때, 피봇은 가운데 원소로 설정한다.

 

1단계 : L을 피봇 값인 2보다 크거나 같은 원소를 만날 때 까지 이동하고, R을 2보다 작은 원소를 만날 때 까지 이동한다. L과 R이 가리키는 원소의 값을 비교하였을 때 3이 1보다 크기 때문에 두 자리를 교환한다. 다시 L을 2보다 크거나 같은 원소를 만날 때 까지 이동하고, R을 2보다 작은 원소를 만날 때 까지 이동한다. 이 때, L과 R이 만나 멈췄기 때문에 가르키는 값과 피봇의 값을 비교하고, 2가 8보다 작기 때문에 두 자리를 교환한다. 더 이상 이동할 수 없으므로 피봇이었던 2의 위치를 확정한다.

2단계 : 왼쪽 부분집합의 크기가 1이기 때문에 정렬을 하지 않고, 오른쪽 부분집합만 퀵 정렬을 실행한다. L을 피봇 값인 5보다 크거나 같은 원소를 만날 때 까지 이동하고, R을 5보다 작은 원소를 만날 때 까지 이동한다. L과 R이 가리키는 원소의 값을 비교하였을 때 7이 4보다 크기 때문에 자리를 교환한다. 다시 L과 R을 이동시킨 뒤, 멈춘 자리에서 값을 서로 비교한다. 8보다 2가 더 작기 때문에 자리를 교환한다. 다시 L과 R을 이동시키는데 R이 L과 만나 멈췄기 때문에 8과 피봇인 5의 값을 비교한 후, 5가 8보다 작기 때문에 자리를 교환하지 않고 5의 위치를 확정한다.

3단계 : 왼쪽 부분집합의 퀵 정렬을 실행한다. L이 가리키는 피봇보다 크거나 같은 값이자 피봇 값인 4와 R이 가리키는 값을 비교하였을 때 4보다 3이 더 작으므로 두 위치를 교환한 뒤 4의 위치를 확정한다.

4단계 : 오른쪽 부분집합의 퀵 정렬을 실행한다. 마찬가지로 L과 R 값을 비교하여 교환한 뒤, R이 L과 만나 더 이상 이동할 수 없으므로 7과 8을 비교하여 7의 위치를 확정한다.

5단계 : 모든 남은 부분집합의 크기가 1이므로 위치를 확정한 뒤 퀵 정렬을 종료한다.

 

2.2 코드

퀵 정렬 역시 정렬을 위한 partition() 함수와 분할과 퀵 정렬을 재귀적으로 호출하는 quickSort() 두 함수를 통해 작동된다. 퀵 소트의 시간 복잡도는 평균적으로 O(n log n) 으로 빠른 편이지만, 피봇 선정 위치에 따라 최악의 경우 O(n^2)가 될 수 있다. 하지만 다른 정렬 방법에 비해 자리 교환 횟수가 적기 때문에 일반적으로 다른 정렬 방법보다 빠르게 실행된다.

 

예제 코드의 피봇은 첫 번째 원소로 설정하였다.

 

#1. partition(vector<int>::iterator begin, vector<int>::iterator end)

vector<int>::iterator partition(vector<int>::iterator begin, vector<int>::iterator end) {
    int pivot = *begin;
    auto left = begin + 1;
    auto right = end;

    while(true) {
        while(*left <= pivot && distance(left, right) > 0) left++;
        while(*right > pivot && distance(left, right) > 0) right--;

        if(left == right) break;
        else iter_swap(left, right);
    }

    if(pivot > *right)
        iter_swap(begin, right);

    return right;
}

 

#2. quickSort(vector<int>::iterator begin, vector<int>::iterator end)

void quickSort(vector<int>::iterator begin, vector<int>::iterator end) {
    if(distance(begin, end) >= 1) {
        auto it = partition(begin, end); // vector<int> it = partition(begin, end);
        quickSort(begin, it - 1);
        quickSort(it, end);
    }
}

+)

작년 알고리즘 수업 들을 때 시험기간에 퀵 소트를 공부하면서 우연히 찾아보게 된 영상 중 하나인데, 끝까지 보고 앉아있는 내 자신을 볼 수 있다. 의외로 그 어떤 예제보다도 이해가 잘된다.

🔗 : https://www.youtube.com/watch?v=ywWBy6J5gz8