Skip to content

The “quick-sort” adventure & some great links to learn it.



Recently I had to figure out the workings of quick sort,one the fastest and easiest sorts to implement. There is a heap load of tutorials about quick sort apart from the videos demonstrations and animations showing the inner workings of quick sort. Before I link to the resources which I found helpful in learning quick sort, here is my implementation of quick sort in C.

int partition_data(int* data, int low, int high)
{
	if(low > high)
		return -1;

	int down = low;
	int up = high;
	//just assume and take the first element as the pivot value and index
	int pivot = low ;
	int pivot_element = data[pivot];

	while(down < up){
		//keep moving down till the  you find an element whose value is greater than the pivot element.
		//this element should be on the right side of the pivot element
		while(data&#91;down&#93; <= pivot_element && down < high)
			down++;

		//keep moving up till you find an element which is smaller than the pivot element.
		// this element should be on the left side of the pivot element.
		while(data&#91;up&#93; > pivot_element && up > low)
			up--;

		
		//swap the elements
		if(down < up){
			swap(data&#91;down&#93;, data&#91;up&#93;);
		}
	}
        //swap the pivot and the up element data , placing the pivot in its correct position
	swap(data&#91;pivot&#93;, data&#91;up&#93;);
	//extra step just for the sake of clarity
	pivot = up;
	return pivot; 
}



void qik_sort(int *data, int low, int high)
{
	if(high > low){
		int pivot = partition_data(data, low, high);
		print_data(data, 10);
		//sort the low -> pivot array
		qik_sort(data, low, pivot - 1);
		//sort the pivot -> high array
		qik_sort(data, pivot + 1, high);
	}
}

The version is a bit more documented than the ones you would generally find online. Also I assume my notes here will help me in recollecting quick sort in the future(This time it took me 3 days to figure it out).

Some helpful resources for learning quick sort are as follows:

  • http://www.comp.dit.ie/rlawlor/Alg_DS/sorting/Quick%20Sort%20Explanation.pdf
  • – The example given makes it worth a read.

  • http://m3peeps.org/qs.htm
  • – One of the most easy to understand explanations of quick sort.

  • http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L16-QuickSort.htm
  • http://betterexplained.com/articles/sorting-algorithms/
  • http://www.angelfire.com/pq/jamesbarbetti/articles/sorting/001_QuicksortIsBroken.htm
  • – Great analysis and great resource to getting more out of the simple quick sort.

  • http://stackoverflow.com/questions/6903064/handling-duplicate-keys-in-quicksort
  • – Mandatory stackoverflow.com links

  • http://stackoverflow.com/questions/11355621/pseudo-quicksort-time-complexity
  • – Mandatory stackoverflow.com links