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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#ifndef _MEDIAN_H
#define _MEDIAN_H
/* This is taken from http://ndevilla.free.fr/median/median/src/wirth.c */
/*
* Algorithm from N. Wirth's book, implementation by N. Devillard.
* This code in public domain.
*/
#include <stdint.h>
#define elem_type uint32_t
#define ELEM_SWAP(a,b) { register elem_type t=(a);(a)=(b);(b)=t; }
/*---------------------------------------------------------------------------
Function : kth_smallest()
In : array of elements, # of elements in the array, rank k
Out : one element
Job : find the kth smallest element in the array
Notice : use the median() macro defined below to get the median.
Reference:
Author: Wirth, Niklaus
Title: Algorithms + data structures = programs
Publisher: Englewood Cliffs: Prentice-Hall, 1976
Physical description: 366 p.
Series: Prentice-Hall Series in Automatic Computation
---------------------------------------------------------------------------*/
static elem_type kth_smallest(elem_type a[], int n, int k)
{
register int i,j,l,m ;
register elem_type x ;
l=0 ; m=n-1 ;
while (l<m) {
x=a[k] ;
i=l ;
j=m ;
do {
while (a[i]<x) i++ ;
while (x<a[j]) j-- ;
if (i<=j) {
ELEM_SWAP(a[i],a[j]) ;
i++ ; j-- ;
}
} while (i<=j) ;
if (j<k) l=i ;
if (k<i) m=j ;
}
return a[k] ;
}
#define median(a,n) kth_smallest(a,n,(((n)&1)?((n)/2):(((n)/2)-1)))
#endif
|
