[정렬] Quick Sort

퀵정렬은 피봇을 기준으로 왼쪽에는 피봇보다 작은 값을, 오른쪽에는 피봇보다 큰 값을 위치시켜 정렬하는 divide & conquer 알고리즘이다.

매번 해당 피봇의 자리를 찾는 과정이라고 볼 수 있다.

평균적으로 O(nlogn)이 걸리지만, 최악의 경우 O(n^2)이 걸린다.

다른 O(nlogn)의 알고리즘보다도 빠른데, 그 이유는 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환하며, 한 번 결정된 피봇이 추후 연산에서 제외되는 특성 때문이다.

최악의 경우 O(n^2)이 되는 이유는 merge sort와는 달리, 비균등하게 배열을 나누기 때문에

높이가 최대 O(n)이 될 수 있기 때문이다.

이렇게 되는 경우는 배열이 이미 정렬되어 있을 경우이다.

즉, 원소 간 비교는 O(n)으로 동일하지만, 높이가 평균적으로 O(logn)~O(n)까지 달라져 최악의 경우에는 매우 나쁜 성능을 보여준다.

---

#include <iostream>
#include <vector>

using namespace std;

// pivot의 위치를 결정해 리턴.
int partition(int arr[], int s, int e){
    int low = s+1, high = e;
    // 가장 왼쪽 값을 피봇으로 선택 
    // => 따라서 high의 최종 위치는 pivot보다 작은 값이므로 
    // high와 pivot을 마지막에 교환해 pivot을 가운데로 변경
    int pivot = arr[s];
    while(low < high){
        // pivot보다 큰 값을 찾을 때까지 low 증가
        while(low <= e && pivot > arr[low]){
            low++;
        }
        // pivot보다 작은 값을 찾을 때까지 high 감소
        while(high >= s && pivot < arr[high]){
            high--;
        }
        if(low >= high){
            break;
        }
        // 두 개 교환
        int tmp = arr[low];
        arr[low] = arr[high];
        arr[high] = tmp;
    }

    // pivot과 high를 교환
    arr[s] = arr[high];
    arr[high] = pivot;


    return high;
}

void quick_sort(int arr[], int s, int e){
    if(s >= e){
        return;
    }
    int pivot = partition(arr, s, e);
    quick_sort(arr, s, pivot-1);
    quick_sort(arr, pivot+1, e);
}

int main(void){
    int n = 10;
    int arr[10] = {2, 1, 9, 3, 4, 7, 2, 8, 10, 5};

    quick_sort(arr, 0, 9);

    for(int i = 0; i < 10; i++){
        cout << arr[i] << " ";
    }
    cout << "\n";

    return 0;
}