1 /* Sort.c -- Sort functions
2 2014-04-05 : Igor Pavlov : Public domain */
3
4 #include "Precomp.h"
5
6 #include "Sort.h"
7
8 #define HeapSortDown(p, k, size, temp) \
9 { for (;;) { \
10 size_t s = (k << 1); \
11 if (s > size) break; \
12 if (s < size && p[s + 1] > p[s]) s++; \
13 if (temp >= p[s]) break; \
14 p[k] = p[s]; k = s; \
15 } p[k] = temp; }
16
HeapSort(UInt32 * p,size_t size)17 void HeapSort(UInt32 *p, size_t size)
18 {
19 if (size <= 1)
20 return;
21 p--;
22 {
23 size_t i = size / 2;
24 do
25 {
26 UInt32 temp = p[i];
27 size_t k = i;
28 HeapSortDown(p, k, size, temp)
29 }
30 while (--i != 0);
31 }
32 /*
33 do
34 {
35 size_t k = 1;
36 UInt32 temp = p[size];
37 p[size--] = p[1];
38 HeapSortDown(p, k, size, temp)
39 }
40 while (size > 1);
41 */
42 while (size > 3)
43 {
44 UInt32 temp = p[size];
45 size_t k = (p[3] > p[2]) ? 3 : 2;
46 p[size--] = p[1];
47 p[1] = p[k];
48 HeapSortDown(p, k, size, temp)
49 }
50 {
51 UInt32 temp = p[size];
52 p[size] = p[1];
53 if (size > 2 && p[2] < temp)
54 {
55 p[1] = p[2];
56 p[2] = temp;
57 }
58 else
59 p[1] = temp;
60 }
61 }
62
HeapSort64(UInt64 * p,size_t size)63 void HeapSort64(UInt64 *p, size_t size)
64 {
65 if (size <= 1)
66 return;
67 p--;
68 {
69 size_t i = size / 2;
70 do
71 {
72 UInt64 temp = p[i];
73 size_t k = i;
74 HeapSortDown(p, k, size, temp)
75 }
76 while (--i != 0);
77 }
78 /*
79 do
80 {
81 size_t k = 1;
82 UInt64 temp = p[size];
83 p[size--] = p[1];
84 HeapSortDown(p, k, size, temp)
85 }
86 while (size > 1);
87 */
88 while (size > 3)
89 {
90 UInt64 temp = p[size];
91 size_t k = (p[3] > p[2]) ? 3 : 2;
92 p[size--] = p[1];
93 p[1] = p[k];
94 HeapSortDown(p, k, size, temp)
95 }
96 {
97 UInt64 temp = p[size];
98 p[size] = p[1];
99 if (size > 2 && p[2] < temp)
100 {
101 p[1] = p[2];
102 p[2] = temp;
103 }
104 else
105 p[1] = temp;
106 }
107 }
108
109 /*
110 #define HeapSortRefDown(p, vals, n, size, temp) \
111 { size_t k = n; UInt32 val = vals[temp]; for (;;) { \
112 size_t s = (k << 1); \
113 if (s > size) break; \
114 if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
115 if (val >= vals[p[s]]) break; \
116 p[k] = p[s]; k = s; \
117 } p[k] = temp; }
118
119 void HeapSortRef(UInt32 *p, UInt32 *vals, size_t size)
120 {
121 if (size <= 1)
122 return;
123 p--;
124 {
125 size_t i = size / 2;
126 do
127 {
128 UInt32 temp = p[i];
129 HeapSortRefDown(p, vals, i, size, temp);
130 }
131 while (--i != 0);
132 }
133 do
134 {
135 UInt32 temp = p[size];
136 p[size--] = p[1];
137 HeapSortRefDown(p, vals, 1, size, temp);
138 }
139 while (size > 1);
140 }
141 */
142