Root/
| Source at commit 1146 created 12 years 10 months ago. By azimutz, Sync with trunk (r1145). Add nVidia dev id's, 0DF4 for "GeForce GT 450M" (issue 99) and 1251 for "GeForce GTX 560M" (thanks to oSxFr33k for testing). | |
|---|---|
| 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 | |
