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

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
- http://m3peeps.org/qs.htm
- 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
- http://stackoverflow.com/questions/6903064/handling-duplicate-keys-in-quicksort
- http://stackoverflow.com/questions/11355621/pseudo-quicksort-time-complexity

– The example given makes it worth a read.

– One of the most easy to understand explanations of quick sort.

– Great analysis and great resource to getting more out of the simple quick sort.

– Mandatory stackoverflow.com links

– Mandatory stackoverflow.com links