QuickSort

quicksort.cpp

template<typename T>
void quickSort(std::vector<T>& nums)
{
    _qSort(nums, 0, nums.size());
}

template<typename T>
void _qSort(std::vector<T>& nums, int begin, int end)
{
    if(end - begin < 2)
        return;

    int pivot = choosePivot(nums, begin, end);

    swap(nums[begin], nums[pivot]);
    pivot = begin;

    int i = begin + 1;
    for(int j = begin + 1; j < end; j++)
    {
        if(nums[j] < nums[pivot])
        {
            swap(nums[i], nums[j]);
            i++;
        }
    }
    swap(nums[pivot], nums[i-1]);


    _qSort(nums, begin, i-1);
    _qSort(nums, i, end);


}