Специальные методы сортировки a

Рис. 11.3. Четыре случая слияния типа 0-1
Каждый из этих четырех примеров состоит из 5 строк: задача слияния типа 0-1; результат выполнения операции обратного тасования, порождающий две подзадачи слияния; результат рекурсивного завершения слияний; результат тасования и результат завершающих нечетно-четных сравнений. На последнем этапе обмен выполняется только если количество нулей в обоих входных файлах нечетно.
Упражнения
11.1. Приведите результат тасования и обратного тасования ключей E A S Y Q U E S T I O N.
11.2. Обобщите программу 11.1 для реализации h-путевых тасования и обратного тасования. Обеспечьте работоспособность примененной стратегии для случая, если размер файла не кратен h.
11.3. Реализуйте операции тасования и обратного тасования без использования вспомогательного массива.
11.4. Покажите, что линейная программа, которая сортирует N различных ключей, сможет отсортировать и N не обязательно различных ключей.
11.5. Покажите, как линейная программа, приведенная в тексте, сортирует каждую из шести перестановок чисел 1, 2 и 3.
11.6. Приведите пример линейной программы, которая выполняет сортировку четырех элементов.
11.7. Докажите лемму 11.1. Совет: Покажите, что если программа не способна отсортировать некоторый входной массив с произвольными ключами, то существует некоторая последовательность нулей и единиц, которую она также не может отсортировать.
11.8. Покажите, в стиле диаграммы на рис.11.2, как программа 11.2 выполняет слияние ключей A E Q S U Y E I N O S T.
11.9. Выполните упражнение 11.8 для ключей A E S Y E I N O Q S T U.
11.10. Выполните упражнение 11.8 для ключей 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0.
11.11. Эмпирически сравните время выполнения сортировки слиянием Бэтчера с временем выполнения стандартной нисходящей сортировки слиянием (программы 8.3 и 8.2) для N = 10³, 10⁴, 10⁵ и 10⁶ .
11.12. Приведите такие реализации функций compexch, shuffle и unshuffle, что программы 11.2 и 8.3 будут работать в режиме косвенной сортировки (см. "Элементарные методы сортировки" ).
11.13. Приведите такие реализации функций compexch, shuffle и unshuffle, что программы 11.2 и 8.3 будут выводить для заданного N линейную программу сортировки N элементов. Для отслеживания значений индексов можно воспользоваться вспомогательным глобальным массивом.
11.14. Если переставить элементы второго сливаемого файла в обратном порядке, получится битоническая последовательность (см. определение в "Слияние и сортировка слиянием" ). После изменения заключительного цикла программы 11.2 так, чтобы он начинался с l, а не с l+1, получится программа, сортирующая битонические последовательности. Покажите, в стиле диаграммы на рис. 11.2, как с помощью этого метода выполняется слияние ключей A E S Q U Y T S O N I E.
11.15. Докажите, что модификация программы 11.2, описанная в упражнении 11.14, способна отсортировать любую битоническую последовательность.