|
rlm@1
|
1 /* Sort.c -- Sort functions
|
|
rlm@1
|
2 2008-08-17
|
|
rlm@1
|
3 Igor Pavlov
|
|
rlm@1
|
4 Public domain */
|
|
rlm@1
|
5
|
|
rlm@1
|
6 #include "Sort.h"
|
|
rlm@1
|
7
|
|
rlm@1
|
8 #define HeapSortDown(p, k, size, temp) \
|
|
rlm@1
|
9 { for (;;) { \
|
|
rlm@1
|
10 UInt32 s = (k << 1); \
|
|
rlm@1
|
11 if (s > size) break; \
|
|
rlm@1
|
12 if (s < size && p[s + 1] > p[s]) s++; \
|
|
rlm@1
|
13 if (temp >= p[s]) break; \
|
|
rlm@1
|
14 p[k] = p[s]; k = s; \
|
|
rlm@1
|
15 } p[k] = temp; }
|
|
rlm@1
|
16
|
|
rlm@1
|
17 void HeapSort(UInt32 *p, UInt32 size)
|
|
rlm@1
|
18 {
|
|
rlm@1
|
19 if (size <= 1)
|
|
rlm@1
|
20 return;
|
|
rlm@1
|
21 p--;
|
|
rlm@1
|
22 {
|
|
rlm@1
|
23 UInt32 i = size / 2;
|
|
rlm@1
|
24 do
|
|
rlm@1
|
25 {
|
|
rlm@1
|
26 UInt32 temp = p[i];
|
|
rlm@1
|
27 UInt32 k = i;
|
|
rlm@1
|
28 HeapSortDown(p, k, size, temp)
|
|
rlm@1
|
29 }
|
|
rlm@1
|
30 while (--i != 0);
|
|
rlm@1
|
31 }
|
|
rlm@1
|
32 /*
|
|
rlm@1
|
33 do
|
|
rlm@1
|
34 {
|
|
rlm@1
|
35 UInt32 k = 1;
|
|
rlm@1
|
36 UInt32 temp = p[size];
|
|
rlm@1
|
37 p[size--] = p[1];
|
|
rlm@1
|
38 HeapSortDown(p, k, size, temp)
|
|
rlm@1
|
39 }
|
|
rlm@1
|
40 while (size > 1);
|
|
rlm@1
|
41 */
|
|
rlm@1
|
42 while (size > 3)
|
|
rlm@1
|
43 {
|
|
rlm@1
|
44 UInt32 temp = p[size];
|
|
rlm@1
|
45 UInt32 k = (p[3] > p[2]) ? 3 : 2;
|
|
rlm@1
|
46 p[size--] = p[1];
|
|
rlm@1
|
47 p[1] = p[k];
|
|
rlm@1
|
48 HeapSortDown(p, k, size, temp)
|
|
rlm@1
|
49 }
|
|
rlm@1
|
50 {
|
|
rlm@1
|
51 UInt32 temp = p[size];
|
|
rlm@1
|
52 p[size] = p[1];
|
|
rlm@1
|
53 if (size > 2 && p[2] < temp)
|
|
rlm@1
|
54 {
|
|
rlm@1
|
55 p[1] = p[2];
|
|
rlm@1
|
56 p[2] = temp;
|
|
rlm@1
|
57 }
|
|
rlm@1
|
58 else
|
|
rlm@1
|
59 p[1] = temp;
|
|
rlm@1
|
60 }
|
|
rlm@1
|
61 }
|
|
rlm@1
|
62
|
|
rlm@1
|
63 /*
|
|
rlm@1
|
64 #define HeapSortRefDown(p, vals, n, size, temp) \
|
|
rlm@1
|
65 { UInt32 k = n; UInt32 val = vals[temp]; for (;;) { \
|
|
rlm@1
|
66 UInt32 s = (k << 1); \
|
|
rlm@1
|
67 if (s > size) break; \
|
|
rlm@1
|
68 if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
|
|
rlm@1
|
69 if (val >= vals[p[s]]) break; \
|
|
rlm@1
|
70 p[k] = p[s]; k = s; \
|
|
rlm@1
|
71 } p[k] = temp; }
|
|
rlm@1
|
72
|
|
rlm@1
|
73 void HeapSortRef(UInt32 *p, UInt32 *vals, UInt32 size)
|
|
rlm@1
|
74 {
|
|
rlm@1
|
75 if (size <= 1)
|
|
rlm@1
|
76 return;
|
|
rlm@1
|
77 p--;
|
|
rlm@1
|
78 {
|
|
rlm@1
|
79 UInt32 i = size / 2;
|
|
rlm@1
|
80 do
|
|
rlm@1
|
81 {
|
|
rlm@1
|
82 UInt32 temp = p[i];
|
|
rlm@1
|
83 HeapSortRefDown(p, vals, i, size, temp);
|
|
rlm@1
|
84 }
|
|
rlm@1
|
85 while (--i != 0);
|
|
rlm@1
|
86 }
|
|
rlm@1
|
87 do
|
|
rlm@1
|
88 {
|
|
rlm@1
|
89 UInt32 temp = p[size];
|
|
rlm@1
|
90 p[size--] = p[1];
|
|
rlm@1
|
91 HeapSortRefDown(p, vals, 1, size, temp);
|
|
rlm@1
|
92 }
|
|
rlm@1
|
93 while (size > 1);
|
|
rlm@1
|
94 }
|
|
rlm@1
|
95 */ |
