Slash0

  • 31 мая 2012 г.
  • 2488 Слова
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
НАЦИОНАЛЬНАЯ МЕТАЛУРГИЧЕСКАЯ АКАДЕМИЯ УКРАИНЫ

КУРСОВАЯ РАБОТА

По дисциплине: «Теория алгоритмов»

Тема: «Сортировка слиянием без копирования»

Проверил:
Козлов В.П.
« » 2009Выполнил ст.гр. ИТС-06

« » 2009

2009
Содержание

1. Введение........................................................................................................................................2
2.Двухпутевое слияние…………………………………………………………………...………..3
3. Сортировка слиянием безкопирования……………………......................................................5
4.Листинг программы……………………………………………………………………………...7
5. Анализ эффективности…………………………………………………..……………………..10
6. Пример работы программы………………………………………………...…………………..11
7. Вывод………………………………………………...…………………………………………..11
8.Список литературы……………………………………………...……………………………….12

1. Введение

Семейство алгоритмов быстрой сортировки, основано на операциивыборки: нахождение k-то минимальною элемента в файле. Мы убедились в том, что выполнение операции выборки аналогично делению файла на две части, на часть, содержащую все к наименьших элементов, и часть, содержащую N— k больших по значению элементов. В этой главе исследуется семейство алгоритмов сортировки, в основе которых лежит вспомогательный процесс, известный как слияние, т.е., объединение двухотсортированных файлов в один файл большего размера. Слияние является основой для простого алгоритма сортировки типа "разделяй и властвуй", а также для его двойника — алгоритма восходящей (снизу-вверх) сортировки слиянием, при этом оба из них достаточно просто реализуются. Выборка и слияние — суть вспомогательные операции
в том смысле, что выборка разбивает файл на два независимых файла, в то время какслияние объединяет два независимых файла в один. Контраст между этими двумя операциями становится очевидным, если применить принцип "разделяй и властвуй" для создания конкретных методов сортировки. Можно изменить организацию файла таким образом, что когда обе части файла подвергаются сортировке, упорядочивается и весь файл; и наоборот, можно разбить файл на две части для последующей сортировки, а затемобъединить упорядоченные части, чтобы получить весь файл в упорядоченном виде. Мы уже видели, что получается в первом случае: это ни что иное как быстрая сортировка, которая состоит из процедуры выборки, за которой следуют два рекурсивных вызова.
В этой главе рассматривается сортировка слиянием (mergesort), которая является дополнением быстрой сортировки в том, что она состоит из двух рекурсивных вызововс последующей процедурой слияния.
Одним из наиболее привлекательных свойств сортировки слиянием является тот
факт, что она сортирует файл, состоящий из N элементов, за время, пропорциональное NlogN, независимо от характера входных данных. Основной недостаток сортировки слиянием заключается в том, что прямолинейные реализации этого алгоритма требуют дополнительного пространства памяти,пропорционального N. Это препятствие можно обойти, однако сделать это довольно сложно, причем потребуются дополнительные затраты, которые в общем случае не оправдываются на практике, особенно если учесть, что существует альтернатива в виде пирамидальной сортировки. Получить программную реализацию сортировки слиянием не труднее, чем реализацию пирамидальной сортировки, при этом длина внутреннего циклапринимает среднее значение между аналогичными показателями быстрой сортировки и пирамидальной сортировки, следовательно, сортировка методом слияния достойна того, чтобы к ней проявить внимание в случае, когда на первый план выходят такие показатели как быстродействие, необходимость избегать наихудших случаев, возможность использования...
tracking img