Методы программирования. Кулаков Ю.В - 8 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

ляет записям перемещаться большими скачками, а не короткими шажками. Оцените время работы этого алго-
ритма и сравните его с временем сортировки простыми вставками в различных условиях. Рассмотрите другие
пути усовершенствования простых вставок, основанные на тщательном анализе структур данных. Изучите ал-
горитм L, реализующий вставки в список, и заметьте, что он не перемещает записи в памяти. Оцените время
его работы и экономию времени по сравнению с алгоритмом S, полученную за счет дополнительного простран-
ства памяти. Познакомьтесь с методом сортировки с вычислением адреса, основной идеей которого является
такое обобщение метода вставок в список, чтобы располагать не одним списком, а несколькими. Оцените эко-
номию времени от использования нескольких списков вместо одного.
Внимательно познакомьтесь с методами обменной сортировки, предусматривающей систематический обмен
местами между элементами пар, в которых нарушается упорядоченность, пока таких пар не останется. Изучите
"метод пузырька", являющийся наиболее очевидным способом сортировки, и алгоритм B его реализации. Выпол-
ните этот алгоритм вручную для некоторых входных данных и проанализируйте полученные результаты. Иссле-
дуйте время работы алгоритма B, и сравните его быстродействие с быстродействием простых вставок (алгоритм S).
Рассмотрите возможные усовершенствования "метода пузырька" и сделайте вывод о его достоинствах. Рассмотри-
те метод обменной сортировки со слиянием, который предусматривает подбор для сравнений некоторых пар несо-
седних ключей, и алгоритм M его реализации. Познакомьтесь с доказательством того, что магическая последова-
тельность сравнений и обменов, описанная в алгоритме М, действительно сортирует любой файл. Изучите метод
Хоара быстрой сортировки (обменной сортировки с разделением), в котором результат каждого сравнения исполь-
зуется для определения, какие ключи сравнивать следующими. Обратите внимание на то, что такая стратегия не
годится для параллельных вычислений, но может оказаться плодотворной для вычислительных машин, работаю-
щих последовательно. Рассмотрите алгоритм Q обменной сортировки с разделением и проведите его анализ. Изу-
чите метод обменной поразрядной сортировки, основанный на двоичном представлении ключей, и рассмотрите
реализующий его алгоритм R. Оцените время работы алгоритма обменной поразрядной сортировки и сделайте вы-
воды о его быстродействии.
Рассмотрите еще одно важное семейство методов сортировки, называемое сортировкой посредством вы-
бора, которое основано на идее многократного выбора сначала записи с наименьшим ключом, затем записи с
ключом, наименьшим из оставшихся, и так далее, пока не будут выбраны все записи. Изучите алгоритм S сор-
тировки посредством простого выбора, выполните его вручную для некоторых входных данных и проанализи-
руйте полученные результаты. Оцените время работы этого алгоритма и сравните с быстродействием алгорит-
ма простых вставок (алгоритм S), а также с "методом пузырька" (алгоритм В). Рассмотрите усовершенствования
простого выбора, основанные на том, что информация, полученная после первого шага выбора, используется
при последующих выборах. В частности, рассмотрите сортировку посредством выбора из дерева и алгоритм H
пирамидальной сортировки. Проанализируйте эффективность алгоритма H в сравнении с сортировкой методом
Шелла с убывающим шагом (алгоритм D) и быстрой сортировкой Хоара (алгоритм Q).
Познакомьтесь с множеством сортировок слиянием, где слияние означает объединение двух или более
упорядоченных файлов в один упорядоченный файл. Изучите алгоритм M сортировки двухпутевым слиянием,
выполните его вручную для некоторых входных данных. Проанализируйте этот алгоритм. Затем рассмотрите
алгоритм N сортировки естественным двухпутевым слиянием, проанализируйте его и сравните с быстрой и
пирамидальной сортировками. Изучите алгоритм S сортировки простым двухпутевым слиянием, оцените время
его работы и сравните с алгоритмом N. Рассмотрите алгоритмы N и S с точки зрения структур данных и рас-
смотрите алгоритм L сортировки посредством слияния списков. Оцените затраты памяти и время работы алго-
ритмов для связанного и последовательного распределения памяти, проведите сравнительный анализ и сделай-
те выводы.
Изучите интересный класс методов распределяющей сортировки, являющейся, по существу, прямо противо-
положной слиянию. Рассмотрите алгоритм R поразрядной сортировки списка, использующий связанные структу-
ры данных, и вспомогательный алгоритм H сцепления очередей. Выполните такую сортировку вручную для неко-
торых входных данных и проанализируйте полученные результаты. Оцените время работы алгоритма R, сравните
с временем работы других алгоритмов, построенных на основе аналогичных предположений (метод сортировки с
вычислением адреса и алгоритм L сортировки посредством слияния списков), и сделайте выводы.
2.3. Внешняя сортировка
Познакомьтесь с понятием внешней сортировки. Обратите внимание на то, что внешняя сортировка в кор-
не отлична от внутренней, т.к. время доступа к файлам на внешних носителях нас жесточайшим образом лими-
тирует. Уясните, что внешняя сортировка сводится в основном к внутренней сортировке с последующим
"внешним слиянием".
Изучите метод многопутевого слияния и выбора с замещением, являющийся расширением метода внут-
ренней сортировки, основанного на двухпутевом слиянии – процессе объединения двух упорядоченных после-
довательностей в одну. Познакомьтесь с понятиями дерева выбора, выбора с замещением и дерева "проиграв-
ших". Изучите процедуру получения начальных отрезков посредством выбора с замещением и алгоритм R вы-
бора с замещением.
После того как станет понятным образование начальных отрезков, рассмотрите различные методы распре-
деления отрезков на внешних носителях (лентах) и слияния их до тех пор, пока не получится единственный
отрезок. Изучите алгоритм D сортировки многофазным слиянием с использованием "горизонтального" распре-
деления. Рассмотрите другую основную схему, называемую "каскадным слиянием", и модификацию каскадной
сортировки, когда добавлена еще одна лента и почти все время перемотки в течение каскадной сортировки
можно совместить. Познакомьтесь еще с одним подходом к сортировке слиянием, называемым осциллирующей

Страницы