[Algorithm] Quick Sort | SUMFIのBlog

Quick Sort

퀵 소트는 UnStable한 정렬로 Divde and Conquer의 개념을 적용한 정렬이다
하나의 Pivot을 선택해 해당 피벗의 값을 비교하여 엔티티 벡터를 좌 우로 분할한다
좌우로 분할하면 피벗은 엔티티 백터 내에서 적절한 위치에 존재하게 되고 피벗을 기준으로 좌 우는 작은 엔티티 큰 엔티티가 존재하게 된다
해당 엔티티범위들을 재귀적으로 반복해 정렬을 수행한다
O(n logn)의 시간 복잡도와 O(1)의 공간 복잡도를 가진다
Worst case의 경우 O(N^2)이다 이는 피벗을 어떻게 선정하느냐에 따라 달라진다
Dive and Conquer의 개념을 이해하면 쉽게 구현이 가능하다

동작 원리

오름차순 정렬 기준

피벗을 선정하고 Start 번째와 스왑한다
Left = Start + 1, Right = End - 1 부터 시작한다
Left는 피벗보다 큰 값을 만날 때 까지 순회한다
Right는 피벗보다 작은 값을 만날 때 까지 순회한다
Left가 Right보다 작다면 두 엔티티를 스왑한다
Left가 Right보다 크다면 파티션을 마친다
Left와 Start를 스왑한다
피벗을 기준으로 좌 우를 재귀적으로 반복한다

구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <random>
#include <numeric>

using namespace std;

inline void Partition(vector<int> &quickSortVec, int &left,
			int &right, int &high){
    int pivot = quickSortVec[left];
    int low = left + 1;
    while(low < high){
        while(low <= high && quickSortVec[low] < pivot) low++;
        while(high >= low && quickSortVec[high] > pivot) high --;
        if(low<high)  swap(quickSortVec[low], quickSortVec[high]);
    }
    swap(quickSortVec[left], quickSortVec[high]);
}

void QuickSort(vector<int> &quickSortVec, int left, int right){
    if(left<right){
        int standard = right+1;
        Partition(quickSortVec,left,right,standard);
        QuickSort(quickSortVec,left,standard-1);
        QuickSort(quickSortVec,standard+1,right);
    }
}

int main() {
    std::srand ( unsigned ( std::time(0) ) );
    vector<int> vec(1000);
    iota(begin(vec),end(vec),1);
    std::shuffle(std::begin(vec), std::end(vec), default_random_engine {});
    cout<<"Before Cell Sorting"<<endl;
    for(auto it : vec)
        cout<<it<<" ";
    cout<<endl;

    QuickSort(vec, 0, vec.size()-1);

    cout<<"After Cell Sorting"<<endl;
    for(auto it : vec)
        cout<<it<<" ";
    return 0;
}

Quick Sort

동작 원리

구현

같이보기