qsort source
Michael Meissner
meissner at rtp47.UUCP
Thu Sep 5 03:47:50 AEST 1985
Just for fun, I tried pqsort with a program I developed to evaluate qsort
functions compared to the library qsort function. It computes the number
calls to the comparison function (since that is often the bottle-neck for
qsort(3), since comparisons aren't cheap). The trials were (200 element
integer array, library qsort from system Vr1):
Case # # trials Initial array
------ -------- -------------
random: 93 random (seeded from time)
halves: 1 halves (2, 4, 6, ..., 1, 3, 5, ...)
rsort: 1 array sorted in reverse
rsort-H: 1 array sorted in reverse, except last element
rsort-L: 1 array sorted in reverse, except first element
sort: 1 array sorted in order
sort-H: 1 array sorted in order, except last element
sort-L: 1 array sorted in order, except first element
Case # Bell Sort Pqsort
------ --------- ------
random: 1439.48 (avg) 1447.18 (avg)
halves: 10099 2784
rsort: 1153 19900
rsort-H: 1153 19900
rsort-L: 1153 19900
sort: 1153 19900
sort-H: 1153 19702
sort-L: 1177 19900
Thus, the Bell qsort really shines when given nearly sorted arrays, or arrays
sorted nearly in reverse order, and is slightly better on random arrays. It's
downfall is in sorting arrays split by halves. Note, as the number of exchanges
was not counted, it may be that pqsort does less exchanges. It may also be
the internal functions are not aligned to a longword on a VAX in the library
qsort, thus slowing it down. It may also be a difference between the system V
qsort and the 4.[12] qsort.
Michael Meissner
Data General
...{ ihnp4, decvax }!mcnc!rti-sel!rtp47!meissner
More information about the Comp.sources.unix
mailing list