Re: [HACKERS] \dt and disk access

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.

On the other hand, if you go to something like bubble sort, it will
work faster than quick sort if the data is sorted and you are adding one
more item, but on unsorted data it takes an enormously longer length of
time to sort a large list.

David Friend                ! cq995@freenet.carleton.ca
Atlantis Scientific Inc.        ! david.friend@atlsci.com
20 Colonnade Rd, Suite 110        ! 613-727-1087 (voice)
Ottawa, Ontario, CANADA  K2E 7M6    ! 800-265-3894 (voice)
ERGOvista Scientific Image Analysis    ! 613-727-5853 (fax)

------------------------------