usr/klibc/qsort.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);
}
1	niro	532	/*
2			* qsort.c
3			*
4			* This is actually combsort. It's an O(n log n) algorithm with
5			* simplicity/small code size being its main virtue.
6			*/
7
8			#include <stddef.h>
9	niro	815	#include <stdlib.h>
10	niro	532	#include <string.h>
11
12			static inline size_t newgap(size_t gap)
13			{
14			gap = (gap * 10) / 13;
15			if (gap == 9 \|\| gap == 10)
16			gap = 11;
17
18			if (gap < 1)
19			gap = 1;
20			return gap;
21			}
22
23			void qsort(void *base, size_t nmemb, size_t size,
24			int (compar) (const void , const void *))
25			{
26			size_t gap = nmemb;
27			size_t i, j;
28			char p1, p2;
29			int swapped;
30
31			if (!nmemb)
32			return;
33
34			do {
35			gap = newgap(gap);
36			swapped = 0;
37
38			for (i = 0, p1 = base; i < nmemb - gap; i++, p1 += size) {
39			j = i + gap;
40			if (compar(p1, p2 = (char )base + j size) > 0) {
41			memswap(p1, p2, size);
42			swapped = 1;
43			}
44			}
45			} while (gap > 1 \|\| swapped);
46			}