brian.olender@canremote.uucp (BRIAN OLENDER) (09/23/89)
Subj: Looking for portable sort algorithm In article <1102@lakesys.UUCP> davek@lakesys.UUCP (Dave Kraft) writes: >Hi, >I'm looking for a sort algorithm that is portable >between Turbo C 2.0 and Xenix. There are many different sort algorithms; and equally as many applications for same. A common application is to sort an array of pointers or structures (or other objects) in memory; the ANSI standard routine qsort() is designed for this. To call qsort, you must provide as parameters: (1) a pointer to the array of elements to be sorted. (2) the number of elements in the array. (3) the width of each element. [use the macro "sizeof()" to determine this] (4) a pointer to a comparison function which in some way compares the elements which it's arguments point to. [Returning zero if the elements are equal; positive if the first argument evaluates greater than the second; negative otherwise]. A useful reference for this and many other library functions is "The Waite Group's Turbo C Bible" by Barkakati; published by Howard W. Sams & Company. Here is a heapsort which should be reasonably portable between ANSI compilers. Heapsort is sometimes preferred over quicksort since it has very much better worst case performance (although quicksort wins where average performance is the criterion). ======== cut here ========= /* hsort - a Heap Sort Function in 'C' * * Released to the public domain 1989 by B. P. Olender * * Calling Convention: Same as ANSI library function qsort() * * References: Donald E. Knuth, "The Art of Computer Programming * - Volume 3 - Sorting and Searching"; * Addison-Wesley * * William H. Press et al, "Numerical Recipes in C"; * Cambridge Press */ #include <stdlib.h> #include <string.h> typedef int (*comp_t)(const void *, const void *); *-*-*-*-* Message continued in next message *-*-*-*-* --- * Via ProDoor 3.1aR
brian.olender@canremote.uucp (BRIAN OLENDER) (09/23/89)
Subj: Looking for portable sort algorithm
*-*-*-*-* Message continued from prior message *-*-*-*-*
void hsort(void *, size_t, size_t, comp_t);
void
hsort (void *base, /* pointer to the array base */
size_t nel, /* number of elements */
size_t width, /* size of elements */
comp_t comp) /* comparison function */
{
char *i, *j, *l, *ir, *temp;
if (nel < 2)
return; /* if not at least two elements *
if (!(temp = (char *)malloc(width)))
return; /* memory allocation error */
ir = (char *)base + (nel - 1) * width; /* last element */
l = (char *)base + (nel >> 1) * width; /* middle element + 1 */
for (;;) {
if (l <= base) { /* selection phase */
memcpy(temp, ir, width); /* make room here */
memcpy(ir, base, width); /* select top of heap */
ir -= width;
if (ir <= base) {
memcpy(base, temp, width); /* smallest element */
free(temp);
return;
}
}
else { /* heap creation phase */
l -= width;
memcpy(temp, l, width); /* element to be sifted */
}
/* sift down element in temp to its proper level */
j = l;
while (i = j, (j += (j - base + width)) <= ir) {
if (j < ir && (*comp)(j, j + width) < 0)
j += width;
if ((*comp)(j, temp) < 0)
break;
memcpy(i, j, width); /* demote element in temp */
}
memcpy(i, temp, width); /* this is temp's level */
}
}
======== cut here =========
__ ____
/ ) / / /) /
/--< __ o __. ____ / / (/ _ ____ __/ _ __
/___/ / (_<_ (_/|_/ / <_ /___/ _/\_(/_/ / <_(_/|_(/__/ (_
---
* Via ProDoor 3.1aR