Quick Sort

Notes

Skiena Chapter 4

Overview

Quick sort - also known as partition-exchange sort - is based on the idea of picking a random pivot, and sorting things on either side of the pivot. The real savings of quicksort come from the fact that, once we partition all elements into a high and low pile, we can now sort these piles independently. Thus, like merge sort, we are progressively reducing the size of the piles of things we are sorting, and can implement quicksort recursively.

Quick sort is a random algorithm. Whenever we deal with a random algorithm, we always want to think about what the worst case scenario is, and what we can do to avoid it. In the case of quicksort, the worst case scenario consists of bad choices for each pivot - namely, each pivot that is chosen happens to be right next to the prior pivot, so we are continually sorting things one at a time, making quick sort equivalent to Insertion Sort.

In the average case, quicksort is O(N log N) - in other words, it is as good as, or better than, heap sort or merge sort (our two "old faithful" O(N log N) search algorithms).

However, in the worst case (which should happen very infrequently), quicksort is O(N^2).

Implementation

Quick Sort/Pseudocode

Quick Sort/Python

Quick Sort/Java

Quick Sort/Go

C Implementation

Here is a C implementation of quicksort from Skiena Chapter 4:

quicksort(item_type s[], int lo, int hi) 
{
	int p; // index of partition
	if((hi-lo)>0) { 
		p = partition(s, lo, hi);
		quicksort(s, lo, p-1);
		quicksort(s, p+1, hi);
	}
}

This makes use of the following partition function:

int partition(item_type s[], int lo, int hi)
{
	int i; 			// counter
	int p; 			// pivot element index
	int firsthigh; 	// divider position for pivot element

        // pivot equals s at hi
	p = hi;

	firsthigh = 1;
	for(i = 1; i < hi; i++) { 
		if(s[i] < s[p])  {
			wswap(&s[i], &s[firsthigh]);
			firsthigh++;
		}
	}

	swap(&s[p], &s[firsthigh]);

	return( firsthigh );
}