Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Minimum no. of comparisons to find median of 3 numbers

Tags:

median

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];
}
like image 611
Karan Kalra Avatar asked Jun 17 '13 23:06

Karan Kalra


2 Answers

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;
}
like image 150
Raghav Avatar answered Sep 20 '22 08:09

Raghav


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;
}
like image 26
codeb34v3r Avatar answered Sep 23 '22 08:09

codeb34v3r