Подтвердить что ты не робот

Разработать эффективный алгоритм для сортировки 5 различных ключей в менее чем 8 сравнениях

Создайте эффективный алгоритм для сортировки 5 отдельных - очень больших - ключей менее 8 сравнений в худшем случае. Вы не можете использовать сортировку radix.

4b9b3361

ОТВЕТЫ

Ответ 1

Сравните A с B и C с D. WLOG, предположим, что A > B и C > D. Сравните A с C. WLOG, предположим, что A > C. Сортировка E в A-C-D. Это можно сделать с помощью двух сравнений. Сортировка B в {E, C, D}. Это можно сделать с помощью двух сравнений, в общей сложности семь.

Ответ 2

Это псевдокод на основе бета-ответа. Возможно, у меня есть некоторые ошибки, поскольку я сделал это в спешке.

if (A > B)
    swap A, B
if (C > D)
    swap C, D
if (A > C)
    swap A, C
    swap B, D  # Thanks Deqing!

if (E > C)
    if (E > D) %A C D E
        if (B > D)
            if (B > E)
                return (A, C, D, E, B)
            else
                return (A, C, D, B, E)
         else
            if (B < C)
                return (A, B, C, D, E)
            else
                return (A, C, B, D, E)

    else %A C E D
        if (B > E)
            if (B > D)
                return (A, C, E, D, B)
            else
                return (A, C, E, B, D)
         else
            if (B < C)
                return (A, B, C, E, D)
            else
                return (A, C, B, E, D)
else
    if (E < A) % E A C D
        if (B > C)
            if (B > D)
                return (E, A, C, D, B)
            else
                return (E, A, C, B, D)
         else
             return (E, A, B, C, D)

    else %A E C D
        if (B > C)
            if (B > D)
                return (A, E, C, D, B)
            else
                return (A, E, C, B, D)
         else
            if (B < E)
                return (A, B, E, C, D)
            else
                return (A, E, B, C, D)

Ответ 3

Пять элементов могут быть отсортированы с семью сравнениями в худшем литье, потому что log 2 (5!) = 6.9. Я предлагаю проверить, достигает ли какой-либо стандартный алгоритм сортировки сортировки это число - если не должно быть довольно сложно жестко кодировать последовательность сравнения из-за небольшого количества требуемых сравнений.

Я предлагаю написать программу, чтобы найти последовательность сравнения. Создайте список со всеми 120 перестановками чисел от одного до пяти. Затем попробуйте все десять возможных сравнений и выберите тот, который разбивает список как можно лучше в двух списках одинакового размера. Выполните этот раскол и примените ту же процедуру к двум спискам рекурсивно.

Я написал небольшую программу, чтобы сделать это, и вот результат.

Comparison 1: 0-1 [60|60] // First comparison item 0 with item 1, splits case 60/60
Comparison 2: 2-3 [30|30] // Second comparison for the first half of the first comparison
Comparison 3: 0-2 [15|15] // Third comparison for the first half of the second comparison for the first half of first comparison
Comparison 4: 2-4 [8|7]
Comparison 5: 3-4 [4|4]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 5: 0-4 [4|3]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-2 [1|2]
Comparison 7: 1-3 [1|1]
Comparison 4: 0-4 [8|7]
Comparison 5: 1-4 [4|4]
Comparison 6: 1-3 [2|2]
Comparison 7: 3-4 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 6: 3-4 [2|2]
Comparison 7: 0-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 5: 0-3 [4|3]
Comparison 6: 1-3 [2|2]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 6: 2-4 [2|1]
Comparison 7: 3-4 [1|1]
Comparison 3: 0-3 [15|15] // Third comparison for the second half of the second comparison for the first half of first comparison
Comparison 4: 3-4 [8|7]
Comparison 5: 2-4 [4|4]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 5: 0-4 [4|3]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 6: 1-2 [2|1]
Comparison 7: 1-3 [1|1]
Comparison 4: 0-4 [8|7]
Comparison 5: 1-4 [4|4]
Comparison 6: 1-2 [2|2]
Comparison 7: 2-4 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 6: 2-4 [2|2]
Comparison 7: 0-2 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 5: 0-2 [4|3]
Comparison 6: 1-2 [2|2]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 6: 2-4 [1|2]
Comparison 7: 3-4 [1|1]
Comparison 2: 2-3 [30|30] // Second comparison for the second half of the first comparison
Comparison 3: 0-3 [15|15]
Comparison 4: 0-4 [7|8]
Comparison 5: 0-2 [3|4]
Comparison 6: 2-4 [2|1]
Comparison 7: 3-4 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 5: 1-4 [4|4]
Comparison 6: 2-4 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 0-2 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 4: 3-4 [7|8]
Comparison 5: 0-4 [3|4]
Comparison 6: 1-2 [1|2]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 5: 2-4 [4|4]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 3: 0-2 [15|15]
Comparison 4: 0-4 [7|8]
Comparison 5: 0-3 [3|4]
Comparison 6: 2-4 [1|2]
Comparison 7: 3-4 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 5: 1-4 [4|4]
Comparison 6: 3-4 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 0-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 4: 2-4 [7|8]
Comparison 5: 0-4 [3|4]
Comparison 6: 1-2 [2|1]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 5: 3-4 [4|4]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]

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

Сортировка результата сверху путем сравнения показывает очевидную структуру для первых сравнений, но с увеличением числа сравнения становится сложнее. Все блоки симметричны относительно середины, обозначенной символом -----.

Comparison 1: 0-1 [60|60]

Comparison 2: 2-3 [30|30]
Comparison 2: 2-3 [30|30]

Comparison 3: 0-2 [15|15]
Comparison 3: 0-3 [15|15]
-----
Comparison 3: 0-3 [15|15]
Comparison 3: 0-2 [15|15]

Comparison 4: 2-4 [8|7]
Comparison 4: 0-4 [8|7]
Comparison 4: 3-4 [8|7]
Comparison 4: 0-4 [8|7]
-----
Comparison 4: 0-4 [7|8]
Comparison 4: 3-4 [7|8]
Comparison 4: 0-4 [7|8]
Comparison 4: 2-4 [7|8]

Comparison 5: 3-4 [4|4]
Comparison 5: 0-4 [4|3]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-3 [4|3]
Comparison 5: 2-4 [4|4]
Comparison 5: 0-4 [4|3]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-2 [4|3]
-----
Comparison 5: 0-2 [3|4]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-4 [3|4]
Comparison 5: 2-4 [4|4]
Comparison 5: 0-3 [3|4]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-4 [3|4]
Comparison 5: 3-4 [4|4]

Comparison 6: 1-3 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-2 [1|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 3-4 [2|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 2-4 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 1-2 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 2-4 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 2-4 [1|2]
-----
Comparison 6: 2-4 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 2-4 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-2 [1|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 2-4 [1|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 3-4 [2|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 1-2 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 1-3 [2|2]

Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
-----
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]

Ответ 4

Это должно быть 7 или более сравнений.

Существует 120 (5 факториалов) способов для размещения 5 объектов. Алгоритм, использующий 6 сравнений, может отличать только 2 ^ 6 = 64 различных начальных аранжировок, поэтому алгоритмы с использованием 6 или менее сравнений не могут сортировать все возможные входы.

Может быть способ сортировки, используя только 7 сравнений. Если вы хотите только отсортировать 5 элементов, такой алгоритм может быть найден (или доказан не существовать) грубой силой.

Ответ 5

Согласно Wikipedia:

Определение точного количества сравнений, необходимых для сортировки заданного количества записей, является сложной задачей, даже при малом n, и не существует простой формулы для решения ".

Предположительно, это означает, что нет известного приемлемого (эффективного) алгоритма для определения точно оптимальной сортировки.

Ответ 6

Сортировка сети s имеют ограниченную структуру, поэтому не отвечайте на исходный вопрос; но они веселые. Список сортировочных сетей генерирует хорошие диаграммы или списки SWAP для до 32 входов. Для 5 он дает

There are 9 comparators in this network, grouped into 6 parallel operations.  
[[0,1],[3,4]]  
[[2,4]]  
[[2,3],[1,4]]  
[[0,3]]  
[[0,2],[1,3]]  
[[1,2]]

Ответ 8

Пример последовательности операций с использованием mergesort (ниже merge функция объединит два отсортированных подсписок в один отсортированный комбинированный список):

elements[1..2] <- merge(elements[1..1], elements[2..2]) # 1 comparison
elements[3..4] <- merge(elements[3..3], elements[4..4]) # 1 comparison
elements[3..5] <- merge(elements[3..4], elements[5..5]) # 1-2 comparisons
elements[1..5] <- merge(elements[1..2], elements[3..5]) # 2-4 comparisons

Ответ 9

A B C D E

A
| C D E     - 1 Comparison
B

A C
| | E       - 1 Comparison
B D

  A
 / \
B   C   E   - 1 Comparison
     \
      D

E требуется 3 сравнения. Его следует сравнить с A, C, D

Попробуйте A-C-D-E в этом порядке.

В целом будет девять сравнений - не очень эффективный.

Ответ 10

Другие заявили, что есть 5!= 120 аранжировок (перестановок) для обработки, поэтому вам нужно 7 сравнений. Чтобы идентифицировать перестановку, в принципе вы можете построить большое вложенное выражение if в виде 7 сравнений. Определив перестановку, можно применять предварительно рассчитанную последовательность подкачки/вращения.

Первая проблема заключается в том, что выбор второго сравнения зависит от результата первого сравнения и т.д. Трюк на каждом этапе состоит в том, чтобы выбрать хорошее сравнение, чтобы разделить текущий набор возможных перестановок на два равных подмножества. Самый простой подход - оценить раскол, который будет достигнут в каждом сравнении, пока вы не найдете подходящий баланс. Выйдите рано, если вы найдете идеальный баланс, но имейте в виду, что идеальный баланс не всегда возможен, поскольку у нас нет ровно 2 ^ 7 = 128 перестановок - в некоторых случаях (я предполагаю 8) нам нужно всего шесть сравнений.

Вторая проблема заключается в разработке последовательностей подкачки/вращения для каждой из 120 возможных перестановок и, возможно, для динамического программирования. Вероятно, требуется рекурсивный поиск if-I-do-this, следующий результат - это то, что потом рекурсия "игровое дерево", и вы должны действительно кэшировать промежуточные результаты IOW. Слишком устал, чтобы выяснить детали банкомата, извините.

Вы можете поместить все этапы в орграф, который отключается (идентифицируя перестановку), а затем возвращает вентиляторы (применяя каждый шаг переупорядочения). Затем, вероятно, запустите его с помощью алгоритма минимизации орграфа.

Оберните это в генератор кода, и все готово - ваш собственный алгоритмически близкий к совершенству 5 сортировщик предметов. Тип digraph подразумевает gotos в сгенерированном коде (особенно если вы минимизируете), но люди склонны закрывать глаза на это в сгенерированном коде.

Конечно, все это немного грубая сила, но зачем беспокоиться об элегантности и эффективности - вероятность того, что вы будете запускать рабочий генератор только в любом случае, а размер проблемы достаточно мал, чтобы быть достижимым (хотя, вероятно, нет, если вы независимо от наивного "игрового дерева" выполняется поиск каждой перестановки).

Ответ 11

FWIW, здесь компактная и простая в использовании версия Python с тестами, чтобы убедиться, что она работает:

def sort5(a, b, c, d, e):
    'Sort 5 values with 7 Comparisons'
    if a < b:      a, b = b, a
    if c < d:      c, d = d, c
    if a < c:      a, b, c, d = c, d, a, b
    if e < c:
        if e < d:  pass
        else:      d, e = e, d
    else:
        if e < a:  c, d, e = e, c, d
        else:      a, c, d, e = e, a, c, d
    if b < d:
        if b < e:  return b, e, d, c, a
        else:      return e, b, d, c, a
    else:
        if b < c:  return e, d, b, c, a
        else:      return e, d, c, b, a

if __name__ == '__main__':
    from itertools import permutations

    assert all(list(sort5(*p)) == sorted(p) for p in permutations(range(5)))

Ответ 12

Невозможно иметь менее 9 сравнений для сортировки 5 элементов, когда ввод неизвестен. Нижняя граница была доказана для сортировки сетей до 10. См. Https://en.wikipedia.org/wiki/Sorting_network.

Правильность сортировки сетей может быть проверена по принципу Zero-One, как упомянуто в книге "Искусство компьютерного программирования", том 3, автор Knuth. То есть, если сеть сортировки может правильно сортировать все перестановки 0 и 1, то это правильная сеть сортировки. Ни один из алгоритмов, упомянутых в этом посте, не прошел тест Zero-one.

Кроме того, нижняя граница говорит о том, что сортировки на основе сравнения не могут иметь меньше, чем ceil (log (n!)) Компараторов для правильной сортировки, однако это не означает, что это достижимо.