[정렬] Quick sort

Quick sort

일정한 기준(pivot)에 따라서 큰 값과 작은 값으로 나누는 것의 반복으로 정렬.

시간 복잡도는 nlogn이다. 하지만 최악의 경우 (pivot이 가장 크거나 작다면) n^2이 되어버린다.

구현

보통은 재귀를 이용하여 구현한다.

사용자가 설정한 특정 값을 기준으로 그 값보다 더 큰값과 더 작은 값으로 나누는 과정을 반복한다.
이때, 특정한 값의 경우는 사용자의 맘. -> 보통은 가장 왼쪽의 값으로 한다.

1. 초기상태. pivot 값과 store 값 모두 left로 설정.
    store에서는 pivot보다 작은 값을 가진 idx의 최대값. store번째 까지는 pivot 보다 작은 값. store 이후에는 더 큰값이 들어감.
2. left+1, right까지 탐색.
3. arr[pivot] > arr[i]이라면, arr[i]와 arr[++store]을 swap
4. 탐색이 끝났다면, arr[pivot] 과 arr[store]을 swap
5. pivot = store로 값 갱신 후 pivot return.

이후에 0 ~ store-1 , store + 1 ~ right 로 나누어서 각각 partition을 진행하면 된다.

int partition(int left, int right) {
    int stored = left;

    int pivot = Arr[left];
    for(int i = left+1; i <= right; i++) {
        if(Arr[i] < pivot) {
            swap(Arr[i], Arr[++stored]);
        } 
    }
    swap(Arr[stored], Arr[left]);

    return stored;
}

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

    int p = partition(left, right);
    QuickSort(left, p-1);
    QuickSort(p+1, right);
}