Debian Codegraph @

libsrc/math/heapsort.h

raw
1 /* code from cpl 6.6
2 * changes: renames and sorts the input using the pattern */
3 void ADDTYPE(heapSort)(int n, MIDAS_TYPE self[], int sort_pattern[])
4 {
5 int i;
6 int reverse = 0;
7
8 if (n == 0) return;
9
10 /* by zero indexing, but contents are by one, added later */
11 for (i = 0; i < n; i++) {
12 sort_pattern[i] = i;
13 }
14
15 /*
16 * Heap sort
17 */
18 for (i = n / 2 - 1; i >= 0; i--) {
19 int done = 0;
20 int root = i;
21 int bottom = n - 1;
22
23 while ((root*2 + 1 <= bottom) && (!done)) {
24 int child = root*2 + 1;
25
26 if (child+1 <= bottom) {
27 if ((!reverse && MIDAS_TOOLS_SORT_LT(
28 self[sort_pattern[child]],
29 self[sort_pattern[child + 1]]))
30 ||
31 (reverse && MIDAS_TOOLS_SORT_LT(
32 self[sort_pattern[child + 1]],
33 self[sort_pattern[child]]))
34 ) {
35 child += 1;
36 }
37 }
38
39 if ((!reverse && MIDAS_TOOLS_SORT_LT(
40 self[sort_pattern[root]],
41 self[sort_pattern[child]]))
42 ||
43 (reverse && MIDAS_TOOLS_SORT_LT(
44 self[sort_pattern[child]],
45 self[sort_pattern[root]]))
46 ) {
47 MIDAS_INT_SWAP(sort_pattern[root], sort_pattern[child]);
48 root = child;
49 }
50 else {
51 done = 1;
52 }
53 }
54 }
55
56 for (i = n - 1; i >= 1; i--) {
57 int done = 0;
58 int root = 0;
59 int bottom = i - 1;
60 MIDAS_INT_SWAP(sort_pattern[0], sort_pattern[i]);
61
62 while ((root*2 + 1 <= bottom) && (!done)) {
63 int child = root*2 + 1;
64
65 if (child+1 <= bottom) {
66 if ((!reverse && MIDAS_TOOLS_SORT_LT(
67 self[sort_pattern[child]],
68 self[sort_pattern[child + 1]]))
69 ||
70 (reverse && MIDAS_TOOLS_SORT_LT(
71 self[sort_pattern[child + 1]],
72 self[sort_pattern[child]]))
73 ) {
74 child += 1;
75 }
76 }
77 if ((!reverse && MIDAS_TOOLS_SORT_LT(
78 self[sort_pattern[root]],
79 self[sort_pattern[child]]))
80 ||
81 (reverse && MIDAS_TOOLS_SORT_LT(
82 self[sort_pattern[child]],
83 self[sort_pattern[root]]))
84 ) {
85 MIDAS_INT_SWAP(sort_pattern[root], sort_pattern[child]);
86 root = child;
87 }
88 else {
89 done = 1;
90 }
91 }
92 }
93
94 /* sort data array */
95 MIDAS_TYPE * nself = malloc(sizeof(*nself) * n);
96 memcpy(nself, self, sizeof(*nself) * n);
97 for (i = 0; i < n; i++) {
98 self[i] = nself[sort_pattern[i]];
99 }
100 free(nself);
101
102 /* change pattern content to by one indexing */
103 for (i = 0; i < n; i++) {
104 sort_pattern[i] += 1;
105 }
106
107 return;
108 }