test-median.c

   1 //#include "sparrow.h"
   2 #include <string.h>
   3 #include <stdio.h>
   4 #include <stdint.h>
   5
   6 int median(int *a, unsigned int n)
   7 {
   8   int middle = n / 2;
   9   int i, j;  /* working bottom, top */
  10   int bottom = 0; /* window bottom */
  11   int top = n - 1; /*window top */
  12
  13   if (! (n & 1)){ /*return lower of 2 centre values */
  14     middle--;
  15   }
  16
  17   while (bottom < top) {
  18     i = bottom;
  19     j = top;
  20     do {
  21       while (a[i] < a[middle]){
  22         i++;
  23       }
  24       while (a[middle] < a[j]){
  25         j--;
  26       }
  27       if (i <= j){
  28         int tmp = a[i];
  29         a[i] = a[j];
  30         a[j] = tmp;
  31         i++;
  32         j--;
  33       }
  34     } while (i <= j);
  35
  36     if (j < middle){
  37       bottom = i;
  38     }
  39     if (middle < i){
  40       top = j;
  41     }
  42   }
  43   return a[middle];
  44 }
  45
  46 int sort_median(int *a, int n)
  47 {
  48   int i, j;
  49   /*stupid sort, but n is very small*/
  50   for (i = 0; i <  n; i++){
  51     for (j = i + 1; j < n; j++){
  52       if (a[i] > a[j]){
  53         int tmp = a[j];
  54         a[j] = a[i];
  55         a[i] = tmp;
  56       }
  57     }
  58   }
  59   int middle = n >> 1;
  60   int answer = a[middle];
  61
  62   if ((n & 1) == 0){
  63     answer += a[middle - 1];
  64     answer /= 2;
  65   }
  66   return answer;
  67 }
  68
  69
  70
  71 int main(int argc, char **argv)
  72 {
  73   int a[] = {1, 3, 4, -3231, 5, 99, 2};
  74   int b[] = {1, 3, 4, 5, 99, 2, 88, 88, 88, 55, 6};
  75   int c[] = { -1, -4, 0, 3};
  76   int d[] = {3, 5};
  77
  78   printf("%d\n", median(a, sizeof(a) / sizeof(int)));
  79   printf("%d\n", median(b, sizeof(b) / sizeof(int)));
  80   printf("%d\n", median(c, sizeof(c) / sizeof(int)));
  81   printf("%d\n", median(d, sizeof(d) / sizeof(int)));
  82
  83   printf("%d\n", sort_median(a, sizeof(a) / sizeof(int)));
  84   printf("%d\n", sort_median(b, sizeof(b) / sizeof(int)));
  85   printf("%d\n", sort_median(c, sizeof(c) / sizeof(int)));
  86   printf("%x\n", sort_median(d, sizeof(d) / sizeof(int)));
  87 }