home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: Science / Science.zip / fblnk224.zip / median.c < prev    next >
C/C++ Source or Header  |  1999-01-28  |  3KB  |  96 lines
  1. /*  median.c  */
  2. /*  Finds the median of values given in an table without sorting */
  3. /*  the entire table   */
  4. /*  Jure Skvarc, november 1998  */
  5. /*  Parameters: */
  6. /*  a         -- a pointer to the table  */
  7. /*  n         -- number of elements in a table  */
  8. /*  width     -- size of elements in bytes      */
  9. /*  compare   -- the compare function           */
  10. /*  The algorithm:  pick up a random element from the table and */
  11. /*  put all of the elements smaller than it before the elements */
  12. /*  that are bigger.  Than repeat the procedure on the half that contains */
  13. /*  middle element and so on until only the middle element remains  */
  14. #include <stdio.h>
  15. #include <stdlib.h>
  16. #include <malloc.h>
  17.  
  18.  
  19. void
  20. median(void *a, int n, int width, int (*compare)(const void *, const void *))
  21.  
  22. {
  23.   int p, z, i, j, middle, c, q, d;
  24.   void *cel, *ti, *tj, *tempel, *tp, *td;
  25.  
  26.   p = 0;     /*  Lowest index of the subarray that has to be examined  */
  27.   z = n - 1; /*  Highest index of the subarray that has to be examined  */
  28.   if (!(cel = malloc(width))) {
  29.     fprintf(stderr, "Out of memory, function median!\n");
  30.     exit(1);
  31.   }
  32.   if (!(tempel = malloc(width))) {
  33.     fprintf(stderr, "Out of memory, function median!\n");
  34.     exit(1);
  35.   }
  36.   middle = (p + z) / 2; /*  Index of the middle element  */
  37.   do {
  38.     tp = a + width * p;
  39.     /*  Select a random element of the table  */
  40.     /*  and exchange its position with the first element */
  41.     td = a + (d = (p + rand() % (z - p) + 1)) * width;
  42.     memcpy(cel, td, width);
  43.     memcpy(td, tp, width);
  44.     memcpy(tp, cel, width);
  45.     i = p + 1;
  46.     j = z + 1;
  47.     q = 1;
  48.     do {
  49.       ti = a + i * width;
  50.       /*  Find an element in the upper part (lower index) of the array */
  51.       /*  which is bigger or equal than the comparison element  */
  52.       while (i < j && (c = compare(cel, ti)) >= 0) {
  53.     q = q && !c;
  54.     i++;
  55.     ti += width;
  56.       }
  57.       j--;
  58.       tj = a + j * width;
  59.       /*  Find an element in the upper part (higher index) of the array */
  60.       /*  which is smaller than the above found element  */
  61.       while (i < j && compare(cel, tj) < 0) {
  62.     q = 0;
  63.     j--;
  64.     tj -= width;
  65.       }
  66.       if (i < j) {
  67.     /* swap the element positions  */
  68.     memcpy(tempel, ti, width);
  69.     memcpy(ti, tj, width);
  70.     memcpy(tj, tempel, width);
  71.     q = 0;
  72.      i++;
  73.       }
  74.     } while (i < j);  
  75.     /*  Now determine which part of the partially sorted table */
  76.     /*  contains the middle index and set the new lower and upper */
  77.     /*  indices accordingly   */
  78.     i--;
  79.     ti = a + i * width;
  80.     if (i != p) {
  81.       memcpy(tempel, tp, width);
  82.       memcpy(tp, ti, width);
  83.       memcpy(ti, tempel, width);
  84.     }
  85.     if (i > middle) {
  86.       if (i == z) z--;
  87.       else  z = i;
  88.     }
  89.     else p = i + 1;
  90.   } while (p < z && !q);
  91.   free(tempel);
  92.   free(cel);
  93. }
  94.  
  95.  
  96.