Let's Do The Quicksort

In my books I demonstrate how to sort numbers and strings by using the very basic bubble sort technique.
As demonstrated in the books, a bubble sort is pretty logical and very easy to understand. The problem with the bubble sort is that it's time-consuming. Because the bubble sort forces the computer to compare each and every pair of values in an array it means that the sort goes through the same number of iterations even when the list has already been sorted.

A better way to sort is the "divide and conquer" method of sorting information, the quicksort. British computer scientist Sir Charles Antony Richard Hoare developed the quicksort algorithm in 1960. Today it stands as the most popular method of sorting information in a computer.

How It Works

You can read details on the quicksort by visiting its almighty Wikipedia entry here (link opens in a new window). Basically it works like this:

The list is split on a pivot.
Elements in the list are shuffled so that those less than the pivot are placed before the pivot, and those greater than the pivot are placed after.
Elements on each side of the pivot are then sorted recursively.

After only a few passes, the list is ordered in a way that sorting the elements is merely a matter of swapping adjacent values. So, unlike the tedious bubble sort, there is no need to go through multiple passes to move a low value from the "left" side of the list to the "right."

As always, a demonstration program works well to prove the point: click here to see the qs1.c code.

In addition to main() there are three functions:

sort() sets the pivot point and recursively chops the array up into smaller and smaller chunks.

partition() works left and right of the pivot point to order the elements according to the pivot value.

swap() simply swaps two array elements.

Altogether these functions quickly arrange elements in the list as the program's output attests:

Before sort:
446 585 212 115 129 0 402 730 344 690
After sort:
0 115 129 212 344 402 446 585 690 730

Feel free to modify the code so that the array holds different values, or perhaps more values. Or modify code from the book to sort lotto balls or a deck of cards or a blast of random numbers.

A Peek Into The Guts

Here is a modified version of the code that lets you see how the sort progresses in a visual way. The code (which you can see by clicking on the link), generates output that looks like this:
Before sort:
444 555 222 111 999 0 888 777 333 666
Pivot point is 666:
444 555 222 111 333 0 666 777 999 888
Pivot point is 0:
0 555 222 111 333 444 666 777 999 888
Pivot point is 444:
0 333 222 111 444 555 666 777 999 888
Pivot point is 111:
0 111 222 333 444 555 666 777 999 888
Pivot point is 333:
0 111 222 333 444 555 666 777 999 888
Pivot point is 888:
0 111 222 333 444 555 666 777 888 999
After sort:
0 111 222 333 444 555 666 777 888 999

You can see the pivot point chosen and then the result of that partition on each line. The first pivot point is 666, and the next line shows the list partitioned with values less-than and greater-than 666.

The second pivot point chosen is 0, then 444, then 333, and finally 888. The sort works because the list keeps getting split into smaller and smaller chunks. So you can see that 999 and 888 aren't "fixed" until the last pass, when the values are merely swapped.

What About Strings?

Strings can be sorted just like values. The difference is that a strcmp() or similar function must be used to compare the strings, and also that an array of pointers to the strings should be sorted instead of swapping the strings themselves, which can be time-consuming and ripe for causing errors.

Click here to copy or download code that demonstrates how to use the quicksort to swap an array of strings.
The string code is essentially the same business as the code for sorting numeric values, but strcmp() is used to compare the strings. strcmp() returns values less than, equal to, or greater than zero depending on how the first and second strings (its arguments) compare. This plays in well with the use of < = > when used for comparing numbers as the comparison signs and symbols are the same.

Of course, the major difference is that an array of string pointers is sorted, not the string array itself. As you recall from the books, the string pointers are merely memory addresses, similar to long ints but referencing a location where the string dwells in the computer's memory. Those values are easier to swap than copying and swapping the actual strings. And, as you can see by the program's output, by swapping an array of pointers you keep the original array un-touched:

Before After
pear apple
apple banana
papaya berry
orange cherry
grape coconut
banana grape
mango mango
berry orange
cherry papaya
coconut pear

Ta-da! It works. But do remember that you must initialize a pointer before you use it (refer to lines 20 and 21 in the code), and that you must use strcmp() or a similar function to compare the strings, not just the regular comparison operators.

What About Other Sorts?

There are many other ways to sort things with a computer. Some of these techniques are simply programming exercises and some of them are ways to sort a huge volume of information quickly. I may present a few as time permits, or as I encounter and use them in my own work.