QuickSort가 뭐죠?

퀵 소트(Quick Sort)는 분할 정복 기법을 활용해서 빠른 속도로 정렬할 수 있는 알고리즘입니다.
O(n * log(n))의 시간복잡도를 가집니다.

어떻게 동작하죠?

퀵 소트의 단계는 이러합니다.
1. Pivot 설정하기
2. Pivot 보다 작은건 인덱스가 작은쪽으로 큰건 인덱스가 큰 쪽으로
3. Pivot과 right를 바꿔줍니다.
그리고 (left, Pivot-1)을 다시 1번 부터 해주고,
(Pivot+1, right)를 다시 1번 부터 해줍니다.

이렇게 하면 첫번째 수를 가지고 정렬해주고 첫번째 수가 들어간 위치를 기준으로 왼쪽 정렬, 오른쪽 정렬을 계속해서 왼쪽보다 오른쪽이 클 때까지만 해주시면 정렬이 됩니다.

Code

#include <iostream>
using namespace std;
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}
int partition(int array[], int left, int right) {
    int end = right;
    right += 1;
    int pivot = left;
    do {
        do {
            left++;
        } while(array[left] < array[pivot] && left <= end);
        do {
            right--;
        } while(array[right] > array[pivot]);
        if(left < right) {
            swap(array[left], array[right]);
        }
    } while(left < right);
    swap(array[pivot], array[right]);
    return right;
}
void quickSort(int array[], int left, int right) {
    if(left < right) {
        int q = partition(array, left, right);
        quickSort(array, left, q-1);
        quickSort(array, q+1, right);
    }
}
int main() {
    int test_arr[] = {23, 123, 32, 41, 2, 6, 141, 22, 3};
    quickSort(test_arr, 0, sizeof(test_arr)/sizeof(test_arr[0]-1));
    for(int i=0; i<sizeof(test_arr)/sizeof(test_arr[0]); i++) {
        cout << test_arr[i] << " ";
    }
    return 0;
}