median.h

   1 /*
   2  * Based on Nicolas Devillard's work at
   3  *
   4  * http://ndevilla.free.fr/median/median/index.html
   5  * http://ndevilla.free.fr/median/median/src/wirth.c
   6  * ndevilla AT free DOT fr
   7  *
   8  * His header:
   9  *
  10  * Algorithm from N. Wirth's book, implementation by N. Devillard.
  11  * This code in public domain.
  12  */
  13
  14
  15 static inline coord_t
  16 coord_median(coord_t *values, unsigned int n)
  17 {
  18   int middle = n / 2;
  19   int i, j;  /* working bottom, top */
  20   int bottom = 0; /* window bottom */
  21   int top = n - 1; /*window top */
  22
  23   if (! (n & 1)){ /*return lower of 2 centre values */
  24     middle--;
  25   }
  26
  27   while (bottom < top) {
  28     i = bottom;
  29     j = top;
  30     do {
  31       while (values[i] < values[middle]){
  32         i++;
  33       }
  34       while (values[middle] < values[j]){
  35         j--;
  36       }
  37       if (i <= j){
  38         coord_t tmp = values[i];
  39         values[i] = values[j];
  40         values[j] = tmp;
  41         i++;
  42         j--;
  43       }
  44     } while (i <= j);
  45
  46     if (j < middle){
  47       bottom = i;
  48     }
  49     if (middle < i){
  50       top = j;
  51     }
  52   }
  53   return values[middle];
  54 }
  55
  56