Learn Quick Sort

Quick Sort

Quick Sort is a divide and conquer recursive algorithm used in sorting a data set. It is one of the fastest sorting algorithms with an average time complexity of O(Nlog(N)) and a worst case time complexity of O(N²).

Algorithm

• Pick a pivot ( element of the data set in the range)
• Iterate through the data set once and re-arrange data so that all the elements larger than the pivot are on the right side of the pivot and elements smaller than the pivot are on the left. 
• Apply the same re-arranging method recursively to the left and the right parts of the data set separated by the pivot.

Picking the pivot

The pivot can be any element of the data set within the range of the partition. But the pivot will decide the running time of the sorting process. Because if you choose the smallest/largest element of the data set every time, the partitioning will be useless and hence running time will be O(N²). Therefore spending some time to pick a good pivot won't be a waste. 

As mentioned above, choosing left-most element, right-most element or the element at middle as the pivot may lead to time inefficiency as the arrangement of the data set is not known. Choosing a random element also has the same risk. The best pivot will be the median of the data set. But finding it would not be wise considering the time efficiency. 

The easiest way to choose a pivot which is not a corner element is, picking the median element of the first, middle and the last element of the data set. This will ensure that you are not at the worst case every time. 

Advantages

• No additional memory required. ( Sort in place )
• Very fast sorting for average case

Disadvantage

• Worst-case complexity is O(N²)
• Sorting time not guaranteed.

Following is an implementation of quick sort algorithm in C

	void quickSort(int arr[SIZE], int left, int right)
	{
	if (left >= right)
	return;
	int piv_pos = partition(arr, left, right); // get pivot position after partitioning
	quickSort(arr, left, piv_pos); //Sort left part
	quickSort(arr, piv_pos + 1, right); //Sort right part
	}

view raw quickSort.c hosted with ❤ by GitHub

Partition function which does the sorting

	int partition(int arr[SIZE], int left, int right)
	{
	int piv_pos = pivot(arr, left, right); //get pivot
	int pos = left + 1, to_be_swapped = left + 1;
	//bring pivot to left
	swap(arr, piv_pos, left);
	piv_pos = left;
	while (1)
	{
	if (pos > right)
	{
	swap(arr, to_be_swapped - 1, piv_pos); // put pivot to right place
	return to_be_swapped - 1;
	}
	if (arr[pos] < arr[piv_pos])
	{
	swap(arr, pos, to_be_swapped); //swap if smaller elements found
	to_be_swapped++;
	}
	pos++;
	}

view raw quickSortPartition.c hosted with ❤ by GitHub

Here is the complete implementation of quick sort algorithm with example tests on github.