views:

4236

answers:

8

Note: Please don't interpret this as "homework question." This is just a thing I curious to know :)

The median of five is sometimes used as an exercise in algorithm design and is known to be computable using only 6 comparisons.

What is the best way to implement this "median of five using 6 comparisons" in C# ? All of my attempts seem to result in awkward code :( I need nice and readable code while still using only 6 comparisons.

public double medianOfFive(double a, double b, double c, double d, double e){
 //
 // return median
 //
 return c;
}

Note: I think I should provide the "algorithm" here too:

I found myself not able to explain the algorithm clearly as Azereal did in his forum post. So I will reference his post here. From http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

Well I was posed this problem in one of my assignments and I turned to this forum for help but no help was here. I eventually found out how to do it.

  1. Start a mergesort with the first 4 elements and order each pair (2 comparisons)

  2. Compare the two lower ones of each pair and eliminate the lowest one from the possibilities (3 comparisons)

  3. Add in the 5th number set aside to the number without a pair and compare the two (4 comparisons)

  4. Compare the two lowest of the two new pairs and eliminate the lower one (5 comparisons)

  5. Compare the one by itself and the lower of the last pair and the lower number is the median

    The possible median is within the parentesis

(54321)

5:4 3:2 2 comparisons

(4<5 2<3 1)

4:2 3 comparisons

2(4<5 3 1)

1:3 4 comparisons

2(4<5 1<3)

4:1 5 comparisons

1,2(4<5 3)

4:3 6 comparisons

1,2(3)4,5

Three is the median

EDIT: As your request and to prevent myself from getting more downvotes, this are C++ code I wrote to find median of five. Don't mind it's awkwardness:

double StageGenerator::MedianOfFive(double n1, double n2, double n3, double n4, double n5){
    double *a = &n1, *b = &n2, *c = &n3, *d = &n4, *e = &n5;
    double *tmp;

    // makes a < b and b < d
    if(*b < *a){
     tmp = a; a = b; b = tmp;
    }

    if(*d < *c){
     tmp = c; c = d; d = tmp;
    }

    // eleminate the lowest
    if(*c < *a){
     tmp = b; b = d; d = tmp; 
     c = a;
    }

    // gets e in
    a = e;

    // makes a < b and b < d
    if(*b < *a){
     tmp = a; a = b; b = tmp;
    }

    // eliminate another lowest
    // remaing: a,b,d
    if(*a < *c){
     tmp = b; b = d; d = tmp; 
     a = c;
    }

    if(*d < *a)
     return *d;
    else
     return *a;

}

It should be more compact, isn't it ?

EDIT:

As @pablito pointed out in his answer. The built-in List.Sort() cannot fulfill this requirement since it uses up to 13 comparisons :]

+7  A: 

An interesting thread here:

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

Quote from thread:

1) Put the numbers in an array. 
2) Use three comparisons and shuffle around the numbers so that a[1] < a[2], a[4] < a[5], and a[1] < a[4]. 
3) If a[3] > a[2], then the problem is fairly easy. If a[2] < a[4], the median value is the smaller of a[3] and a[4]. If not, the median value is the smaller of a[2] and a[5]. 
4) So a[3] < a[2]. If a[3] > a[4], then the solution is the smaller of a[3] and a[5]. Otherwise, the solution is the smaller of a[2] and a[4].
This is looking great. The solution I found is also from the same thread. A solid implementation in C# would also be fine :D
m3rLinEz
+4  A: 

Just to check how many comparisons:

    class MyComparable : IComparable
{

    public static int NumberOfComparisons = 0;

    public int NumPart { get; set; }

    #region IComparable Members

    public int CompareTo(object obj)
    {
        NumberOfComparisons++; //I know, not thread safe but just for the sample
        MyComparable mc = obj as MyComparable;
        if (mc == null)
            return -1;
        else
            return NumPart.CompareTo(mc.NumPart);
    }

    #endregion
}

class Program
{
    static void Main(string[] args)
    {
        List<MyComparable> list = new List<MyComparable>();
        list.Add(new MyComparable() { NumPart = 5 });
        list.Add(new MyComparable() { NumPart = 4 });
        list.Add(new MyComparable() { NumPart = 3 });
        list.Add(new MyComparable() { NumPart = 2 });
        list.Add(new MyComparable() { NumPart = 1 });
        list.Sort();


        Console.WriteLine(MyComparable.NumberOfComparisons);
    }
}

the result is 13.

pablito
+1 Thanks. I put your result in my question body too.
m3rLinEz
+1  A: 

This should do it

private Double medianofFive(double[] input)
{
    Double temp;
if (input[0] > input[1])//#1 - sort First and Second
{
    temp = input[0];
    input[0] = input[1];
    input[1] = temp;
}
if (input[2] > input[3])//#2 sort Third and Fourth
{
    temp = input[2];
    input[2] = input[3];
    input[3] = temp;
}

// replace the smaller of first and third with 5th, then sort
int smallerIndex = input[0] < input[2] ? 0 : 2;//#3
input[smallerIndex] = input[4];

//sort the new pair
if(input[smallerIndex]>input[smallerIndex+1])//#4
{
    temp = input[smallerIndex];
    input[smallerIndex] = input[smallerIndex+1];
    input[smallerIndex+1] = temp;
}

//compare the two smaller numbers
// then compare the smaller of the two's partner with larger of the two
// the smaller of THOSE two is the median
if (input[2] > input[0])
//#5
{
    temp = input[2] > input[1] ? input[1] : input[2];//#6
}
else
{
    temp = input[0] > input[3] ? input[3] : input[0];//#6
}
    return temp;
}
Kevin
Don't know what's going on, but it looks fine in preview, but gets cut off on the main page
Kevin
Fixed. Use the markdown editor, not your own form of markdown.
Geoffrey Chetwood
+4  A: 

This is basically just factoring out the swapping and sorting code from your C++ example:

private static void Swap(ref double a, ref double b) {
    double t = a;
    a = b;
    b = t;
}

private static void Sort(ref double a, ref double b) {
    if (a > b) {
        double t = a;
        a = b;
        b = t;
    }
}

private static double MedianOfFive(double a, double b, double c, double d, double e){
    // makes a < b and c < d
    Sort(ref a, ref b);
    Sort(ref c, ref d);

    // eleminate the lowest
    if (c < a) {
        Swap(ref b, ref d);
        c = a;
    }

    // gets e in
    a = e;

    // makes a < b
    Sort(ref a, ref b);

    // eliminate another lowest
    // remaing: a,b,d
    if (a < c) {
        Swap(ref b, ref d);
        a = c;
    }

    return Math.Min(d, a);
}
Matthew Crumley
Nice improvement of clarity, and any compiler worth anything would inline Swap and Sort if this was being used in a tight loop (the only reason I can see to implement something so specific).
Godeke
I find your code to be the most compact code here and mark it as accepted answer. Other code are also helpful as well, and I vote them all up :)
m3rLinEz
This code is correct, but the comment `// makes a < b and b < d` is wrong; if you check after that sort you'll see that sometimes `b > d`. For example, this happens when you call `MedianOfFive(1, 2, 3, 4, 5)` and generally whenever `e` is the largest of the five arguments.
Jason Orendorff
@Jason, good catch. I just copied the comments from the OP's code without checking them to see if they made sense.
Matthew Crumley
+2  A: 

This is pretty ugly and could use some refactoring, but it explicitly walks through all the comparisons and swaps so you can see what's going on.

public double medianOfFive(double a, double b, double c, double d, double e){
    double median;
    // sort a and b
    if(a > b) // comparison # 1
    {
        double temp = a;
        a = b;
        b = temp;
    }

    // sort c and d
    if(c > d)  // comparison # 2
    {
        double temp = c;
        c = d;
        d = temp;
    }

    // replace the lower of a and c with e
    // because the lowest of the first four cannot be the median
    if(a < c) // comparison # 3
    {
        a = e;
        // re-sort a and b
        if(a > b) // comparison # 4
        {
            double temp = a;
            a = b;
            b = temp;
        }
    }
    else
    {
        c = e;
        // re-sort c and d
        if(c > d)  // comparison # 4
        {
            double temp = c;
            c = d;
            d = temp;
        }
    }

    // eliminate a or c, because the lowest
    // of the remaining four can't be the median either
    if(a < c) // comparison #5
    {
         if(b < c) // comparison #6
         {
              median = c;
         }
         else
         {
              median = b;
         }
    }
    else
    {
         if(d < a) // comparison #6
         {
              median = a;
         }
         else
         {
              median = d;
         }
    }
    return median;
}
Bill the Lizard
A: 

Interesting how many comparisons in MSDN sample...

public static double Median(this IEnumerable<double> source) {
        if (source.Count() == 0)  throw new InvalidOperationException("Cannot compute median for an empty set.");

        var sortedList = from number in source
                         orderby number
                         select number;

        int itemIndex = (int)sortedList.Count() / 2;

        if (sortedList.Count() % 2 == 0) {
            // Even number of items.
            return (sortedList.ElementAt(itemIndex) + sortedList.ElementAt(itemIndex - 1)) / 2; } else {
            // Odd number of items.
            return sortedList.ElementAt(itemIndex); }
    }
Tamir
+1  A: 

For completeness, the question is a specific case of a sorting network, which Knuth (Art of Computer Programming, vol 3) covers in great detail. The classic paper by K.E. Batcher on the subject is brief and worth reading.

joel.neely
This is great! Thanks :)
m3rLinEz
+4  A: 

I found this post interesting and as an exercise I created this which ONLY does 6 comparisons and NOTHING else:

static double MedianOfFive(double a, double b, double c, double d, double e)
{
    return b < a ? d < c ? b < d ? a < e ? a < d ? e < d ? e : d
                                                 : c < a ? c : a
                                         : e < d ? a < d ? a : d
                                                 : c < e ? c : e
                                 : c < e ? b < c ? a < c ? a : c
                                                 : e < b ? e : b
                                         : b < e ? a < e ? a : e
                                                 : c < b ? c : b
                         : b < c ? a < e ? a < c ? e < c ? e : c
                                                 : d < a ? d : a
                                         : e < c ? a < c ? a : c
                                                 : d < e ? d : e
                                 : d < e ? b < d ? a < d ? a : d
                                                 : e < b ? e : b
                                         : b < e ? a < e ? a : e
                                                 : d < b ? d : b
                 : d < c ? a < d ? b < e ? b < d ? e < d ? e : d
                                                 : c < b ? c : b
                                         : e < d ? b < d ? b : d
                                                 : c < e ? c : e
                                 : c < e ? a < c ? b < c ? b : c
                                                 : e < a ? e : a
                                         : a < e ? b < e ? b : e
                                                 : c < a ? c : a
                         : a < c ? b < e ? b < c ? e < c ? e : c
                                                 : d < b ? d : b
                                         : e < c ? b < c ? b : c
                                                 : d < e ? d : e
                                 : d < e ? a < d ? b < d ? b : d
                                                 : e < a ? e : a
                                         : a < e ? b < e ? b : e
                                                 : d < a ? d : a;
}
DRBlaise
Concise and simple. Rotfl.
zendar
Cool! Glad you have find this question useful :)
m3rLinEz
+1 for pretty formatting
R..