Сортировать массив из 5 целых чисел с максимумом 7 сравнений

19

Как отсортировать список из 5 целых чисел, чтобы в худшем случае потребовалось 7 сравнений? Мне все равно, сколько других операций выполняется. Я не знаю ничего конкретного о целых числах.

Я пробовал несколько разных подходов «разделяй и властвуй», которые сводят меня к 8 сравнениям, например, следуя подходу сортировки слиянием или комбинируя сортировку слиянием с использованием бинарного поиска, чтобы найти позицию вставки, но каждый раз, когда я получаю 8, сравнивает наихудший случай ,

Сейчас я просто ищу подсказку, а не решение.

Роберт С. Барнс
источник
Вы пытались написать дерево для сравнения? Это имеет листов, каждая из которых соответствует перестановке целых чисел. Если вы не знаете, что я имею в виду под деревом сравнения, знаете ли вы доказательство того, что вам нужно сравнений? Ps, что заставляет вас думать, что это возможно? n log n5!=120nlogn
Пол GD
1
Ну, в дополнении 8 бит два, if(x > y)это то же самое, if((x - y) & 0x80)что вряд ли можно сравнить. Я предполагаю, что мы должны забыть, что объекты являются целыми числами, и предположить, что мы должны использовать некоторую магическую compare(x, y)функцию для сравнения этих объектов ...
Karolis Juodelė
2
Рассматривает ли раздел 5.3, посвященный оптимальной сортировке в томе 3 «Искусства компьютерного программирования» , который охватывает именно этот вопрос, «подсказку или решение? :-)
Стивен Стадницки,
3
Граница действительно то, чтои . Так что это возможно (в принципе). 5 ! = 120 < 2 7 = 1282cn!5!=120<27=128
vonbrand

Ответы:

23

Есть только один способ начать этот процесс (и почти для всех ваших решений о том, что сравнивать на последующих шагах, есть только один правильный). Вот как это понять. Во-первых, обратите внимание, что для сравнения можно получить возможных ответов, и различных перестановок, которые вы должны различать.5 ! = 12027=1285!=120

Первое сравнение легко: вам нужно сравнить два ключа, и, поскольку вы ничего о них не знаете, все варианты одинаково хороши. Допустим, вы сравниваете и и обнаруживаете, что . Теперь у вас осталось возможных ответов и осталось возможных перестановок (поскольку мы исключили половину из них).b a b 2 6 = 64 60abab26=6460

Затем мы можем либо сравнить и , либо сравнить с одним из ключей, которые мы использовали в первом сравнении. Если мы сравним и и узнаем, что , то у нас есть оставшихся ответа и возможных перестановок. С другой стороны, если мы сравнимd c c d c d 32 30 ccdccdcd3230c с , и мы обнаружили , что C , мы имеем 40 возможных перестановок оставшихся, потому что мы исключили 1 / 3 из возможных перестановок (те, с aac401/3 ). У нас есть только 32 возможных оставшихся ответов, поэтому нам не повезло.cab32

Итак, теперь мы знаем, что нам нужно сравнить первый и второй ключи, а также третий и четвертый ключи. Можно предположить, что у нас и c d . Если мы сравним е с любого из этих четырех ключей, по тем же соображениям мы использовали в предыдущем шаге, мы могли бы устранить только +1 / 3 из перестановок остальных, и мы не повезло. Таким образом, мы должны сравнить два ключа a , b , c , d . С учетом симметрии у нас есть два варианта: сравнить a и c или сравнить a и dabcde1/3a,b,c,dacad, Аналогичный аргумент подсчета показывает, что мы должны сравнить и c . Мы можем предположить без ограничения общности, что a c , и теперь мы имеем a b и a c d .acacabacd

Так как вы попросили подсказку, я не буду разбираться с остальными аргументами. У вас осталось четыре сравнения. Используйте их с умом.

Питер Шор
источник
Как вы узнали, что сравнение с c приводит вас к 40 перестановкам? ac
Роберт С. Барнс
1
@Robert: Предположим , что у вас есть и гр . Тогда есть две перестановки a , b , c, согласующиеся с этими ограничениями, a < b < c и a < c < b . Для каждой из этих двух перестановок есть четыре места, которые вы можете добавить d, и пять мест, которые вы можете добавить e . abaca,b,ca<b<ca<c<bde
Питер Шор
8

Вы можете найти это в книге «Искусство компьютерного программирования», том III, автор D.Knuth, но стратегия такова (я предполагаю, что у вас есть массив ): если вы хотите прочитать подсказку только первые две строки моего ответа{a,b,c,d,e}

  • Первая группа пар чисел: .(a,b),(c,d)
  • Сравните пары, чтобы отсортировать их, например: .a<b,c<d
  • Сравнивая наименьшие элементы пар, мы получаем результат, например, .a<c
  • Сравните последний элемент , с большим элементом в последнем сравнении ( c ) ec
    • Если , легко получить 3 оставшихся сравнения. Законченный.e<c
    • Если то вы должны отсортировать { b , c , d , e } со знанием c < e , c < d . e>c{b,c,d,e}c<e,c<d
      • , если d < e, то Compare(d,e)d<e
        • , если b > dCompare(b,d)b>d
          • . Законченный.Compare(b,e)
        • если b<d
          • . Законченный.Compare(b,c)
      • если d>e
        • если b > eCompare(b,e)b>e
          • . Законченный.Compare(b,d)
        • если b<e
          • . Законченный.Compare(b,c)

Все вышеперечисленные способы являются причиной не более трех сравнений после первого сравнения с c . (означает не более 7). ec

Джордж
источник
Вы уверены, что это правильно? Предположим, вы получите следующие результаты: a <b, c <d, a <c, а затем c <e, b <e, c <b и d <e. Порядок a <c <b <d <e и a <c <d <b <e оба согласуются с ними. Причина в том, что b и d никогда не сравниваются, неявно или явно. Может быть, я где-то ошибаюсь, если так, пожалуйста, поправьте меня.
Джордж,