[gclist] Sorting a doubly linked list.
Tue, 03 Dec 1996 15:11:15 +0000
At 12:01 PM 12/3/96 -0800, you wrote:
>> You simply split
>> your data into three categories, less, equal, and greater than the
>> pivot. You only sort the ones that are less and greater. Then you
>> append the three resulting lists. When all keys are the same, the
>> pivot is necessarily one of those. All elements will thus be in the
>> `equal' caterogy, thus not sorted.
>> Robert Strandh
>This is the 'list' version of quicksort. See
Oh come on Henry. So you have the list [1,2,3,4 ... 1000]. So you take
the 1 off the head and produce three lists  1 and [2,3,4,5 ... 1000] and
you take the third list and get  2 and [3,4,5,6 ... 1000] great algorithm
Knuth would be proud.
I wrote the array qsort in Coherent and won every benchmark three years ago.
Start with the middle element as a pivot. If there is order this is the
best guess and if there is no order it doesn't matter. If its a bad choice,
I used (small partition < large partation/8) means a bad pivot, try 1/4 of
the way in. If thats a bad choice try 1/8 if thats bad go to shellsort.
With arrays expanding the center list turned out worse.
How good was it? One benchmark was an array 1 ... 10000 1 ... 10000 it was
called merging decks. My qsort took three seconds some of the others took
twelve hours. I can't have a garbage collector take twelve hours to sort
finalizers. This is why Knuth suggested random pivots.
Charles Fiterman Geodesic Systems
Phone 312-728-7196 4745 N. Ravenswood Suite 111
Fax 312-728-6096 Chicago Il 60015
A computer language without garbage collection
is like a city without garbage collection.