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 (
     float[] a,
     int n,
     float x,
     ref int i,ref int j)
{

do the left and right scan

  do
  {

   while (a[i] < x)i++;
    while (a[j] > x)j--;

Once the two scans stop we swap values if they are in the wrong part:

   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(
   float[] a,
   int n,
   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.

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.

Listing

        float[] a = { 1, 2, 3, 0, 8, 9, 5 };
        int k = 0;
        median(a, 7, ref k);

      
        private void split(
         float[] a,
         int n,
         float x,
         ref int i, ref int j)
        {
            do
            {
                while (a[i] < x ) i++;
                while (a[j] > x) j--;
                float t = a[i];
                a[i] = a[j];
                a[j] = t;
            } while (i < j);
        }

        private void median(
           float[] a,
           int n,
           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 (i >= k) R = j;
            }
        }
    }

• Mike James, Founder and Chief Editor of I Programmer is a prolific author. In Deep C#: Dive Into Modern C# he provides a “deep dive” into various topics that are important or central to the language. By exploring the motivation behind these key concepts, which is so often ignored in the documentation, the intention is to be thought-provoking and to give developers confidence to exploit C#’s wide range of features.

Related Articles

QuickSort exposed

Advanced Hashing

How not to shuffle - the Knuth Fisher-Yates algorithm

The Monty Hall Problem 

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

<ASIN:1871962714>

<ASIN:B09FTLPTP9>