Minimum no. of comparisons to find median of 3 num

Question

I was implementing quicksort and I wished to set the pivot to be the median or three numbers. The three numbers being the first element, the middle element, and the last element.

Could I possibly find the median in less no. of comparisons?

median(int a[], int p, int r)
{
    int m = (p+r)/2;
    if(a[p] < a[m])
    {
        if(a[p] >= a[r])
            return a[p];
        else if(a[m] < a[r])
            return a[m];
    }
    else
    {
        if(a[p] < a[r])
            return a[p];
        else if(a[m] >= a[r])
            return a[m];
    }
    return a[r];
}

Answer 1

You can write up all the permutations:

    1 0 2
    1 2 0
    0 1 2
    2 1 0
    0 2 1
    2 0 1

Then we want to find the position of the 1. We could do this with two comparisons, if our first comparison could split out a group of equal positions, such as the first two lines.

The issue seems to be that the first two lines are different on any comparison we have available: a<b, a<c, b<c. Hence we have to fully identify the permutation, which requires 3 comparisons in the worst case.

Answer 2

You can't do it in one, and you're only using two or three, so I'd say you've got the minimum number of comparisons already.

Answer 3

I know that this is an old thread, but I had to solve exactly this problem on a microcontroller that has very little RAM and does not have a h/w multiplication unit (:)). In the end I found the following works well:

static char medianIndex[] = { 1, 1, 2, 0, 0, 2, 1, 1 };

signed short getMedian(const signed short num[])
{
    return num[medianIndex[(num[0] > num[1]) << 2 | (num[1] > num[2]) << 1 | (num[0] > num[2])]];
}

Answer 4

Rather than just computing the median, you might as well put them in place. Then you can get away with just 3 comparisons all the time, and you've got your pivot closer to being in place.

T median(T a[], int low, int high)
{
    int middle = ( low + high ) / 2;
    if( a[ middle ].compareTo( a[ low ] ) < 0 )
        swap( a, low, middle );
    if( a[ high ].compareTo( a[ low ] ) < 0 )
        swap( a, low, high );
    if( a[ high ].compareTo( a[ middle ] ) < 0 )
        swap( a, middle, high );

    return a[middle];
}

Answer 5

There is actually a clever way to isolate the median element from three using a careful analysis of the 6 possible permutations (of low, median, high). In python:

def med(a, start, mid, last):
    # put the median of a[start], a[mid], a[last] in the a[start] position
    SM = a[start] < a[mid]
    SL = a[start] < a[last]
    if SM != SL:
        return
    ML = a[mid] < a[last]
    m = mid if SM == ML else last
    a[start], a[m] = a[m], a[start]

Half the time you have two comparisons otherwise you have 3 (avg 2.5). And you only swap the median element once when needed (2/3 of the time).

Full python quicksort using this at:

https://github.com/mckoss/labs/blob/master/qs.py

Answer 6

int32_t FindMedian(const int n1, const int n2, const int n3) {
    auto _min = min(n1, min(n2, n3));
    auto _max = max(n1, max(n2, n3));
    return (n1 + n2 + n3) - _min - _max;
}