|Written by Mike James|
|Friday, 11 August 2017|
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.
do the left and right scan
Once the two scans stop we swap values if they are in the wrong part:
A function that makes use of the basic split method to find the median is:
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.
Notice that this will only give you median if n is odd and it doesn't work at all if there are duplicate values in the array.
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.
Related ArticlesQuickSort exposed
or email your comment to: email@example.com
|Last Updated ( Friday, 11 August 2017 )|