Root/
| Source at commit 1834 created 12 years 4 months ago. By blackosx, Fix (patch) building process. Resources now download and build successfully so package can be made. Checks are now needed to see if this works on different localizations and different systems. I have a feeling more work weill be needed to handle the unicodes etc. | |
|---|---|
| 1 | /*␊ |
| 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 | #include <stdlib.h>␊ |
| 10 | #include <string.h>␊ |
| 11 | ␊ |
| 12 | extern void memswap(void *m1, void *m2, size_t n);␊ |
| 13 | ␊ |
| 14 | static inline size_t newgap(size_t gap)␊ |
| 15 | {␊ |
| 16 | ␉gap = (gap * 10) / 13;␊ |
| 17 | ␉if (gap == 9 || gap == 10)␊ |
| 18 | ␉␉gap = 11;␊ |
| 19 | ␊ |
| 20 | ␉if (gap < 1)␊ |
| 21 | ␉␉gap = 1;␊ |
| 22 | ␉return gap;␊ |
| 23 | }␊ |
| 24 | ␊ |
| 25 | void qsort(void *base, size_t nmemb, size_t size,␊ |
| 26 | ␉ int (*compar) (const void *, const void *))␊ |
| 27 | {␊ |
| 28 | ␉size_t gap = nmemb;␊ |
| 29 | ␉size_t i, j;␊ |
| 30 | ␉char *p1, *p2;␊ |
| 31 | ␉int swapped;␊ |
| 32 | ␊ |
| 33 | ␉if (!nmemb)␊ |
| 34 | ␉␉return;␊ |
| 35 | ␊ |
| 36 | ␉do {␊ |
| 37 | ␉␉gap = newgap(gap);␊ |
| 38 | ␉␉swapped = 0;␊ |
| 39 | ␊ |
| 40 | ␉␉for (i = 0, p1 = base; i < nmemb - gap; i++, p1 += size) {␊ |
| 41 | ␉␉␉j = i + gap;␊ |
| 42 | ␉␉␉if (compar(p1, p2 = (char *)base + j * size) > 0) {␊ |
| 43 | ␉␉␉␉memswap(p1, p2, size);␊ |
| 44 | ␉␉␉␉swapped = 1;␊ |
| 45 | ␉␉␉}␊ |
| 46 | ␉␉}␊ |
| 47 | ␉} while (gap > 1 || swapped);␊ |
| 48 | }␊ |
| 49 | |
