Можно разделить пять элементов по медианной с шестью сравнениями?

Question

Учитывая пять случайных элементов, можно найти медиана, используя только шесть сравнений. Но у меня есть дополнительное требование о том, что следующее условие также выполнено:

< с & & б < с & & с < d & & с < е

Это НЕ требуется для < б или 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]); 
} 

Я быстро то, что я хочу, чтобы усилить с помощью медианы пяти выбрать точку опоры. Выполняя это условие, пять элементов уже отсортированы.

Можно ли выполнить это в шести сравнениях, или это семь лучших, что я могу сделать?

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

Answer 2

Итак, вот доказательство того, что вам нужно, по крайней мере 6 сравнений.

Прежде всего, обратите внимание, что вся полученная информация основана только на сравнении. Мы можем сделать замену в самом конце, исходя из того, что произошло во время шагов сравнения. Также обратите внимание, что наши сравнения могут основываться только на проведенных сравнениях ранее. Например, первый шаг в алгоритме всегда будет таким же, как ранее не проводилось сравнение; второе сравнение уже может зависеть от первого и т. д.

Давайте укажем «элементы» по их величине - 1,2,3,4,5. Они могут отображаться на входе в любом порядке. Теперь нам нужно по крайней мере четыре сравнения, чтобы заказать элементы правильно. К ним относятся:

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

Любое другое сравнение дополнительные. Кроме того, если мы не можем избежать обоих сравнений в [2] или оба сравнения в [4] - они также становятся дополнительно.

Поскольку начальная перестановка может быть что угодно, мы сразу получаем один дополнительные сравнения: 1 < 5 (это важно, чтобы понять: как наш алгоритм всегда принимает те же первые два элемента в соответствии с тем, как они представлены на входе, скажем, a и b, всегда есть вероятность, что a = 1 и b = 5).

Теперь, есть два случая для второго этапа:

Случай 1: мы сравним два отличных 1 и 5 элементов. Поскольку мы не можем отличить 2, 3 и 4 на этом этапе, мы сразу получаем второе дополнительное сравнение: 2 < 4. Таким образом, мы имеем до 6 сравнений.

Случай 2: сравнить 1 или 5 с одним из 2, 3 или 4. Без ограничения общности предположим, что мы сравниваем 1. Поскольку мы не можем отличить 2, 3, муравей 4, мы получаем наш второй дополнительно сравнение: 1 < 4. QED