rchao@well.sf.ca.us (Robert Chao) (05/03/90)
Can someone post C code for a simple Quicksort? I'm new at this and copied a Quicksort pseudocode from a book into my C program. I noticed that the pseudo code didn't include a check to keep i and j from running off the ends of the list (where i is the location of the value you are comparing with the current key you want to place in its final position, and so is j). (The book was a data structure book by Tremblay and Sorenson.) Basically I understand Quicksort all right but I've never done it in code. Are there different variations on Quicksort? Thanks Robert Chao
ok@goanna.cs.rmit.OZ.AU (Richard O'keefe) (05/04/90)
In article <17773@well.sf.ca.us>, rchao@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}