MythTV  master
quickselect.c
Go to the documentation of this file.
1 /*
2  * http://ndevilla.free.fr/median/median/src/quickselect.c
3  *
4  * This Quickselect routine is based on the algorithm described in
5  * "Numerical recipes in C", Second Edition,
6  * Cambridge University Press, 1992, Section 8.5, ISBN 0-521-43108-5
7  * This code by Nicolas Devillard - 1998. Public domain.
8  */
9 
10 #include "quickselect.h"
11 
12 #define ELEM_SWAP(a,b) { register unsigned char t=(a);(a)=(b);(b)=t; }
13 
14 unsigned char
15 quick_select(unsigned char *arr, int nelems, int select)
16 {
17  int low = 0;
18  int high = nelems - 1;
19 
20  for (;;) {
21  if (high <= low) /* One element only */
22  return arr[select];
23 
24  if (high == low + 1) { /* Two elements only */
25  if (arr[low] > arr[high])
26  ELEM_SWAP(arr[low], arr[high]);
27  return arr[select];
28  }
29 
30  /* Find median of low, middle and high items; swap into position low */
31  int middle = (low + high) / 2;
32  if (arr[middle] > arr[high]) ELEM_SWAP(arr[middle], arr[high]);
33  if (arr[low] > arr[high]) ELEM_SWAP(arr[low], arr[high]);
34  if (arr[middle] > arr[low]) ELEM_SWAP(arr[middle], arr[low]);
35 
36  /* Swap low item (now in position middle) into position (low+1) */
37  ELEM_SWAP(arr[middle], arr[low+1]);
38 
39  /* Nibble from each end towards middle, swapping items when stuck */
40  int ll = low + 1;
41  int hh = high;
42  for (;;) {
43  do ll++; while (arr[low] > arr[ll]);
44  do hh--; while (arr[hh] > arr[low]);
45 
46  if (hh < ll)
47  break;
48 
49  ELEM_SWAP(arr[ll], arr[hh]);
50  }
51 
52  /* Swap middle item (in position low) back into correct position */
53  ELEM_SWAP(arr[low], arr[hh]);
54 
55  /* Re-set active partition */
56  if (hh <= select)
57  low = ll;
58  if (hh >= select)
59  high = hh - 1;
60  }
61 }
62 
63 #undef ELEM_SWAP
64 
65 unsigned char
66 quick_select_median(unsigned char *arr, int nelems)
67 {
68  return quick_select(arr, nelems, (nelems - 1) / 2);
69 }
70 
71 #define ELEM_SWAP(a,b) { register unsigned short t=(a);(a)=(b);(b)=t; }
72 
73 unsigned short
74 quick_select_ushort(unsigned short *arr, int nelems, int select)
75 {
76  int low = 0;
77  int high = nelems - 1;
78 
79  for (;;) {
80  if (high <= low) /* One element only */
81  return arr[select];
82 
83  if (high == low + 1) { /* Two elements only */
84  if (arr[low] > arr[high])
85  ELEM_SWAP(arr[low], arr[high]);
86  return arr[select];
87  }
88 
89  /* Find median of low, middle and high items; swap into position low */
90  int middle = (low + high) / 2;
91  if (arr[middle] > arr[high]) ELEM_SWAP(arr[middle], arr[high]);
92  if (arr[low] > arr[high]) ELEM_SWAP(arr[low], arr[high]);
93  if (arr[middle] > arr[low]) ELEM_SWAP(arr[middle], arr[low]);
94 
95  /* Swap low item (now in position middle) into position (low+1) */
96  ELEM_SWAP(arr[middle], arr[low+1]);
97 
98  /* Nibble from each end towards middle, swapping items when stuck */
99  int ll = low + 1;
100  int hh = high;
101  for (;;) {
102  do ll++; while (arr[low] > arr[ll]);
103  do hh--; while (arr[hh] > arr[low]);
104 
105  if (hh < ll)
106  break;
107 
108  ELEM_SWAP(arr[ll], arr[hh]);
109  }
110 
111  /* Swap middle item (in position low) back into correct position */
112  ELEM_SWAP(arr[low], arr[hh]);
113 
114  /* Re-set active partition */
115  if (hh <= select)
116  low = ll;
117  if (hh >= select)
118  high = hh - 1;
119  }
120 }
121 
122 #undef ELEM_SWAP
123 
124 unsigned short
125 quick_select_median_ushort(unsigned short *arr, int nelems)
126 {
127  return quick_select_ushort(arr, nelems, (nelems - 1) / 2);
128 }
129 
130 #define ELEM_SWAP(a,b) { register float t=(a);(a)=(b);(b)=t; }
131 
132 float
133 quick_select_float(float *arr, int nelems, int select)
134 {
135  int low = 0;
136  int high = nelems - 1;
137 
138  for (;;) {
139  if (high <= low) /* One element only */
140  return arr[select];
141 
142  if (high == low + 1) { /* Two elements only */
143  if (arr[low] > arr[high])
144  ELEM_SWAP(arr[low], arr[high]);
145  return arr[select];
146  }
147 
148  /* Find median of low, middle and high items; swap into position low */
149  int middle = (low + high) / 2;
150  if (arr[middle] > arr[high]) ELEM_SWAP(arr[middle], arr[high]);
151  if (arr[low] > arr[high]) ELEM_SWAP(arr[low], arr[high]);
152  if (arr[middle] > arr[low]) ELEM_SWAP(arr[middle], arr[low]);
153 
154  /* Swap low item (now in position middle) into position (low+1) */
155  ELEM_SWAP(arr[middle], arr[low+1]);
156 
157  /* Nibble from each end towards middle, swapping items when stuck */
158  int ll = low + 1;
159  int hh = high;
160  for (;;) {
161  do ll++; while (arr[low] > arr[ll]);
162  do hh--; while (arr[hh] > arr[low]);
163 
164  if (hh < ll)
165  break;
166 
167  ELEM_SWAP(arr[ll], arr[hh]);
168  }
169 
170  /* Swap middle item (in position low) back into correct position */
171  ELEM_SWAP(arr[low], arr[hh]);
172 
173  /* Re-set active partition */
174  if (hh <= select)
175  low = ll;
176  if (hh >= select)
177  high = hh - 1;
178  }
179 }
180 
181 float
182 quick_select_median_float(float *arr, int nelems)
183 {
184  return quick_select_float(arr, nelems, (nelems - 1) / 2);
185 }
186 
187 #undef ELEM_SWAP
188 
189 /* vim: set expandtab tabstop=4 shiftwidth=4: */
#define ELEM_SWAP(a, b)
Definition: quickselect.c:130
unsigned short quick_select_median_ushort(unsigned short *arr, int nelems)
Definition: quickselect.c:125
float quick_select_median_float(float *arr, int nelems)
Definition: quickselect.c:182
float quick_select_float(float *arr, int nelems, int select)
Definition: quickselect.c:133
unsigned short quick_select_ushort(unsigned short *arr, int nelems, int select)
Definition: quickselect.c:74
unsigned char quick_select_median(unsigned char *arr, int nelems)
Definition: quickselect.c:66
unsigned char quick_select(unsigned char *arr, int nelems, int select)
Definition: quickselect.c:15