Алгоритм пирамидальной сортировки



Закрыты продажи

Описание алгоритма


Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди оставшихся n-1 элементов и т. д. Сумма первых n-1 целых равна

. Как же в таком случае можно усовершенствовать упомянутый метод сортировки ? Этого можно добиться, только оставляя после каждого прохода больше информации, чем просто идентификация единственного минимального элемента. Например, сделав n/2 сравнений, можно определить в каждой паре ключей наименьший. С помощью n/4 cравнений – меньший из пары уже выбранных меньших и т. д. Проделав n-1 сравнений, мы можем построить дерево выбора и идентифицировать его корень как нужный нам наименьший ключ.

Второй этап сортировки – спуск вдоль пути, отмеченного наименьшим элементом, и исключение его из дерева путём замены либо на пустой элемент(дырку) в самом низу, либо на элемент из соседней ветви в промежуточных вершинах. Элемент, передвинувшийся в корень дерева, вновь будет наименьшим(теперь уже вторым) ключом, и его можно исключить. После n таких шагов дерево станет пустым (то есть в нём останутся только дырки), и процесс сортировки заканчивается. Обратим внимание – на каждом из n шагов выбора требуется только log2 n cравнений. Поэтому на весь процесс понадобится порядка n log2 n элементарных операций плюс ещё n шагов на построение дерева. Это весьма существенное улучшение не только прямого метода, требующего n2 шагов, но и даже метода Шелла, где нужно n1,2 шага. Естественно, сохранение дополнительной информации делает задачу более изощрённой, поэтому в сортировке по дереву каждый отдельный шаг усложняется. Ведь в конце концов для сохранения избыточной информации, получаемой при начальном проходе, создаётся некоторая древообразная структура. Наша следующая задача – найти приёмы эффективной организации этой информации.

Конечно, хотелось бы, в частности, избавиться от дырок, которыми в конечном итоге будет заполнено всё дерево и которые порождают много ненужных сравнений. Кроме того, надо было бы поискать такое представление дерева из n элементов, которое требует лишь n единиц памяти, а не 2n-1, как это было раньше.


Содержание  Назад  Вперед