Наименьшее количество сравнений, необходимых для сортировки (заказа) 5 элементов

Найдите наименьшее количество сравнений, необходимое для сортировки (упорядочения) пяти элементов, и разработайте алгоритм, который сортирует эти элементы, используя это количество сравнений.

Решение : их 5! = 120 возможных результатов. Поэтому двоичное дерево для процедуры сортировки будет иметь по крайней мере 7 уровней. Действительно, ≥ 120 означает≥ 7. Но 7 сравнений недостаточно. Наименьшее количество сравнений, необходимых для сортировки (упорядочивания) пяти элементов, составляет 8.$2^h$$h$

Вот мой актуальный вопрос: я найти алгоритм , который делает это в 8 сравнения , но как я могу доказать , что это не может быть сделано в 7 сравнений?

Решение неверное. Демут [1; через 2, сек 5.3.1] показывает, что пять значений могут быть отсортированы с использованием только семи сравнений, т. Е. Нижняя граница «теоретической информации» в этом случае является жесткой.

Ответ - метод, разработанный для $n=5$ , а не общий алгоритм. Это тоже не очень приятно. Это схема:

1. Сортировка первых двух пар.

2. Закажите пары по их соответствующему большему элементу.

   Назовите результат $[a,b,c,d,e]$ ; мы знаем, $a<b<d$ и $c<d$ .

3. Вставьте $e$ в $[a,b,d]$ .

4. Вставьте $c$ в результат шага 3.

Первый шаг явно требует двух сравнений, второй только один. Последние два шага занимают два сравнения каждый; мы вставляем в список из трех элементов в обоих случаях (для шага 4. обратите внимание, что мы знаем из что меньше, чем последний элемент списка в списке) и сначала сравниваем со средним элементом. Всего получается семь сравнений.$c<d$$c$

Поскольку я не вижу, как написать «хороший» псевдокод этого, посмотрите здесь для протестированной (и, надеюсь, читаемой) реализации.

1. Кандидат наук. Дипломная работа (Стэнфордский университет) Х.Б. Демута (1956)

   См. Также Электронная сортировка данных по HB Demuth (1985)

2. Сортировка и поиск Дональд Э. Кнут; Искусство компьютерного программирования Vol. 3 (2-е изд, 1998)

Теоретическая нижняя граница сортировки на основе сравнения равна . То есть, чтобы отсортировать элементов, используя только сравнения или требуется по крайней мере логарифм по основанию 2 дляследовательно, операций.$\log(n!)$$n$$<$$>$n ! log ( 5 ! ) ≈ 6,91$n!$$\log(5!) \approx 6.91$

Поскольку и , используя двоичное дерево решений, вы можете отсортировать 5 элементов за 7 сравнений. Дерево точно определяет, какая из 120 перестановок у вас есть, а затем выполняет перестановки, необходимые для его сортировки.$5!= 120$$2^7= 128$

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

я думал о быстрой сортировке. Вы выбираете в качестве точки поворота элемент, который просто является средним элементом. сравните ось с оставшимися 4 пунктами, в результате чего будут отсортированы две стопки. каждая из этих куч может быть отсортирована за 1 сравнение. если я не совершил ужасную ошибку, 5 пунктов были полностью отсортированы всего за 6 сравнений, и я думаю, что это абсолютное наименьшее количество сравнений, необходимых для выполнения работы. Первоначальный вопрос был найти наименьшее количество сравнений для сортировки 5 элементов.

Если вы можете проверить алгоритм, проверьте его на всех комбинациях чисел. Если у вас много номеров, протестируйте множество случайных комбинаций. Не точно, но быстрее всех комбинаций.

Минимальное
a <b <c = 2
a <b <c <d = 3
a <b <c <d <e = 4

Максимум
3 ^ 3
4 ^ 4
5 ^ 5

Вставьте в середину используйте 3-6 для 4 чисел.
Слияние используйте 4-5 для 4 номеров.
Минимальное сравнение по вики - 5 для 4 чисел :) Для 5 - 7. Вы используете 8, все еще так много.
https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list
Если вы знаете все до сравнений, вы можете пойти вниз с сравнениями. Мой средний показатель по 4 числам составляет 3,96 / 1024 всех комбинаций.