As of right now, my functioin finds the median of 3 numbers and sorts them, but it always makes three comparisons. I'm thinking I can use a nested if statement somewhere so that sometimes my function will only make two comparisons.
int median_of_3(int list[], int p, int r)
{
int median = (p + r) / 2;
if(list[p] > list[r])
exchange(list, p, r);
if(list[p] > list[median])
exchange(list, p, median);
if(list[r] > list[median])
exchange(list, r, median);
comparisons+=3; // 3 comparisons for each call to median_of_3
return list[r];
}
I'm not sure I see where I can make that nested if statement.
If you only need the median value, here's a branch-less solution based on min/max operators:
median = max(min(a,b), min(max(a,b),c));
Intel CPU's have SSE min/max vector instructions, so depending on your or your compiler's ability to vectorize, this can run extremely fast.
If we allow extra operations, we could use at most 2 comparisons to find the median. The trick is to use exclusive or to find the relationship among three numbers.
void median3(int A[], int p, int r)
{
int m = (p+r)/2;
/* let a, b, c be the numbers to be compared */
int a = A[p], b = A[m], c = A[r];
int e = a-b;
int f = a-c;
if ((e^f) < 0) {
med_comparisons += 1;
/* a is the median with 1 comparison */
A[m] = a;
/* b < a < c ? */
if (b < c) /* b < a < c */ { A[p] = b, A[r] = c; }
else /* c < a < b */ { A[p] = c, A[r] = b; }
comparisons += 2;
} else {
med_comparisons += 2;
int g = b-c;
if ((e^g) < 0) {
/* c is the median with 2 comparisons */
A[m] = c;
/* a < c < b ? */
if (a < b) /* a < c < b */ { A[p] = a, A[r] = b; }
else /* b < c < a */ { A[p] = b, A[r] = a; }
} else {
/* b is the median with 2 comparisons */
A[m] = b;
/* c < b < a ? */
if (a > c) /* c < b < a */ { A[p] = c; A[r] = a; }
else /* a < b < c */ { /* do nothing */ }
}
comparisons += 3;
}
}
The first exclusive or (e^f) is to find out the difference of the sign bit between (a-b) and (a-c).
If they have different sign bit, then a is the median. Otherwise, a is either the minimum or the maximum. In that case, we need the second exclusive or (e^g).
Again, we are going to find out the difference of the sign bit between (a-b) and (b-c). If they have different sign bit, one case is that a > b && b < c. In this case, we also get a > c because a is the maximum in this case. So we have a > c > b. The other case is a < b && b > c && a < c. So we have a < c < b; In both cases, c is the median.
If (a-b) and (b-c) have the same sign bit, then b is the median using similar arguments as above. Experiments shows that a random input will need 1.667 comparisons to find out the median and one extra comparison to get the order.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With