если вы можете отсортировать 5 чисел в 7 сравнениях, как отсортировать 6 чисел в 10 сравнениях?

Question

Есть еще один вопрос о сортировке 5 чисел в 7 сравнениях:

Сортировка массива с минимальным количеством сравнений

Мой вопрос касается сортировки 6 чисел в 10сравнения.

Answer 1

Вы можете сделать это за 12 тривиально :

• Сортировка первых 5 чисел с 7 сравнениями
• Сравните итоговое число с каждым из первых 5, чтобы определить его положение

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

Answer 2

Самый быстрый способ сделать это (с наименьшим возможным средним числом сравнений, равным теоретическому значению):

c1 -→ o  | 3/10 comparisons
c2 -→ o
o -→ o

Тогда после сравнения двух больших чисел (c1 и c2) имеем

o -→ c1

o -→ o -→ c2 | 4/10 comparisons
 ↘
   ↘o

Затем мы сравниваем «c1» с «c2» и получаем два возможных варианта (первый, если c1> c2, в противном случае второй)

A)Worse(26/45 of all cases)  B)Better(19/45)   | 5/10 comparisons

o -→ c1 -↘                             b-↘
           ↘                               ↘
  o -→ c2 -→ o                o -→ c1-→ c2-→ c3
   ↘                           ↘  
     ↘o                          ↘a

A) В первом случае следующим шагом будет сравнение «c1» с «c2», после чего мы можем получить A1), если c1> c2, иначе A2)

A1)                       A2)                 | 6/10
       o↘                 c1-→ c2 -→ o -→ o
          ↘                        ↗
 o -→ c1-→ c2 -→ c3              a -→ b
  ↘
    ↘a

A1) Сортируем «a» в последовательности {c1; c2; c3}, начиная со сравнения с c2, затем получаем

A1.1)                     A1.2)               | 8/10
       a↘                            a↘
          ↘                             ↘
 c1-→ c2-→ o -→ o -→ o     c1-→ c2-→ c3-→ o -→ o 

A1) Тогда нам нужно только отсортировать «a» в последовательности {c1; c2} или {c1; c2; c3}, начиная в обоих (!) Случаях A1.1 и A1.2 со сравнением с «c2» в Сравнение 1-2 (А1) или 2 (А2).

A2) Мы сортируем «a» в {c1; c2}, всегда начиная со сравнения с c1, затем мы сортируем «b» в последовательности элементов, которые меньше «a», начиная со сравнения с любым элементом (если есть 2), 2-й (если есть 3), любой из 2-го или 3-го (если в этой последовательности 4 элемента)

B) Как и выше, мы сортируем «a» в последовательности {c1; c2; c3}, начиная со сравнения с c2, после этого мы сортируем «b» в последовательности элементов, меньших чем c3, начиная со сравнения с c2 (если есть 3 элемента) или c2 или c3 (если есть 4). Это займет 3-4 сравнения. Вы также можете сделать наоборот, начиная с «b», результат не изменится.

В общей сложности этот алгоритм сортирует 6 чисел в 9 сравнениях в 19/45 случаях и в 10 сравнениях в 26/45 случаях.

Минутка теории

6! = 720, 2 ^ 9 = 512, это означает, что после 9 сравнений мы можем получить 512 разных результатов, поэтому для 304 (304 - это 512 - 2 * (720-512)) из них мы можем сказать: «Это все «Мы определенно знаем порядок», но для 208 отдыха нам нужно еще одно сравнение, чтобы отличить их от 208 других утилит с такими же результатами сравнения. 304/720 = 19/45; 208 * 2/720 = 26/45 ~ 0,578 Таким образом, наилучший из возможных алгоритмов будет иметь в среднем 9,578 сравнений. Есть еще один вариант: сортировка 5 в 7 сравнениях и сортировка 6-го элемента в 3 сравнениях впоследствии, но поскольку лучший алгоритм «5 в 7» сортирует по 6 сравнениям в 1/15 случаев, алгоритм «6 в 10» будет сортировать по 8 сравнение в 1/45 случаев (9 сравнений в 16/45 случаях, 10 сравнений в 28/45 случаях), что в среднем привело к 9,6 сравнениям.

Answer 3

Я полагаю, что вы можете добиться большего успеха, чем 13, просто по принципу O (n log n) роста.

Основной подход заключается в том, что вы разрабатываете дерево решений, которое определяет, с какой перестановкой вы имеете дело, но не чувствительно к фактическим значениям. Но если предположить, что для поиска оптимального варианта необходим исчерпывающий поиск возможных деревьев решений, необходимо помнить, что по мере увеличения количества элементов количество рассматриваемых деревьев решений быстро увеличивается на * . По предположению экспоненциально, хотя я не проверял это предположение - оно может быть даже хуже.

Вы можете добиться большего успеха, чем 13, просто жестко закодировав тесты, которые представляют собой обычный алгоритм сортировки, но не алгоритм O (n ^ 2), такой как пузырьковая сортировка или даже (я подозреваю) быстрая сортировка.

В принципе, я думаю, что идея больше проблем, чем стоит. Пять, вероятно, практический предел для жестко закодированного оптимального вида. Что-нибудь большее - просто используйте стандартный алгоритм сортировки. Хотя, держу пари, кто-то ответит с реализацией в любом случае.