annotate Meerwald/sort.c @ 3:acb6967ee76d

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

Repositories maintained by Peter Meerwald, pmeerw@pmeerw.net.