|
0
|
1 #include "sort.h"
|
|
|
2
|
|
|
3 #define SWAP_GRAY(A, B) {gray t = A; A = B; B = t;}
|
|
|
4
|
|
|
5 /*
|
|
|
6 * quicksort-alike, from the EMX library (emx/src/lib/misc/qsort.c)
|
|
|
7 * by Eberhard Mattes
|
|
|
8 *
|
|
|
9 * sort() is not stable, the order of equal elements is not defined
|
|
|
10 */
|
|
|
11
|
|
|
12 void _sort_grays(gray *l, gray *r) {
|
|
|
13 gray *i;
|
|
|
14 gray *j;
|
|
|
15 gray *x;
|
|
|
16
|
|
|
17 redo:
|
|
|
18 i = l;
|
|
|
19 j = r;
|
|
|
20 x = l + sizeof(gray) * (((r-l) / sizeof(gray)) / 2);
|
|
|
21
|
|
|
22 do {
|
|
|
23 while (i != x && *i < *x)
|
|
|
24 i++;
|
|
|
25 while (j != x && *j > *x)
|
|
|
26 j--;
|
|
|
27 if (i < j) {
|
|
|
28 SWAP_GRAY(*i, *j);
|
|
|
29 if (x == i)
|
|
|
30 x = j;
|
|
|
31 else if (x == j)
|
|
|
32 x = i;
|
|
|
33 }
|
|
|
34 if (i <= j) {
|
|
|
35 i++;
|
|
|
36 if (j > l)
|
|
|
37 j--;
|
|
|
38 }
|
|
|
39 } while (i <= j);
|
|
|
40
|
|
|
41 if (j-l < r-i) {
|
|
|
42 if (l < j)
|
|
|
43 _sort_grays(l, j);
|
|
|
44 if (i < r) {
|
|
|
45 l = i;
|
|
|
46 goto redo;
|
|
|
47 }
|
|
|
48 }
|
|
|
49 else {
|
|
|
50 if (i < r)
|
|
|
51 _sort_grays(i, r);
|
|
|
52 if (l < j) {
|
|
|
53 r = j;
|
|
|
54 goto redo;
|
|
|
55 }
|
|
|
56 }
|
|
|
57 }
|
|
|
58
|
|
|
59 void sort_grays(gray a[], int n) {
|
|
|
60 if (n > 1)
|
|
|
61 _sort_grays(&a[0], &a[n-1]);
|
|
|
62 }
|
|
|
63
|
|
|
64 /*
|
|
|
65 * select_largest(), from the Numeric Recipes in C, Chapter 8, p. 344,
|
|
|
66 * see http://www.nr.com
|
|
|
67 *
|
|
|
68 * returns in largest[0..m-1] the largest m elements of array[0..n-1]
|
|
|
69 * with largest[0] guaranteed to be the mth largest element; largest[] is
|
|
|
70 * not sorted; the array[] is not altered; this function should be used
|
|
|
71 * only when m << n
|
|
|
72 */
|
|
|
73
|
|
|
74 void select_largest_grays(gray array[], int n, int m, gray largest[]) {
|
|
|
75 int i, j, k;
|
|
|
76
|
|
|
77 if (m <= 0 || m > n/2)
|
|
|
78 return;
|
|
|
79
|
|
|
80 for (i = 0; i < m; i++)
|
|
|
81 largest[i] = array[i];
|
|
|
82 sort_grays(largest, m);
|
|
|
83
|
|
|
84 for (i = m; i < n; i++) {
|
|
|
85 if (array[i] > largest[0]) {
|
|
|
86 largest[0] = array[i];
|
|
|
87 j = 0;
|
|
|
88 k = 1;
|
|
|
89 while (k < m) {
|
|
|
90 if (k < m-1 && largest[k] > largest[k+1])
|
|
|
91 k++;
|
|
|
92 if (largest[j] <= largest[k])
|
|
|
93 break;
|
|
|
94 SWAP_GRAY(largest[k], largest[j]);
|
|
|
95 j = k;
|
|
|
96 k = k << 1;
|
|
|
97 }
|
|
|
98 }
|
|
|
99 }
|
|
|
100 }
|
|
|
101
|
|
|
102 #define SWAP_DOUBLE(A, B) {double t = A; A = B; B = t;}
|
|
|
103
|
|
|
104 void _sort_coeffs(double *l, double *r) {
|
|
|
105 double *i;
|
|
|
106 double *j;
|
|
|
107 double *x;
|
|
|
108
|
|
|
109 redo:
|
|
|
110 i = l;
|
|
|
111 j = r;
|
|
|
112 x = l + sizeof(double) * (((r-l) / sizeof(double)) / 2);
|
|
|
113
|
|
|
114 do {
|
|
|
115 while (i != x && *i < *x)
|
|
|
116 i++;
|
|
|
117 while (j != x && *j > *x)
|
|
|
118 j--;
|
|
|
119 if (i < j) {
|
|
|
120 SWAP_DOUBLE(*i, *j);
|
|
|
121 if (x == i)
|
|
|
122 x = j;
|
|
|
123 else if (x == j)
|
|
|
124 x = i;
|
|
|
125 }
|
|
|
126 if (i <= j) {
|
|
|
127 i++;
|
|
|
128 if (j > l)
|
|
|
129 j--;
|
|
|
130 }
|
|
|
131 } while (i <= j);
|
|
|
132
|
|
|
133 if (j-l < r-i) {
|
|
|
134 if (l < j)
|
|
|
135 _sort_coeffs(l, j);
|
|
|
136 if (i < r) {
|
|
|
137 l = i;
|
|
|
138 goto redo;
|
|
|
139 }
|
|
|
140 }
|
|
|
141 else {
|
|
|
142 if (i < r)
|
|
|
143 _sort_coeffs(i, r);
|
|
|
144 if (l < j) {
|
|
|
145 r = j;
|
|
|
146 goto redo;
|
|
|
147 }
|
|
|
148 }
|
|
|
149 }
|
|
|
150
|
|
|
151 void sort_coeffs(double a[], int n) {
|
|
|
152 if (n > 1)
|
|
|
153 _sort_coeffs(&a[0], &a[n-1]);
|
|
|
154 }
|
|
|
155
|
|
|
156 void select_largest_coeffs(double array[], int n, int m, double largest[]) {
|
|
|
157 int i, j, k;
|
|
|
158
|
|
|
159 if (m <= 0 || m > n/2)
|
|
|
160 return;
|
|
|
161
|
|
|
162 for (i = 0; i < m; i++)
|
|
|
163 largest[i] = array[i];
|
|
|
164 sort_coeffs(largest, m);
|
|
|
165
|
|
|
166 for (i = m; i < n; i++) {
|
|
|
167 if (array[i] > largest[0]) {
|
|
|
168 largest[0] = array[i];
|
|
|
169 j = 0;
|
|
|
170 k = 1;
|
|
|
171 while (k < m) {
|
|
|
172 if (k < m-1 && largest[k] > largest[k+1])
|
|
|
173 k++;
|
|
|
174 if (largest[j] <= largest[k])
|
|
|
175 break;
|
|
|
176 SWAP_DOUBLE(largest[k], largest[j]);
|
|
|
177 j = k;
|
|
|
178 k = k << 1;
|
|
|
179 }
|
|
|
180 }
|
|
|
181 }
|
|
|
182 }
|
|
|
183
|
|
|
184
|
