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