Школа179: Oner Xaum/Сортировка ...

Сортировка.

1.
Сколько взвешиваний понадобится сортировщику, чтобы найти

1. самый тяжелый камень?
2. два самых тяжелых камня?
3. самый тяжелый и самый легкий камень?

2.
Сортировщик. утверждает, что один из камней – самый тяжелый. Он хочет убедить в этом скептиков при помощи нескольких взвешиваний.

1. сколько взвешиваний (самое меньшее) ему понадобится?
2. то же для двух самых тяжелых камней.

3.
Отсортируйте пять (заведомо попарно разных) камней за семь взвешиваний.

4.
Докажите, что при некоторых порядках входа камней Сортировщику понадобится не менее log (n!) взвешиваний.
Указание. Пусть все камни разные – сколько разных перестановок?

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

5.
Напишите сортировку исключениями, используя массив размера n для хранения камней. Количество операций взвешивания не должно превышать n (n – 1) / 2.

6.

1. Докажите, корректность пузырьковой сортировки (т.е. что таким способом действительно все камни будут отсортированы)
2. Сколько действий (сравнений, обменов) нам потребуется в среднем и наихудшем случаях?
3. Постарайтесь улучшить этот способ, сохраняя общую идею, (т. е. сравнение и обмен соседних элементов)
4. Напишите соответствующую программу.

7.
Напишите сортировку включениями, используя массив для хранения постепенно растущего упорядоченного множества. Количество операций взвешивания меньше nlog n.

В задаче 6 количество операций взвешивания имеет порядок теоретического минимума из задачи 4 (докажите!), но количество операций перемещения камней имеет порядок n². Однако, «цена» этих операций ниже (см. 7).

8.

Сортировка слияниями реализует еще одну стратегию, основанную на идее «если есть два упорядоченных множества, их можно объединить за линейное время». Первоначально имеется N одноэлементных множеств, все они упорядочены.

1. 1. Реализуйте сортировку слиянием, которая потребует N log N операций с камнями (взвешиваний, сниманий, надеваний).

1. 1. Напишите программу для предыдущей задачи, используя два массива длины 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 точек на плоскости.

1. Построить N-1-звенную несамопересекающуюся ломаную, проходящую через все эти точки. Число действий N log N.

1. То же, но ломаная N-звенная замкнутая.

15*. Построить (при тех же ограничениях) выпуклую оболочку для N точек на плоскости.