algorithm - 可以通过六次比较按中位数划分五个元素吗？

Question

给定五个随机元素，只需进行六次比较就可以找到中位数。但是我有一个额外的要求，就是还要满足以下条件:

a < c && b < c && c < d && c < e

a < b 或 d < e 不需要它。

我已经能够使用七次 比较来满足此条件，但不是六次。这是我的代码，应该是不言自明的:

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

我有一个快速排序，我希望通过使用中位数 5 来选择主元来增强它。通过满足该条件，五个元素已经排序。

是否有可能在六次比较中完成这个任务，或者七次是我能做的最好的吗？

Answer 1

我花了两个小时解决这个问题，但我找到了解决方案。重要的是要跟踪所做的比较，我已经在评论中做了非常详细的比较。该函数是用 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