blob: a4c881e6f8ab50458b815635a27931bce26f6b08 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#ifndef _AL_ARRAY_SORT_H
#define _AL_ARRAY_SORT_H
#include "lib.h"
/* https://en.wikipedia.org/wiki/Insertion_sort
i ← 1
while i < length(A)
x ← A[i]
j ← i
while j > 0 and A[j-1] > x
A[j] ← A[j-1]
j ← j - 1
end while
A[j] ← x
i ← i + 1
end while
*/
#define AL_INSERSION_SORT(data, type, count, cmp) \
do { \
u32 i = 1, k; \
type x; \
while (i < count) { \
k = i; \
x = (data)[i]; \
while (k > 0 && cmp(&(data)[k - 1], &x) > 0) { \
(data)[k] = (data)[k - 1]; \
k--; \
} \
(data)[k] = x; \
i++; \
} \
} while (0)
#ifdef AL_USE_STDLIB
#define AL_STDLIB_QSORT(data, type, count, cmp) qsort(data, (size_t)count, sizeof(type), cmp)
#endif
#endif // _AL_ARRAY_SORT_H
|