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