67 lines
1.8 KiB
C
67 lines
1.8 KiB
C
|
|
/*
|
|
* Algorithm from N. Wirth's book, implementation by N. Devillard.
|
|
* This code in public domain.
|
|
*/
|
|
|
|
#define ELEM_SWAP(a, b) \
|
|
{ \
|
|
register double 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
|
|
|
|
---------------------------------------------------------------------------*/
|
|
|
|
double kth_smallest(double a[], int n, int k) {
|
|
register int i, j, l, m;
|
|
register double 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];
|
|
}
|
|
|
|
double wirth_median(double a[], int n) {
|
|
if (n % 2 == 0) {
|
|
return 0.5 * (kth_smallest(a, n, n / 2) + kth_smallest(a, n, n / 2 - 1));
|
|
} else {
|
|
return kth_smallest(a, n, (n - 1) / 2);
|
|
}
|
|
}
|