47 lines
828 B
C
47 lines
828 B
C
/*
|
|
* qsort.c
|
|
*
|
|
* This is actually combsort. It's an O(n log n) algorithm with
|
|
* simplicity/small code size being its main virtue.
|
|
*/
|
|
|
|
#include <stddef.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
static inline size_t newgap(size_t gap)
|
|
{
|
|
gap = (gap * 10) / 13;
|
|
if (gap == 9 || gap == 10)
|
|
gap = 11;
|
|
|
|
if (gap < 1)
|
|
gap = 1;
|
|
return gap;
|
|
}
|
|
|
|
void qsort(void *base, size_t nmemb, size_t size,
|
|
int (*compar) (const void *, const void *))
|
|
{
|
|
size_t gap = nmemb;
|
|
size_t i, j;
|
|
char *p1, *p2;
|
|
int swapped;
|
|
|
|
if (!nmemb)
|
|
return;
|
|
|
|
do {
|
|
gap = newgap(gap);
|
|
swapped = 0;
|
|
|
|
for (i = 0, p1 = base; i < nmemb - gap; i++, p1 += size) {
|
|
j = i + gap;
|
|
if (compar(p1, p2 = (char *)base + j * size) > 0) {
|
|
memswap(p1, p2, size);
|
|
swapped = 1;
|
|
}
|
|
}
|
|
} while (gap > 1 || swapped);
|
|
}
|