Hoare's algorithm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

float sf_quantile(int q    /* quantile */,
		  int n    /* array length */,
		  float* a /* array [n] */)
/*< find quantile (caution: a is changed) >*/
{
    float *i, *j, ak, *low, *hi, buf, *k;

    low=a;
    hi=a+n-1;
    k=a+q;
    while (low<hi) {
	    ak = *k;
	    i = low; j = hi;
	    do {
        // 找出a[i]>=ak 时的i值
	      while (*i < ak) i++;
        // 找出a[j]>=ak 时的j值     
	      while (*j > ak) j--;   
        // 交换 a[i]与a[j]的值，并移动i和j  
	      if (i<=j) {
		      buf = *i;
		      (*i)++ = *j;
		      (*j)-- = buf;
	      }
	    } while (i<=j);
      // 更新low 和 hi
	    if (j<k) low = i;
	    if (k<i) hi = j;
    }
    return (*k);
}