1. Сколько взвешиваний понадобится сортировщику, чтобы найти
2. Сортировщик. утверждает, что один из камней – самый тяжелый. Он хочет убедить в этом скептиков при помощи нескольких взвешиваний.
3. Отсортируйте пять (заведомо попарно разных) камней за семь взвешиваний.
4. Докажите, что при некоторых порядках входа камней Сортировщику понадобится не менее log (N!) взвешиваний.
Указание. Пусть все камни разные – сколько разных перестановок?
Алгоритм сортировки использует стратегию исключений, если во внешнем цикле находится сначала самый легкий камень и выдается в окно, затем следующий и т.д.
Стратегия сортировки включениями предполагает, что на столе в любой момент находится отсортированное подмножество камней (в начале – пустое). Основной цикл состоит в добавлении нового камня в это множество, чтобы не нарушать порядка.
Вопрос. Как вы думаете, в каких случаях выгоднее использовать каждый из этих алгоритмов?
5. Напишите сортировку исключениями, используя массив размера N для хранения камней. Количество операций взвешивания не должно превышать N (N-1) / 2.
6. Частным случаем сортировки исключением является пузырьковая сортировка (bubble sort) Она происходит следующим образом: сравниваются первый и второй камни и если они находятся в неправильном порядке, то меняются местами. (эта сортировка относится к обменным сортировкам). Потом сравниваются камни находящиеся на местах 1 и 2 и т.д. Этот процесс (проход по всем парам соседних камней) проводится N раз.
7. Напишите сортировку включениями, используя массив для хранения постепенно растущего упорядоченного множества. Количество операций взвешивания меньше N log N.
В задаче 6 количество операций взвешивания имеет порядок теоретического минимума из задачи 4 (докажите!), но количество операций перемещения камней имеет порядок N2. Однако, «цена» этих операций ниже (см. 7).
8. Примем все камни, выложим на стол, перенумеруем их. Организуем на столе массив с бумажками, имеющими номера 1,2,…N. Будем теперь сортировать бумажки, причем весом бумажки будет считаться вес соответствующего камня. В конце выдаем в окно камни в порядке номеров на бумажках. Реализуйте этот алгоритм.
Сортировка слияниями реализует еще одну стратегию, основанную на идее «если есть два упорядоченных множества, их можно объединить за линейное время». Первоначально имеется N одноэлементных множеств, все они упорядочены.
Пусть дан массив длины N. Предположим, что элемент 1 является вершиной некоего дерева, ее потомки 2 и 3, в общем случае для элемента i потомки 2i и 2i+1 (если они существуют). Дерево называется регулярным, если любая вершина больше всех потомков, и почти регулярным, если это правило нарушается только в корне. Высота такого дерева приблизительно равна log N (докажите!) Важная лемма. Почти регулярное дерево можно превратить в регулярное, совершив количество перестановок в массиве, пропорциональное высоте дерева.
10. Реализовать сортировку, используя тот факт, что нижние два слоя дерева представляют собой «лес» почти регулярных деревьев (постепенно повышая высоту). После получения регулярного дерева удаляем вершину, на ее место ставим последний элемент массива, массив укорачиваем, далее в цикле. Алгоритм имеет время работы
порядка N log N и память N.
11. Цифровая сортировка Имеется массив целых чисел размера N, сами числа от 1 до M. Отсортировать их за время N + M, с таким же расходом памяти. Как вы думаете, почему «нарушается» результат задачи 4?
12. На почте имеется алгоритм для сортировки писем по шестизначному индексу. Используется 10 коробок размером N, время работы
примерно 6 N. Воспроизведите алгоритм, напишите программу.
Несколько задач на применение сортировки
13. Дано N отрезков на прямой. Найти максимальное K (по всем точкам прямой) такое, что точка покрыта K слоями отрезков.
14. Дано N точек на плоскости.
15*. Построить (при тех же ограничениях) выпуклую оболочку для N точек на плоскости.