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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#ifndef ALGDS_SORT_H_
#define ALGDS_SORT_H_
#include <stdlib.h>
#include <string.h>
#include "type_alias.h"
#define QSORT_DEF(T) \
void T##_qsort(T* arr, int n);
#define QSORT_IMPL(T) \
static inline void T##_qsort_swap(T* arr, int lhs, int rhs) { \
if (lhs == rhs) return; \
T buf; \
buf = arr[lhs]; \
arr[lhs] = arr[rhs]; \
arr[rhs] = buf; \
} \
void T##_qsort(T* arr, int n) { \
if (n <= 1) return; \
int pivot = rand() % n; \
T##_qsort_swap(arr, 0, pivot); \
int lp = 1, rp = n-1; \
while (lp < rp) { \
if (T##_cmp(arr[lp], arr[0]) < 0) { \
lp++; \
continue; \
} \
if (T##_cmp(arr[rp], arr[0]) >= 0) { \
rp--; \
continue; \
} \
T##_qsort_swap(arr, lp, rp); \
lp++; \
rp--; \
} \
if (T##_cmp(arr[rp], arr[0]) > 0) rp--; \
T##_qsort_swap(arr, 0, rp); \
T##_qsort(arr, rp); \
T##_qsort(arr+rp+1, n-rp-1); \
}
QSORT_DEF(Int);
QSORT_DEF(Bool);
QSORT_DEF(Long);
QSORT_DEF(Char);
QSORT_DEF(UInt);
QSORT_DEF(ULong);
QSORT_DEF(Double);
QSORT_DEF(Float);
QSORT_DEF(String);
#endif
|
