4

ランダム要素が 5 つある場合、6 回の比較だけで中央値を求めることができます。ただし、次の条件も満たされているという点で、追加の要件があります。

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

a < b または d < e には必要ありません。

7 回の比較でこの条件を満たすことができましたが、6 回ではありませんでした。これは私のコードであり、自明のはずです:

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 を使用してピボットを選択することで強化したいクイック ソートがあります。その条件を満たすことで、すでに 5 つの要素がソートされています。

これを 6 回の比較で達成することは可能ですか、それとも 7 回が最善でしょうか?

4

2 に答える 2

2

私はその問題を2時間挽きましたが、解決策を見つけました。重要なことは、行われた比較を追跡することです。これは、コメントを使用して非常に詳細に行いました。関数は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

于 2012-06-19T19:04:06.730 に答える
1

わかりましたので、少なくとも 6 回の比較が必要であることを証明します。

まず、取得したすべての情報は比較のみに基づいていることに注意してください。比較ステップで発生したことに基づいて、最後にスワッピングを行うことができます。また、比較は以前に行った比較にのみ基づいていることに注意してください。たとえば、アルゴリズムの最初のステップは、以前に比較が行われていないため、常に同じになります。2 番目の比較はすでに最初の比較に依存している可能性があります。

1、2、3、4、5 の大きさに応じて要素に「名前」を付けましょう。これらは任意の順序で入力に表示できます。ここで、要素を正しく並べ替えるには、少なくとも 4 つの比較が必要です。彼らです：

3 > 2           [1]
3 > 1 OR 2 > 1  [2]
3 < 4           [3]
3 < 5 OR 4 < 5  [4]

その他の比較は余分です。[2]また、両方の比較または両方の比較を避けることができない場合、[4]それらも余分になります。

最初の順列は何でもよいので、すぐに追加の比較が 1 つ得られます: 1 < 5(これは理解することが重要です: 私たちのアルゴリズムは常に最初の 2 つの要素が入力でどのように提示されるかに応じて、たとえばaとbを使用するため、常に可能性a = 1とb = 5)。

ここで、2 番目のステップで考慮すべき 2 つのケースがあります。

ケース 1:と 以外の 2 つの要素を比較1し5ます。2、3、およびを区別できないため4、この段階ですぐに 2 番目の余分な比較が得られます2 < 4。したがって、最大6つの比較があります。

ケース 2: orを、、またはのいずれ1かと比較します。一般性を失うことなく、 を比較していると仮定しましょう。、、 antを区別できないため、2 番目の追加の比較を行います。QED523412341 < 4

于 2012-06-20T12:36:50.023 に答える