Mercurial > vba-linux

comparison src/win32/7zip/7z/C/Sort.c @ 1:f9f4f1b99eed

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
importing src directory
author Robert McIntyre <rlm@mit.edu>
date Sat, 03 Mar 2012 10:31:27 -0600
parents
children
comparison
equal deleted inserted replaced
0:8ced16adf2e1 1:f9f4f1b99eed
1 /* Sort.c -- Sort functions
2 2008-08-17
3 Igor Pavlov
4 Public domain */
5
6 #include "Sort.h"
7
8 #define HeapSortDown(p, k, size, temp) \
9 { for (;;) { \
10 UInt32 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
17 void HeapSort(UInt32 *p, UInt32 size)
18 {
19 if (size <= 1)
20 return;
21 p--;
22 {
23 UInt32 i = size / 2;
24 do
25 {
26 UInt32 temp = p[i];
27 UInt32 k = i;
28 HeapSortDown(p, k, size, temp)
29 }
30 while (--i != 0);
31 }
32 /*
33 do
34 {
35 UInt32 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 UInt32 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
63 /*
64 #define HeapSortRefDown(p, vals, n, size, temp) \
65 { UInt32 k = n; UInt32 val = vals[temp]; for (;;) { \
66 UInt32 s = (k << 1); \
67 if (s > size) break; \
68 if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
69 if (val >= vals[p[s]]) break; \
70 p[k] = p[s]; k = s; \
71 } p[k] = temp; }
72
73 void HeapSortRef(UInt32 *p, UInt32 *vals, UInt32 size)
74 {
75 if (size <= 1)
76 return;
77 p--;
78 {
79 UInt32 i = size / 2;
80 do
81 {
82 UInt32 temp = p[i];
83 HeapSortRefDown(p, vals, i, size, temp);
84 }
85 while (--i != 0);
86 }
87 do
88 {
89 UInt32 temp = p[size];
90 p[size--] = p[1];
91 HeapSortRefDown(p, vals, 1, size, temp);
92 }
93 while (size > 1);
94 }
95 */