QuickSort

The next algorithm the course required us to implement is QuickSort. QuickSort is quite a well known algorithm and, theoretically speaking, it performs as good as Merge Sort ( O(n log n) time ). In practice however, it usually comes out faster. Choosing the pivot well is essential to a good running time.
Here is my implementation, with the pivot choosing subroutine left out:

	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);
	}

view raw quicksort.cpp hosted with ❤ by GitHub

In my next post I will show how we can choose a good pivot and how much it matters.