Minimum no. of comparisons to find median of 3 numbers

Karan Kalra picture Karan Kalra · Jun 18, 2013 · Viewed 25k times · Source

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

Raghav picture Raghav · Mar 5, 2015

If the concern is only comparisons, then this should be used.

int getMedian(int a, int b , int c) {
    int x = a-b;
    int y = b-c;
    int z = a-c;
    if(x*y > 0) return b;
    if(x*z > 0) return c;
    return a;
}