Теоретические сведения. «Сортировка с использованием вспомогательного стека»

Лабораторная работа №5

«Сортировка с использованием вспомогательного стека»

Цель работы: изучить алгоритм быстрой обменной сортировки при произвольном распределении множества K ключей.

Теоретические сведения

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

Вспомогательные операции, требуемые для управления стеком и переменными i и j, не сложны, но всё же из-за них процедура быстрой сортировки разделением пригодна, в основном, при большом количестве элементов N. В рассматриваемом алгоритме с целью повышения эффективности используется несколько изменённая стратегия обработки коротких подмассивов. В нём записи R₁, …, R_N перекомпоновываются в пределах того же пространства памяти. По завершении сортировки их ключи будут упорядочены K₁≤ …≤ K_N. В алгоритме предполагается наличие искусственных ключей таких, что

Подмассивы, состоящие из M и менее элементов, являются нерассортированными слева до самого конца вычисления процедуры. Затем выполняется единственный проход сортировки методом простых вставок, где M ≥ 1 – параметр, который выбирается, как описано далее. (Это позволяет сэкономить на вспомогательных операциях, которые необходимы, если непосредственно использовать метод прямых вставок по отношению к коротким подмассивам.)

Записи с одинаковыми ключами меняются местами (это не является строго необходимым), что способствует разделению подмассивов почти пополам, если имеются равные ключи.

Вариант задания 18