Median.h

00001 /*
00002       This file is part of Smoothie (http://smoothieware.org/). The motion control part is heavily based on Grbl (https://github.com/simen/grbl).
00003       Smoothie is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
00004       Smoothie is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
00005       You should have received a copy of the GNU General Public License along with Smoothie. If not, see <http://www.gnu.org/licenses/>.
00006 */
00007 
00008 template <typename T>
00009 void split(T data[], unsigned int n, T x, unsigned int& i, unsigned int& j)
00010 {
00011   do {
00012     while (data[i] < x) i++;
00013     while (x < data[j]) j--;
00014 
00015     if (i <= j) {
00016       T ii = data[i];
00017       data[i] = data[j];
00018       data[j] = ii;
00019       i++; j--;
00020     }
00021   } while (i <= j);
00022 }
00023 
00024 // C.A.R. Hoare's Quick Median
00025 template <typename T>
00026 unsigned int quick_median(T data[], unsigned int n)
00027 {
00028   unsigned int l = 0, r = n-1, k = n/2;
00029   while (l < r) {
00030     T x = data[k];
00031     unsigned int i = l, j = r;
00032     split(data, n, x, i, j);
00033     if (j < k) l = i;
00034     if (k < i) r = j;
00035   }
00036   return k;
00037 }