1 /* Sort.c -- Sort functions
\r
2 2014-04-05 : Igor Pavlov : Public domain */
\r
8 #define HeapSortDown(p, k, size, temp) \
\r
10 size_t s = (k << 1); \
\r
11 if (s > size) break; \
\r
12 if (s < size && p[s + 1] > p[s]) s++; \
\r
13 if (temp >= p[s]) break; \
\r
14 p[k] = p[s]; k = s; \
\r
17 void HeapSort(UInt32 *p, size_t size)
\r
23 size_t i = size / 2;
\r
28 HeapSortDown(p, k, size, temp)
\r
36 UInt32 temp = p[size];
\r
38 HeapSortDown(p, k, size, temp)
\r
44 UInt32 temp = p[size];
\r
45 size_t k = (p[3] > p[2]) ? 3 : 2;
\r
48 HeapSortDown(p, k, size, temp)
\r
51 UInt32 temp = p[size];
\r
53 if (size > 2 && p[2] < temp)
\r
63 void HeapSort64(UInt64 *p, size_t size)
\r
69 size_t i = size / 2;
\r
74 HeapSortDown(p, k, size, temp)
\r
82 UInt64 temp = p[size];
\r
84 HeapSortDown(p, k, size, temp)
\r
90 UInt64 temp = p[size];
\r
91 size_t k = (p[3] > p[2]) ? 3 : 2;
\r
94 HeapSortDown(p, k, size, temp)
\r
97 UInt64 temp = p[size];
\r
99 if (size > 2 && p[2] < temp)
\r
110 #define HeapSortRefDown(p, vals, n, size, temp) \
\r
111 { size_t k = n; UInt32 val = vals[temp]; for (;;) { \
\r
112 size_t s = (k << 1); \
\r
113 if (s > size) break; \
\r
114 if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
\r
115 if (val >= vals[p[s]]) break; \
\r
116 p[k] = p[s]; k = s; \
\r
119 void HeapSortRef(UInt32 *p, UInt32 *vals, size_t size)
\r
125 size_t i = size / 2;
\r
128 UInt32 temp = p[i];
\r
129 HeapSortRefDown(p, vals, i, size, temp);
\r
135 UInt32 temp = p[size];
\r
137 HeapSortRefDown(p, vals, 1, size, temp);
\r