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
- 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