c++ quick sort 구현 코드

quick sort는 정렬을 평균적으로 O(n*logn)의 시간복잡도로 수행 가능하다.

최악의 경우는 O(n^2)이다.

 

quick sort의 정렬이 최악이 되는 경우는 pivot이 계속 인덱스의 끝에 위치하는 경우이다.

하지만 구현하기 쉬우면서, 평균적으로 O(nlogn)이기 때문에 괜찮다.

 

코드 >>

#include <iostream>
#include <vector>
 
 
void quick_sort(int start, int end, std::vector<int>& nums)
{
    
    int i = start+1;
    int j = end;
    int pivot = start;
    
    if (start >= end)
    {
        return;
    }
    
    
    
    while (i<=j)
    {
        while (nums[i] <= nums[pivot])
        {
            i++;
        }
        while (nums[j] > nums[pivot])
        {
            j--;
        }
        if (i > j)
        {
            
            int tmp = nums[j];
            nums[j] = nums[pivot];
            nums[pivot] = tmp;
            pivot = j;
        }
        else
        {
            int tmp;
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        
    }
    
    quick_sort(start, pivot-1, nums);
    quick_sort(pivot+1, end, nums);
    
}
 
 
int main()
{
    std::vector<int> nums = {5,4,7,9,5,2,3,99,5,1,2,3,7,4,2};
    quick_sort(0,nums.size()-1,nums);
    for (const auto num : nums)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
 
    return 0;
}