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

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

13 голосов
/ 08 октября 2009

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

Ответы [ 12 ]

33 голосов
/ 08 октября 2009

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

18 голосов
/ 08 октября 2009

Это псевдокод, основанный на ответе Беты. Могут быть некоторые ошибки, поскольку я сделал это в спешке. 

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)
6 голосов
/ 08 октября 2009

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

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

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

6 голосов
/ 08 октября 2009

Пять предметов могут быть отсортированы с семью сравнениями в худшем броске, потому что 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]
3 голосов
/ 08 октября 2009

Согласно Википедии :

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

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

2 голосов
/ 10 ноября 2016

Я написал реализацию C решения этой проблемы, которую можно найти здесь: Сортировка 5 элементов с использованием 7 сравнений

Мой код хорошо прокомментирован с объяснением того, почему он работает.

2 голосов
/ 22 октября 2009

Сортировка сети с иметь ограниченную структуру, так что не отвечайте на первоначальный вопрос; но они веселые.
Список сетей сортировки генерирует хорошие диаграммы или списки 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]]
1 голос
/ 25 августа 2016

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)))
1 голос
/ 08 октября 2009

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

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

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

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

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

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

1 голос
/ 08 октября 2009 

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 в таком порядке.

Всего будет девять сравнений - не очень производительных.

Страница:
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...