Given five random elements, it's possible to find the median using just six comparisons. But I have an extra requirement in that the following condition is also satisfied:
a < c && b < c && c < d && c < e
It is NOT required for a < b or d < e.
I've been able to satisfy this condition using seven comparisons, but not six. This is my code, which should be self explanatory:
void medianSort(int[] arr)
{
assert(arr.length == 5);
void sortPair(ref int a, ref int b)
{
if(a > b) swap(a, b);
}
sortPair(arr[0], arr[1]);
sortPair(arr[3], arr[4]);
sortPair(arr[0], arr[3]);
sortPair(arr[1], arr[4]);
sortPair(arr[2], arr[3]);
sortPair(arr[1], arr[2]);
sortPair(arr[2], arr[3]);
}
I have a quick sort that I wish to enhance by using a median of five to choose the pivot. By satisfying that condition, five elements are already sorted.
Is it possible to accomplish this in six comparisons, or is seven the best I can do?
I grinded away at the problem for two hours, but I found a solution. The important thing is to keep track of the comparisons made, which I've done in great detail with the comments. The function is written in D.
void medianSort(alias pred = "a < b", T)(ref T a, ref T b, ref T c, ref T d, ref T e)
{
alias binaryFun!pred less;
bool greater(T a, T b){ return !less(a, b); }
if(greater(a, b)) swap(a, b); // #1
// a<b
if(greater(d, e)) swap(d, e); // #2
// a<b d<e
if(less(a, d)) // #3
{
// a<d<e a<b
// eliminate a
// d<e
if(greater(b,c)) swap(b,c); // #4
// b<c d<e
}
else // if(less(d, a))
{
// a<b d<a d<e
// d<a<b d<e
swap(a, d);
// a<d<b a<e
// eliminate a
// d<b
swap(d, b);
// b<d
if(greater(c, e)) swap(c, e); // #4
// b<d c<e
swap(c, d);
// b<c d<e
}
// b<c d<e
if(less(b, d)) // #5
{
// b<c b<d d<e
// b<c b<d<e
// eliminate b
// d<e
}
else
{
// b<c d<e d<b
// d<b<c d<e
swap(b, d);
// b<d<c b<e
// eliminate b
// d<c
swap(c, e);
// d<e
}
// d<e
// median is smaller of c and d
if(greater(c, d)) swap(c, d); // #6
}
Python: http://pastebin.com/0kxjxFQX