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.
[cpp]
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[down] <= 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[up] > pivot_element && up > low)
up–;

//swap the elements
if(down < up){ swap(data[down], data[up]); } } //swap the pivot and the up element data , placing the pivot in its correct position swap(data[pivot], data[up]); //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);
}
}
[/cpp]

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

Leave a Reply