duane@anasazi.UUCP (Duane Morse) (08/29/85)
Here is my own version of qsort for those of you interested in sorting
algorithms.
--------------------SUBROUTINE FOLLOWS, THEN MY SIGNATURE -------------
/*TITLE pqsort.c - quicksort algorithm 1/10/85 10:04:32 */
static char *version = "@(#)pqsort.c 1.1 1/10/85 10:04:32";
/*
** void pqsort(vec, nel, esize, compptr)
**
** Quick Sort routine.
** Based on Knuth's ART OF COMPUTER PROGRAMMING, VOL III, pp 114-117.
** For some unknown reason, this works faster than the library's qsort.
**
** Parameters:
** vec = points to beginning of structure to sort.
** nel = number of elements.
** esize = size of an element.
** compptr = points to the routine for comparing two elements.
**
** Returns:
** Nothing.
*/
static int elsize; /* Element size */
static int (*comp)(); /* Address of comparison routing */
static void memexch(), mysort();
void pqsort(vec, nel, esize, compptr)
unsigned char *vec;
int nel;
int esize;
int (*compptr)();
{
/* If less than 2 items, done */
if (nel < 2)
return;
elsize = esize;
comp = compptr;
/* Call the real worker */
mysort(vec, nel);
}
/*PAGE*/
/*
** void mysort(vec, nel)
**
** The real quick sort routine.
**
** Parameters:
** vec = points to beginning of structure to sort.
** nel = number of elements.
**
** esize = size of an element.
** compptr = points to the routine for comparing two elements.
**
** Returns:
** Nothing.
*/
static void mysort(vec, nel)
unsigned char *vec;
int nel;
{
register short i, j;
register unsigned char *iptr, *jptr, *kptr;
/*
** If 2 items, check them by hand.
*/
begin:
if (nel == 2) {
if ((*comp)(vec, vec + elsize) > 0)
memexch(vec, vec + elsize, elsize);
return;
}
/*
** Initialize for this round.
*/
j = nel;
i = 0;
kptr = vec;
iptr = vec;
jptr = vec + elsize * nel;
/*PAGE*/
while (--j > i) {
/*
** From the righthand side, find the first value that should be
** to the left of k.
*/
jptr -= elsize;
if ((*comp)(jptr, kptr) > 0)
continue;
/*
** Now from the lefthand side, find the first value that should be
** to the right of k.
*/
iptr += elsize;
while(++i < j && (*comp)(iptr, kptr) <= 0)
iptr += elsize;
if (i >= j)
break;
/*
** Exchange the two items.
** k will eventually end up between them.
*/
memexch(jptr, iptr, elsize);
}
/*
** Move item 0 into position.
*/
memexch(vec, iptr, elsize);
/*
** Now sort the two partitions.
*/
if ((nel -= (i + 1)) > 1)
mysort(iptr + elsize, nel);
/*
** To save a little time, just start the routine over by hand.
*/
if (i > 1) {
nel = i;
goto begin;
}
}
/*PAGE*/
/*
** memexch(s1, s2, n)
**
** Exchange the contents of two vectors.
**
** Parameters:
** s1 = points to one vector.
** s2 = points to another vector.
** n = size of the vectors in bytes.
**
** Returns:
** Nothing.
*/
static void memexch(s1, s2, n)
register unsigned char *s1;
register unsigned char *s2;
register int n;
{
register unsigned char c;
while (n--) {
c = *s1;
*s1++ = *s2;
*s2++ = c;
}
}
------------------------------------------------------
--
Duane Morse ...!noao!terak!anasazi!duane
(602) 275-0302meissner@rtp47.UUCP (Michael Meissner) (09/04/85)
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