Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site rtp47.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!zeta!sabre!petrus!bellcore!decvax!harpo!whuxlm!akgua!mcnc!rti-sel!rtp47!meissner
From: meissner@rtp47.UUCP (Michael Meissner)
Newsgroups: net.sources
Subject: Re: qsort source
Message-ID: <170@rtp47.UUCP>
Date: Wed, 4-Sep-85 13:47:50 EDT
Article-I.D.: rtp47.170
Posted: Wed Sep  4 13:47:50 1985
Date-Received: Sat, 7-Sep-85 04:43:03 EDT
References: <276@anasazi.UUCP>
Reply-To: meissner@rtp47.UUCP (Michael Meissner)
Distribution: net
Organization: Data General, RTP, NC
Lines: 40
Keywords: qsort, pqsort
Summary: Bell qsort (system V) is better


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