[정렬#3] 퀵 정렬(Quick Sort)

가장 먼저 Pivot을 배열에서 하나 선택해서 Pivot을 기준으로 왼쪽에는 Pivot보다 작은 수가, 오른쪽에는 Pivot보다 큰 수가 정렬되도록 한다. 

이를 위해 배열의 인덱스 0을 가르키는 Low(또는 Left)를 시작으로 인덱스를 하나씩 증가시키며 Pivot보다 큰 수를 찾는다.

Left가 찾고 난 뒤, Right가 배열의 끝에서 점점 감소하며 Pivot보다 작은 수를 찾는다. 그러면 현재 Left는 Pivot보다 큰 수, Right는 Pivot보다 작은 수를 가르키고 있으므로 이 둘을 Swap한다.

(위의 그림에서는 두 수를 모두 찾고 나서 swap하는 것이 아닌, 빈칸(Vac)이 생기는 곳에 곧바로 찾은 수를 넣고 있다. 예를 들면, Pivot으로 선택된 45가 있던 자리에 Vac이 생기고, High가 가르키는 값이 처음부터 45보다 작으므로, 45가 있던 Vac자리고 곧바로 수를 옮기고 있는 그림을 볼 수 있다.)

Swap이 되어도 Left가 Right보다 작거나 같을 때까지(While) 계속 배열을 스캔한다. (두 번째 그림에서 'while loop exits'를 보면 알 수 있다)

다음으로 Pivot을 Left(low) 자리에 놓고, 

'원래 배열의 인덱스 0~Left-1'에 대하여 QuickSort를 재귀 호출.

'Left~원래 배열의 인덱스 마지막'에 대하여 QuickSort를 재귀 호출.

(Divide and Conquer 방식을 따른다)

재귀 호출 탈출은 배열의 사이즈가 0일 경우로 정한다.

모든 재귀호출을 끝내면 배열은 정렬된 상태가 되는 것을 볼 수 있다.

using namespace std;
 
 
 
void quickSort(int* arr, int left, int right){
    int pivot = left;
    int originalLeft = left;
    int originalRight = right;
 
    if (right - left <= 0)
        return;
 
    while (left <= right){
        while (arr[left] <= arr[pivot] && left <= right)
            left++;
        while (arr[right] >= arr[pivot] && left <= right)
            right--;
 
        if (left <= right){
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        
    }
    int temp = arr[pivot];
    arr[pivot] = arr[right];
    arr[right] = temp;
 
    quickSort(arr, originalLeft, left - 1);
    quickSort(arr, left, originalRight);
}
 
int main(){
 
    int arr[9] = { 3, 7, 2, 4, 5, 12, 6,10, 9 };
 
    quickSort(arr, 0, 8);
 
    for (int i = 0; i < 9; i++){
        cout << arr[i] << endl;
    }
 
    return 0;
} 

(이 구현은 완벽히 제자리 정렬(in-place sort) 방식이 아니다. 여기서 제자리 정렬이란 정렬되는 원소들의 갯수에 비해 무시할 만한 메모리만을 사용하는 정렬 방식을 뜻한다.)

Quick Sort의 경우 최악의 경우는 이미 오름차순으로 정렬되어 있을 경우이다. 이 경우 을 따른다.

평균적으로는 을 따른다.