boortz@sics.se (Kent Boortz) (04/01/91)
I have written a sort routine using heapsort that is more than 3 times
faster than qsort included in the THINK C standard library. I know that
QuickSort is faster teoreticaly, and this one will not beat the new qsort
in the GNU library. HeapSort has some advantages. No additional memory
is used, not even stack space and it has no worst case.
I thought it could be useful and the source is so small that I include it here.
I hope it is OK.
Kent Boortz
boortz@sics.se
/*
* QSORT - implemented with heapsort
* (c) 1991, Kent Boortz
*
* This is a straight forward implementation of heapsort. The heap
* is created in O(n) time and the transformation from this heap
* to a sorted array is done in O(n * log n).
*
* This code is more than 3 times faster than the qsort included
* in the THINK C standard library. Heapsort has also the advantage
* that it uses no additional memory (THINK C qsort uses stack space)
* and that heapsort has no worst case.
*
* The code is written in a way to fool even the most stupid C
* compiler to produce reasonable code. I know that most/all
* of these ugly things is unnecessary when compiling with GCC.
*
*/
#include <stdlib.h>
void hsort(void *, size_t, size_t, int (*)());
#ifdef THINK_C
/* Note: The dbra instruction could not be used because the size */
/* of an element could be > 16 bits */
#define SWAP(BASE,SIZE,A,B,L) \
asm { \
move.l BASE,A0 /* char *a = base + A; */ \
add.l A,A0 \
move.l BASE,A1 /* char *b = base + B; */ \
add.l B,A1 \
move.l SIZE,D0 /* long i = size - 1; */ \
L: move.b (A0),D1 /* t = *a; */ \
move.b (A1),(A0)+ /* *(a++) = *b; */ \
move.b D1,(A1)+ /* *(b++) = t; */ \
subq.l #1,D0 \
bne.s L \
}
#else
#ifdef SPARC
#define SWAP(BASE,SIZE,A,B,C) \
{ \
register char *a = (BASE+A); \
register char *b = (BASE+B); \
long i = SIZE - 1; \
do \
{ \
long t; \
t = a[i]; \
a[i] = b[i]; \
b[i] = t; \
} \
while (--i >= 0); \
}
#else
#define SWAP(BASE,SIZE,A,B,C) \
{ \
register char *a = (BASE+A); \
register char *b = (BASE+B); \
long i = SIZE; \
do \
{ \
char t; \
t = *a; \
*(a++) = *b; \
*(b++) = t; \
} \
while (--i > 0); \
}
#endif SPARC
#endif THINK_C
void hsort(xbase, n, size, compar)
void *xbase;
register size_t n;
register size_t size;
int (*compar)(void *, void *);
{
register long e,p,c; /* end of heap, parent, child */
int mask = (size & (size - 1)) ^ size; /* Magic ;-) */
register char *base = (char *)xbase;
n *= size; /* n is now offset to last element+1 */
base -= size;
/*
* Create the heap
*
*/
for (e = (mask & n ? n - size : n) >> 1; e > 0; e -= size) {
for (p = e; (c = p << 1) < n; p = c) {
if (((c + size) < n) && ((*compar)(base + c + size, base + c) > 0))
c += size;
if ((*compar)(base + p, base + c) >= 0) break;
SWAP(base, size, c, p, @loop1);
}
}
/*
* Create a sorted list by using the property that the heap has the
* largest element on top. Adjust the heap after removing this largest
* element.
*
*/
for (e = n; e > size; e -= size) {
SWAP(base, size, size, e, @loop2);
for (p = size; (c = p << 1) < e; p = c) {
if (((c + size) < e) && ((*compar)(base + c + size, base + c) > 0))
c += size;
if ((*compar)(base + p, base + c) >= 0) break;
SWAP(base, size, c, p, @loop3);
}
}
}
--
Kent Boortz
boortz@sics.se