Quicksort - need help and code

[Richard O'keefe]

In article <17773 at well.sf.ca.us>, rchao at well.sf.ca.us (Robert Chao) writes:
> Can someone post C code for a simple Quicksort?

The very simplest method is to call qsort(), which comes free with C.

> Are there different variations on Quicksort?

Lots and lots.  There's quicksort and quickersort.  There's median-of-three,
fat pivot, all kinds of variations.

The most important thing to remember about quicksort is that it is a
thing which people like to put in data structures books but which should
not be used in practice:
	if you know you are sorting numbers, there are quite a lot
	of sorting algorithms with O(N) expected time

	if you have to pass a comparison function, the alleged low cost
	of book-keeping in quicksort is swamped by procedure calling,
	and as quicksort (on a good day with the wind behind it) does
	30% more comparisons than the _worst_ case of merge sort, if
	you can spare O(N) memory and have enough time on your hands to
	write your own sorting routine there is no excuse for using
	quicksort instead of mergesort.

Quicksort was invented for a machine which had *256* words of main
memory and *16,384* words of backing store ("disc")!  Clearly, on that
machine, it was *far* more important to be able to sort _at all_ in its
extremely limited memory than to be able to sort fast.  If you have to
code a sorting algorithm on a typical "process control" chip with
limited on-chip memory, quicksort is ideal for that.
But that's _all_ it's good for.

For most people, the really important thing is to have a sorting routine
which you can _trust_ even if it _is_ rather slow, so if you are more
interested in _using_ a sorting routine than writing one, stick with qsort()
{which might be some variety of quicksort but need not be}