MythTV  master
quickselect.cpp
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 template <typename T>
13 void ELEM_SWAP(T& a, T& b)
14 {
15  T t = a;
16  a = b;
17  b = t;
18 }
19
20 unsigned char
21 quick_select(unsigned char *arr, int nelems, int select)
22 {
23  int low = 0;
24  int high = nelems - 1;
25
26  for (;;) {
27  if (high <= low) /* One element only */
28  return arr[select];
29
30  if (high == low + 1) { /* Two elements only */
31  if (arr[low] > arr[high])
32  ELEM_SWAP(arr[low], arr[high]);
33  return arr[select];
34  }
35
36  /* Find median of low, middle and high items; swap into position low */
37  int middle = (low + high) / 2;
38  if (arr[middle] > arr[high]) ELEM_SWAP(arr[middle], arr[high]);
39  if (arr[low] > arr[high]) ELEM_SWAP(arr[low], arr[high]);
40  if (arr[middle] > arr[low]) ELEM_SWAP(arr[middle], arr[low]);
41
42  /* Swap low item (now in position middle) into position (low+1) */
43  ELEM_SWAP(arr[middle], arr[low+1]);
44
45  /* Nibble from each end towards middle, swapping items when stuck */
46  int ll = low + 1;
47  int hh = high;
48  for (;;) {
49  do ll++; while (arr[low] > arr[ll]);
50  do hh--; while (arr[hh] > arr[low]);
51
52  if (hh < ll)
53  break;
54
55  ELEM_SWAP(arr[ll], arr[hh]);
56  }
57
58  /* Swap middle item (in position low) back into correct position */
59  ELEM_SWAP(arr[low], arr[hh]);
60
61  /* Re-set active partition */
62  if (hh <= select)
63  low = ll;
64  if (hh >= select)
65  high = hh - 1;
66  }
67 }
68
69 unsigned char
70 quick_select_median(unsigned char *arr, int nelems)
71 {
72  return quick_select(arr, nelems, (nelems - 1) / 2);
73 }
74
75 unsigned short
76 quick_select_ushort(unsigned short *arr, int nelems, int select)
77 {
78  int low = 0;
79  int high = nelems - 1;
80
81  for (;;) {
82  if (high <= low) /* One element only */
83  return arr[select];
84
85  if (high == low + 1) { /* Two elements only */
86  if (arr[low] > arr[high])
87  ELEM_SWAP(arr[low], arr[high]);
88  return arr[select];
89  }
90
91  /* Find median of low, middle and high items; swap into position low */
92  int middle = (low + high) / 2;
93  if (arr[middle] > arr[high]) ELEM_SWAP(arr[middle], arr[high]);
94  if (arr[low] > arr[high]) ELEM_SWAP(arr[low], arr[high]);
95  if (arr[middle] > arr[low]) ELEM_SWAP(arr[middle], arr[low]);
96
97  /* Swap low item (now in position middle) into position (low+1) */
98  ELEM_SWAP(arr[middle], arr[low+1]);
99
100  /* Nibble from each end towards middle, swapping items when stuck */
101  int ll = low + 1;
102  int hh = high;
103  for (;;) {
104  do ll++; while (arr[low] > arr[ll]);
105  do hh--; while (arr[hh] > arr[low]);
106
107  if (hh < ll)
108  break;
109
110  ELEM_SWAP(arr[ll], arr[hh]);
111  }
112
113  /* Swap middle item (in position low) back into correct position */
114  ELEM_SWAP(arr[low], arr[hh]);
115
116  /* Re-set active partition */
117  if (hh <= select)
118  low = ll;
119  if (hh >= select)
120  high = hh - 1;
121  }
122 }
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 float
131 quick_select_float(float *arr, int nelems, int select)
132 {
133  int low = 0;
134  int high = nelems - 1;
135
136  for (;;) {
137  if (high <= low) /* One element only */
138  return arr[select];
139
140  if (high == low + 1) { /* Two elements only */
141  if (arr[low] > arr[high])
142  ELEM_SWAP(arr[low], arr[high]);
143  return arr[select];
144  }
145
146  /* Find median of low, middle and high items; swap into position low */
147  int middle = (low + high) / 2;
148  if (arr[middle] > arr[high]) ELEM_SWAP(arr[middle], arr[high]);
149  if (arr[low] > arr[high]) ELEM_SWAP(arr[low], arr[high]);
150  if (arr[middle] > arr[low]) ELEM_SWAP(arr[middle], arr[low]);
151
152  /* Swap low item (now in position middle) into position (low+1) */
153  ELEM_SWAP(arr[middle], arr[low+1]);
154
155  /* Nibble from each end towards middle, swapping items when stuck */
156  int ll = low + 1;
157  int hh = high;
158  for (;;) {
159  do ll++; while (arr[low] > arr[ll]);
160  do hh--; while (arr[hh] > arr[low]);
161
162  if (hh < ll)
163  break;
164
165  ELEM_SWAP(arr[ll], arr[hh]);
166  }
167
168  /* Swap middle item (in position low) back into correct position */
169  ELEM_SWAP(arr[low], arr[hh]);
170
171  /* Re-set active partition */
172  if (hh <= select)
173  low = ll;
174  if (hh >= select)
175  high = hh - 1;
176  }
177 }
178
179 float
180 quick_select_median_float(float *arr, int nelems)
181 {
182  return quick_select_float(arr, nelems, (nelems - 1) / 2);
183 }
184
185 /* vim: set expandtab tabstop=4 shiftwidth=4: */
quick_select_median_float
float quick_select_median_float(float *arr, int nelems)
Definition: quickselect.cpp:180
quick_select_median
unsigned char quick_select_median(unsigned char *arr, int nelems)
Definition: quickselect.cpp:70
quickselect.h
hardwareprofile.i18n.t
t
Definition: i18n.py:36
ELEM_SWAP
void ELEM_SWAP(T &a, T &b)
Definition: quickselect.cpp:13
quick_select_float
float quick_select_float(float *arr, int nelems, int select)
Definition: quickselect.cpp:131
quick_select
unsigned char quick_select(unsigned char *arr, int nelems, int select)
Definition: quickselect.cpp:21
quick_select_median_ushort
unsigned short quick_select_median_ushort(unsigned short *arr, int nelems)
Definition: quickselect.cpp:125
quick_select_ushort
unsigned short quick_select_ushort(unsigned short *arr, int nelems, int select)
Definition: quickselect.cpp:76