Mercurial > hg > wm

comparison Meerwald/sort.c @ 0:be303a3f5ea8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
import
author Peter Meerwald <pmeerw@cosy.sbg.ac.at>
date Sun, 12 Aug 2007 13:14:34 +0200
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:be303a3f5ea8
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

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