Quick Sort

 

#include <bits/stdc++.h>



template<typename T>
void QuickSort(std::vector<T> & arr, int left, int right) {

    int len = right - left + 1;
    if (len <= 1) return;
    int pivotIdx = std::rand() % len + left;
    int lastIdx = right;
    int pivot = arr[pivotIdx];
    std::swap(arr[pivotIdx], arr[lastIdx]);

    int leftIdx = left;
    int rightIdx = lastIdx - 1;

    while(leftIdx <= rightIdx) {
        if (arr[leftIdx] <= pivot) {
            ++leftIdx;
            continue;
        }

        if (arr[rightIdx] > pivot) {
            --rightIdx;
            continue;
        }

        if (pivot < arr[leftIdx] && pivot >= arr[rightIdx]) {
            std::swap(arr[leftIdx], arr[rightIdx]);
            continue;
        }
    }
    std::swap(arr[leftIdx], arr[lastIdx]);

    QuickSort(arr, left, leftIdx - 1);
    QuickSort(arr, leftIdx, right);
}



template<typename T>
void printArr(std::vector<T> arr){
    for (auto ele : arr) {
        std::cout << ele << " ";
    }
    std::cout << "\n";
}



int main(int argc, char** argv) {

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::vector<int> arr = {5, 7, 9, 3, 1, 5, 5, 2, 4};
    std::cout << "before : ";
    printArr(arr);
    
    QuickSort(arr, 0, arr.size() - 1);

    std::cout << "after  : ";
    printArr(arr);
	return 0;
}

 

 

정리

시간복잡도

worst case : O(N^2)   ---> 각 분할이 1 , N - 1로 분할되는 경우

average case : O(NlogN)

best case : O(NlogN)  ---> 각 분할이 N / 2, N / 2로 분할되는 경우

 

공간복잡도

O(1)

 

Stable : X