[알고리즘] quick sort

시간복잡도

최선: NlogN (피벗이 중앙에 위치할 경우)
평균: NlogN
최악: N^2 (분할이 0:10으로 되는 경우)

소스코드

#include <iostream>
#include <random>
using namespace std;

void generate(vector<int>& v) {
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(1,30);
    for(int i = 0; i < 10; i++) {
        v.push_back(dis(gen));
    }
}

int partition(vector<int>& v, int p, int r) {
    int i = p-1, j = p;
    while(j < r){
        if(v[j] > v[r]) { // 오름차순
            j++;
        }
        else {
            i++;
            swap(v[i], v[j]);
            j++;
        }
    }
    swap(v[r], v[i+1]);
    return i+1;
}

void quicksort(vector<int>& v, int p, int r) {
    if(p < r) {
        // q = pivot pos
        // 정렬
        int q = partition(v, p, r);

        // 작은쪽 분할
        quicksort(v, p, q-1);
        // 큰쪽 분할
        quicksort(v, q+1, r);
    }
}

int main() {
    vector<int> v;
    for(int i = 0; i < 10; i++) {
        v.clear();
        generate(v);

        cout << "---before---\n";
        for(auto& _v : v) {
            cout << _v << " ";
        }
        cout << endl << endl;

        quicksort(v, 0, v.size()-1);
        cout << "---after---\n";
        for(auto& _v : v) {
            cout << _v << " ";
        }

        cout << "\n====================\n";
    }

    return 0;
}

피벗

위 소스코드에서는 피벗을 맨 마지막 원소로 선택하였다.
하지만 이는 좋은 방법이 아니다.
듀얼 피벗이나, 3개의 피벗을 선택하여 중앙값을 피벗으로 선택하는 방법이 있다.
아래 문제는 위의 소스코드를 활용하여 풀었을 때, 시간초과가 발생한다. 최악의 경우 N^2의 시간복잡도를 보이기 때문이다.
수 정렬하기4

하지만, 피벗을 랜덤으로 정하면 최악의 경우를 피할 수 있으므로 위 문제를 해결할 수 있다.