At 9:48 PM 6/23/97, David Friend wrote:
>On Sun, 22 Jun 1997, Thomas G. Lockhart wrote:
>
>> I don't know which Knuth algorithm the code uses, but some sort
>> algorithms perform very poorly on data which happens to be already
>> sorted. QuickSort, which comes on many Unix boxes (the qsort() call) is
>> quickest on completely unordered/disordered data and its slowest
>> performance is on already perfectly sorted data (I'm doing this from
>> memory, but the facts may be mostly correct :).
>
From what I remember, the quick sort algorithm works just as fast on
>sorted data as on unsorted data. In other words, the algorithm does not
>take advantage of the fact that the data is sorted.
What Thomas says is correct for the standard textbook description of
quicksort. It is not hard to reverse the order of the compare and fix it
so its worst case is reverse-sorted instead of presorted data. I would
expect that most vendor's implementations have this fix, but no guarantees.
I have skipped the first part of this discussion. Quicksort is a good
in-memory algorithm for uniprocessors. It may not be applicable to
database sorts of very large data sets.
Signature failed Preliminary Design Review.
Feasibility of a new signature is currently being evaluated.
h.b.hotz@jpl.nasa.gov, or hbhotz@oxy.edu
------------------------------
