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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
/* $Id$ */
/** @file sort_func.hpp Functions related to sorting operations. */
#ifndef SORT_FUNC_HPP
#define SORT_FUNC_HPP
#include <stdlib.h>
#include "math_func.hpp"
#include "mem_func.hpp"
/**
* Type safe qsort()
*
* @todo replace the normal qsort with this one
* @note Use this sort for irregular sorted data.
*
* @param base Pointer to the first element of the array to be sorted.
* @param num Number of elements in the array pointed by base.
* @param comparator Function that compares two elements.
* @param desc Sort descending.
*/
template <typename T>
static FORCEINLINE void QSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)
{
if (num < 2) return;
qsort(base, num, sizeof(T), (int (CDECL *)(const void *, const void *))comparator);
if (desc) MemReverseT(base, num);
}
/**
* Type safe Gnome Sort.
*
* This is a slightly modifyied Gnome search. The basic
* Gnome search trys to sort already sorted list parts.
* The modification skips these.
*
* @note Use this sort for presorted / regular sorted data.
*
* @param base Pointer to the first element of the array to be sorted.
* @param num Number of elements in the array pointed by base.
* @param comparator Function that compares two elements.
* @param desc Sort descending.
*/
template <typename T>
static inline void GSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)
{
if (num < 2) return;
assert(base != NULL);
assert(comparator != NULL);
T *a = base;
T *b = base + 1;
uint offset = 0;
while (num > 1) {
const int diff = comparator(a, b);
if ((!desc && diff <= 0) || (desc && diff >= 0)) {
if (offset != 0) {
/* Jump back to the last direction switch point */
a += offset;
b += offset;
offset = 0;
continue;
}
a++;
b++;
num--;
} else {
Swap(*a, *b);
if (a == base) continue;
a--;
b--;
offset++;
}
}
}
#endif /* SORT_FUNC_HPP */
|
