Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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

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

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

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

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

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

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

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

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

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

 

Номер варианта Множество ключей
  9, 1, 3, 73, 7, 21, 7, 13, 6, 78

 

<== предыдущая лекция | следующая лекция ==>
Функции Генподрядчика | Внимание и сознание.
Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал