Сообщение от
bellaps
Как отсортировать 8 чисел только 16 сравнениями??
Ну алгоритм тут довольно хитрый (описан у Кнута) и с не очень большой практической ценностью. Обычный merge sort отсортирует за 17 сравнений и это будет намного практичнее.
А за 16 сравнений это делается так:
1. Сначала сортируем элементы в парах, на что понадобится 4 сравнения
[b1][a1] [b2][a2] [b3][a3] [b4][a4]
Теперь у нас b1 < a1, b2 < a2 и т.д.
2. Теперь полностью упорядочиваем между собой пары по возрастанию старших элементов пар
a. На это потребуется 5 сравнений
[b1][a1] [b2][a2] [b3][a3] [b4][a4]
То есть пусть теперь у нас a1 < a2 < a3 < a4 и в то же время b1 < a1, b2 < a2 и т.д.
3. Теперь мысленно извлекаем элементы
b из последовательности
[a1][a2][a3][a4]
и вставляем их по одному обратно в правильные места в такой очередности: b1, b3, b2, b4.
3.1. b1 уже находился на своем месте, поэтому мы вставляем его обратно без сравнения вообще
[b1][a1][a2][a3][a4]
3.2. b3 (который меньше a3) должен попасть куда-то до a3. На бинарный поиск места для вставки среди 3 элементов надо 2 сравнения.
Тут могут получиться разные варианты:
[b3][b1][a1][a2][a3][a4]
[b1]
[b3][a1][a2][a3][a4]
[b1][a1]
[b3][a2][a3][a4]
[b1][a1][a2]
[b3][a3][a4]
3.3. b2 (который меньше a2) должен попасть куда-то до a2. Обратите внимание, что область поиска в любом случае - 3 или 2 элемента. На бинарный поиск места для вставки надо 2 сравнения.
Количество возможных исходов тут вырастает и я их "рисовать" не буду.
3.4. b4 (который меньше a4) должен попасть куда-то до a4. Тут просто делается бинарный поиск места для вставки среди 6 элементов, на который надо 3 сравнения.
Все. Итого 4+5+2+2+3 = 16 сравнений.
Уменьшение количества сравнений возникает за счет хитрого выбора порядка вставки элементов
b обратно в последовательность. И порядок этот диктуется так называемыми
Числами Якобсталя.
