-=>Quoting Mathieu Bouchard to Darin Mcbride <=-
MB>1. take the 1st element as the pivot.
MB>2. walk through the list, separate the bigs from the smalls by
MB>building two lists. looks like a zipper that you unzip.
MB>3. process the two lists separately and recursively.
MB>4. unite them with the pivot.
MB>is this a quicksort or not?
It is,... except for the zipper part. [grin]
DM>Quicksort needs to be able to quickly find
DM>arbitrary nodes and swap them.
MB>This ain't no quicksort, afaik.
Maybe he is refering to the partitioning function...
DM>And I think quicksort has O(log n) timing, unless I'm already
DM>forgetting the standard timings. :-) If I'm right, that's a major
DM>difference in speed between nlgn and lgn.
MB>quicksort, mergesort, heapsort are in n log n time. how do you expect
MB>that sorting a collection of n elements takes less than n time?
MB>(unless it is pre-ordered to a certain extent, in a known manner)
Regular Quick sort is a poor performer with pre-sorted arrays. The
imporved ones that take multiple samples for determining the mean
tend to do better, ie. the first, middle, and last average method.
If someone needs to add, or update a list, then resort it, a bubble
sort will probably do the trick.
MB>matju
cya
--- Maximus/2 3.01
---------------