Fast median search

 a asic implementationn

  1. #define ELEM_SWAP(a, b) {
  2.     register elem_type t = (a); (a) = (b); (b) = (t);
  3. }
  4.  
  5. elem_type quickSelect(elem_type arr[], int n)
  6. {
  7.     int low, high;
  8.     int median;
  9.     int middle, ll, hh;
  10.  
  11.     low = 0;
  12.     high = n - 1;
  13.     median = (low + high) / 2;
  14.     for (; ;)
  15.     {
  16.         if (high < low)         /* one element only */
  17.             return arr[median];
  18.         if (high == low + 1) {
  19.             /* Two elements only */
  20.             if (arr[low] > arr[high])
  21.                 ELEM_SWAP(arr[low], arr[high]);
  22.             return arr[median];
  23.         }
  24.  
  25.         /* Find median of low, median and high items; Swap into positin low */
  26.         middle = (low + high) / 2;
  27.         if (arr[middle] > arr[high]) ELEM_SWAP(arr[middle], arr[high]);
  28.         if (arr[low] > arr[high]) ELEM_SWAP(arr[low], arr[high]);
  29.         if (arr[middle] > arr[low]) ELEM_SWAP(arr[middle], arr[low]);
  30.  
  31.         /* Swap low item (now in position middle) into low + 1 */
  32.         ELEM_SWAP(arr[middle], arr[low+1]);
  33.  
  34.         /* Nibble from each end towards middle, swapping items was stuck */
  35.         ll = low + 1;
  36.         hh = high;
  37.         for (;;)
  38.         {
  39.             do ll++; while (arr[low] > arr[ll]);
  40.             do hh--; while (arr[hh] > arr[low]);
  41.  
  42.             if (hh < ll) break;
  43.             ELEM_SWAP(arr[ll], arr[hh]);
  44.            
  45.         }
  46.         /* Swap middle item (in position low) back into position */
  47.         ELEM_SWAP(arr[low], arr[hh]);
  48.         /* Re-set actieve partition */
  49.         if (hh <= median)
  50.             low = ll;
  51.         if (hh >= median)
  52.             high = hh - 1;
  53.     }
  54. }
  55.  
  56.  

Algorithm c median search algo Comments(0) 2008年9月24日 20:12







Host by is-Programmer.com | Power by Chito 1.3.3 beta | Designed by Wink Hosting.