[Algorithm/C++] 퀵 정렬(Quick Sort) - 분할과 재귀

 

 

1. 설명

퀵 정렬(Quick Sort)란 분할과 재귀를 사용하여 최종적으로 정렬된 리스트를 얻는 정렬 방식 중 하나이다.

 

 

여기서 분할이란 처음의 1개 문제가 있었다면 이를 2개 혹은 3개처럼 더욱 작은 문제로 나누어서 문제를 각각 해결한 후 합하여 처음의 복잡하였던 1개의 문제의 해답을 구하는 방법이다.

 

 

재귀란 간단하게 함수 속에서 해당 함수를 호출하는 형태라고 할 수 있으며, 계속 반복하여 실행되기 때문에 반복하여 실행되는 중 실행을 중단하는 조건을 포함해야만 하며 그렇지 않으면 무한 루프에 빠지게 된다.

 

 

 

동작 예시 (출처: https://visualgo.net/en/sorting)

 

 

퀵 정렬은 분할과 재귀를 사용한다고 하였는데, 우선 분할을 수행하여 동일한 형태이지만 작은 문제 2개로 만들고 동일한 형태이기 때문에, 재귀를 통하여 나누어진 작은 문제에서도 앞서 수행한 분할 작업부터 반복하게 된다.

 

 

 

분할을 할 때는 피벗(Pivot)이라는 값을 기준으로 왼쪽과 오른쪽으로 분할을 수행한다.

 

1. 위 동작 예시로 설명을 하자면 우선 처음 노란색의 Pivot이 선택된다. 이는 보통 왼쪽 끝이나 오른쪽 끝을 선택한다.

 

2. 그다음 어느 동작을 수행한 후 pivot이었던 노란색이 위치를 교환하면서 주황색으로 변하게 된다. 그러면 이때 기준으로 왼쪽에 있는 원소들은 Pivot보다 작은 원소들이며, 오른쪽에 있는 원소들은 Pivot보다 큰 값을 갖는 원소들로 이루어지게 된다.

 

3. 이제 Pivot보다 작은 원소들로 이루어진 왼쪽 원소들과, Pivot보다 큰 원소들로 이루어진 오른쪽 원소들로 더욱 작은 형태의 왼쪽, 오른쪽으로 분할되었다.

 

4. 분할하여 작은 문제로 나누었으니 다음으로 왼쪽의 원소들에서도 앞서 1번 과정부터 Pivot을 정한 후 어느 과정을 반복하여 수행하여 또 분할함으로써 최종적으로 정렬된 리스트를 얻게 되며, 마찬가지로 오른쪽의 원소들에서도 1번 과정부터 수행함으로써 정렬된 리스트를 얻게 되어 이를 합치면 최종적으로 정렬된 전체 리스트를 얻을 수 있게 된다.

 

 

 

 

특징

▶ 시간 복잡도는 O(N log N)이다. 이는 평균적인 시간 복잡도이며 선택 정렬(Selection Sort), 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort)의 O(N^2)와 비교해서 이름 그대로(퀵 정렬) 매우 빠르다는 것을 알 수 있다.

▶ 공간 복잡도는 O(log N)이다. 재귀적 호출로 발생하는 것이며, 최악의 경우 O(n)의 공간 복잡도를 가질 수도 있다.

▶ Unstable Sort이다. Unstable Sort란 동일한 값이 있을 경우 정렬 후 그 값들끼리 순서가 유지되지 않는 정렬이다. 

▶ 평균적인 시간 복잡도는 O(N log N)으로 매우 빠르지만 최악의 경우에서는 O(N^2)으로 매우 비효율로 동작하게 된다. 퀵 정렬의 최악의 경우는 이미 어느 정도 정렬이 되어 있는 리스트를 정렬하는 것이다.

또한, 최선의 경우에서 삽입 정렬이 O(N)으로서 더욱 빠른 속도를 보이지만 대부분의 경우 즉, 평균적인 경우 가장 효율적인 모습을 보여 대부분의 언어에서 내장 정렬 함수로서 퀵 정렬을 사용하는 경우가 많다.

 

 

 

 

2. 코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <iostream>
using namespace std;

void print(string s);
void quick_sort(int left, int right);
int partition(int left, int right);
vector<int> v = { 1, 7, 4, 3, 2, 9, 4 };

int main() {
    quick_sort(0, v.size() - 1);
    print("Quick Sort");

    return 0;
}


void print(string s) {
    cout << s << " : ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << "\n";
}

void quick_sort(int left, int right) {
    if (left >= right) return;

    int pivot = partition(left, right);

    quick_sort(left, pivot - 1);
    quick_sort(pivot + 1, right);
}

int partition(int left, int right) {
    int pivot = v[right];
    int pivot_index = right;

    right--;

    while (1) {
        while (v[left] < pivot) left++;
        while (v[right] > pivot) right--;

        if (left >= right) break;
        else {
            swap(v[left], v[right]);
            left++;
        }
    }
    swap(v[left], v[pivot_index]);
    
    return left;
}

 

결과

 

 

● quick_sort 함수

 

1. 재귀적인 형태를 갖으며 무한 루프의 빠지지 않기 위한 조건으로 left >= right 일 경우 return 하도록 하였다.

 

2. partion 함수로 pivot의 인덱스를 구하여 pivot을 기준으로 왼쪽의 원소들과 오른쪽의 원소들로 분할하여 분할된 각 원소들을 사용하여 다시 재귀 호출하고 있다.

 

3. 여기서 분할을 할 때 pivot은 제외가 되는데 그 이유는 pivot은 이미 정렬이 된 상태이기 때문이다.

 

4. 오름차순 기준으로 pivot 기준 왼쪽은 pivot보다 작은 값들로 이루어져 있고, pivot보다 오른쪽은 pivot보다 큰 값들로 이루어져 있기 때문에 이후 분할된 리스트가 어떻게 정렬이 되든 pivot의 위치는 이미 확정이 된 상태이다. 

 

 

 

 

● partition 함수

 

1. pivot으로 가장 오른쪽의 값을 선택하였고 그 값과 인덱스 값을 각각 변수로 초기화해준다.

 

2. 가장 오른쪽 값을 pivot으로 선택하였기 때문에 이 값을 비교 범위에서 제외하기 위하여 right--를 실행한다.

 

3. left는 가장 왼쪽에서 시작하여 pivot보다 큰 값이 나올 때까지 오른쪽으로 이동한다.

 

3. right는 가장 오른쪽에서 시작하여 pivot보다 작은 값이 나올 때까지 왼쪽으로 이동한다.

 

5. 오른쪽으로 이동하는 left가 왼쪽으로 이동하는 right보다 크거나 같아지면 while문을 종료하고, 그렇지 않으면 left 위치한 값과 right 위치한 값을 교환 해준 후 left를 1 증가시킨 후 다시 위 작업을 반복한다.

 

6. left가 right 보다 크거나 같은 곳 즉, pivot의 값이 위치할 인덱스 값을 구하였기 때문에 pivot 값과 해당 위치의 값을 교환해준 후 pivot의 index를 return 해준다.