Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
_select.c
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 1k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

_select.c：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _select.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #include <LEDA/basic_alg.h>
  15. #define SWAP(a,b) { help = *a; *a = *b; *b = help; }
  18. int SELECT(int* l, int* r, int pos)
  19. { 
  20.   // compute element at position "pos" in sequence *l,...,*r
  21.   // expected running time: O(r-l)
  23.   register int* i;
  24.   register int* k;
  25.   register int s;
  26.   register int help;
  28.   while (l < r) 
  29.   { i = l+(r-l)/2;
  30.     if (*i > *r) SWAP(i,r);
  31.     SWAP(l,i);
  33.     i = l;
  34.     k = r;
  35.     s = *l;
  37.     for(;;)
  38.     { while (*(++i) < s);
  39.       while (*(--k) > s);
  40.       if (i<k) SWAP(i,k) else break;
  41.      }
  42.   
  43.     SWAP(l,k);
  44.   
  45.     int j =  k-l+1;
  46.     if (pos <= j) 
  47.        r = k;
  48.     else 
  49.        { l = k+1;
  50.          pos -= j;
  51.         }
  52.   }
  54.   return *l;
  55. }
  59. double SELECT(double* l, double* r, int pos)
  60. { 
  61.   register double* i;
  62.   register double* k;
  63.   register double s;
  64.   register double help;
  66.   while (l < r) 
  67.   { i = l+(r-l)/2;
  68.     if (*i > *r) SWAP(i,r);
  69.     SWAP(l,i);
  71.     i = l;
  72.     k = r;
  73.     s = *l;
  75.     for(;;)
  76.     { while (*(++i) < s);
  77.       while (*(--k) > s);
  78.       if (i<k) SWAP(i,k) else break;
  79.      }
  80.   
  81.     SWAP(l,k);
  82.   
  83.     int j =  k-l+1;
  84.     if (pos <= j) 
  85.        r = k;
  86.     else 
  87.        { l = k+1;
  88.          pos -= j;
  89.         }
  90.   }
  92.   return *l;
  93. }