Search code examples
median

Minimum no. of comparisons to find median of 3 numbers

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];
}
Solution

  • 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.