Сортировка

Сортировка.


Дано множество из n камней одинакового внешнего вида. Можно сравнивать их по весу с помощью чашечных весов без гирь (на каждую чашку помещается ровно один камень). Камни в произвольном порядке подаются через входное окошко в комнату, в которой находится Сортировщик. От него требуется выдать через выходное окошко все поданные ему на входное окошко камни, о в порядке неубывания веса. У сортировщика имеются весы и стол, на котором он может выкладывать камни, делать на них и на столе пометки мелом и т.п. Кроме входного и выходного окон других отверстий в комнате нет.


Задачи


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

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

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

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

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


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


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

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


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


6.

Частным случаем сортировки исключением является пузырьковая сортировка (bubble sort) Она происходит следующим образом: сравниваются первый и второй камни и если они находятся в неправильном порядке, то меняются местами. (эта сортировка относится к обменным сортировкам). Потом сравниваются камни находящиеся на местах 1 и 2 и т.д. Этот процесс (проход по всем парам соседних камней) проводится n раз.

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

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


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


8.

Примем все камни, выложим на стол, перенумеруем их. Организуем на столе массив с бумажками, имеющими номера 1, 2, … n. Будем теперь сортировать бумажки, причем весом бумажки будет считаться вес соответствующего камня. В конце выдаем в окно камни в порядке номеров на бумажках. Реализуйте этот алгоритм.

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

9.
Пусть во всех камнях есть дырки, и первоначально их разделили поровну и надели как бусы на две веревки. Крайний камень можно снимать с левого конца веревки и надевать на правый. Есть еще две запасных веревки.

  1. Реализуйте сортировку слиянием, которая потребует n log n операций с камнями (взвешиваний, сниманий, надеваний).
  2. Напишите программу для предыдущей задачи, используя два массива длины n.

10.
Пусть дан массив длины n. Предположим, что элемент 1 является вершиной некоего дерева, ее потомки 2 и 3, в общем случае для элемента i потомки 2i и 2i+1 (если они существуют). Дерево называется регулярным, если любая вершина больше всех потомков, и почти регулярным, если это правило нарушается только в корне. Высота такого дерева приблизительно равна log n (докажите!) Важная лемма. Почти регулярное дерево можно превратить в регулярное, совершив количество перестановок в массиве, пропорциональное высоте дерева.


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


11.
Цифровая сортировка Имеется массив целых чисел размера N, сами числа от 1 до M. Отсортировать их за время N + M, с таким же расходом памяти. Как вы думаете, почему «нарушается» результат задачи 4?


12.
На почте имеется алгоритм для сортировки писем по шестизначному индексу. Используется 10 коробок размером n, время работы
примерно 6 n. Воспроизведите алгоритм, напишите программу.