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)

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

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

  • – 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 links

  • – Mandatory links