usenet@nlm.nih.gov (usenet news poster) (09/29/90)
Here's source code for a "portable" heap sort function with best- and worst-
case performance of O(NlogN). Perhaps someone has time to compare its
performance with THINK C's qsort and Haydn Huntley's fastQsort.
I've found it to be about half the speed of an average BSD UNIX(TM) qsort
invocation for large lists.
Cheers,
Warren Gish
National Center for Biotechnology Information
National Library of Medicine
gish@ncbi.nlm.nih.gov
/****************************************************************************
hsort -- sort a list using an heap sort algorithm
This software is categorized as "United States Government Work"
and is hereby entered into the public domain under the terms
of the United States Copyright Act. Restrictions can not be
placed on its present or future use. This software is presented
"as is" with no warranty of any kind either expressed or implied.
****************************************************************************/
static void heapify (char *b0, char *b, char *lim, char *last, long w, int (*compar)());
void hsort(base, nel, width, compar)
register char *base; /* Base address of array */
long nel; /* No. of elements in array */
long width; /* Width in bytes of each element in array */
int (*compar)(); /* Element comparison routine */
{
register long i;
register char ch;
register char *base0 = base, *lim, *basef;
lim = &base[((nel-2)/2)*width];
basef = &base[(nel-1)*width];
for (base = &base0[(nel/2 - 1)*width]; base >= base0; base -= width)
heapify(base0, base, lim, basef, width, compar);
for (base = &base0[(nel-1)*width]; base > base0; base -= width) {
for (i=0; i<width; ++i) {
ch = base0[i];
base0[i] = base[i];
base[i] = ch;
}
lim = base0 + ((base-base0)/2 - width);
if (base > base0+width)
heapify(base0, base0, lim, base-width, width, compar);
}
}
static void heapify(base0, base, lim, last, width, compar)
register char *base0, *base, *lim, *last;
register long width;
register int (*compar)();
{
register long i;
register char ch;
register char *left_son, *large_son;
left_son = base0 + 2*(base-base0) + width;
while (base <= lim) {
if (left_son == last)
large_son = left_son;
else
large_son = (*compar)(left_son, left_son+width) >= 0 ?
left_son : left_son+width;
if ((*compar)(base, large_son) < 0) {
for (i=0; i<width; ++i) {
ch = base[i];
base[i] = large_son[i];
large_son[i] = ch;
}
base = large_son;
left_son = base0 + 2*(base-base0) + width;
} else
break;
}
}