Page 2 of 2
Divide and conquer in C#
What is even stranger is that this is a `divide and conquer' type algorithm and so it is likely to be fast. You can show that this method will (on average) find the median of n elements in a time proportional to 2n - which is much better than performing a full sort.
An implementation of this median-finding method in C# might help understand exactly what is going on.
The function split implements the scanning action. The n values are in the array a[ ], x is the splitting value, the left scan pointer is i and the right scan pointer is j. Notice that the two scan pointers have to be passed as ref because their updated values are used by the calling program to discover where they crossed.
private void split (
ref int i,ref int j)
do the left and right scan until the pointers cross
scan from the left then scan from the right
while (a[i] < x)i++;
while (x < a[j])j--;
now swap values if they are in the wrong part:
if (i <= j)
float t = a[i];
a[i] = a[j];
a[j] = t;
and continue the scan until the pointers cross:
} while (i <= j);
A function that makes use of the basic split method to find the median is:
private void median(
ref int k)
int L = 0;
int R = n-1;
k = n / 2;
int i;int j;
while (L < R)
float x = a[k];
i = L; j = R;
split(a, n, x,ref i,ref j);
if (j < k) L = i;
if (k < i) R = j;
This initially sets the scan to the whole of the array and x to the middle value. It then calls split repeatedly on appropriate portions of the array until the two pointers meet in the middle of the array when the value in a[k] is the median.
If you are interested in finding percentiles other than the median then all you have to do is change the initial value of k. The value that you end up with in a[k] is always bigger than the number of element to its left and smaller than the number of elements to its right.
For example, if you set k=n/3 then you will find a value that divides the array into 1/3rd, 2/3rds.
Don't bother to use this algorithm unless the number of values is large. For small arrays almost any method will do and sorting is invariably simpler.
Even when it isn't practical, this quick median method is always beautiful.