[C++] 퀵 소트(Quick Sort) 구현

정렬 알고리즘 중 빠른 속도를 자랑하는 퀵소트 알고리즘

정렬을 하는 알고리즘을 구현했습니다.

 

#include <iostream>
template <typename T>
class QuickSort{
private:
    int sort(T* array_list, int left, int right){
        int pivot = left;
        int low = left + 1;
        int high = right;
        while(low <= high){
            while(low < right && array_list[low] <= array_list[pivot])
                low++;
            while(high > left && array_list[high] >= array_list[pivot])
                high--;
            if(low > high){
                this->swap(array_list[pivot], array_list[high]);
            }
            else{
                this->swap(array_list[low], array_list[high]);
            }
        }
        return high;
    };
    void swap(T& a, T& b){
        T tmp = a;
        a = b;
        b = tmp;
    };
public:
    void quick_sort(T* array_list, int left, int right){
        if(left >= right) return;
        int pivot = this->sort(array_list, left, right);
        this->quick_sort(array_list, left, pivot);
        this->quick_sort(array_list, pivot+1, right);
    };
};

int main(){
    int arr[10];
    for(int i = 0; i < 10; i++){
        arr[i] = rand() % 100;
    }
    int _size = sizeof(arr)/sizeof(int);
    QuickSort<int> qs;
    //before
    for(int i = 0; i < _size; i++)
        std::cout << arr[i] << " ";
    std::cout << "\n";
    qs.quick_sort(arr, 0, _size-1);
    //after
    for(int i = 0; i < _size; i++)
        std::cout << arr[i] << " ";
}

 

실행결과