Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Общие представления о методах сортировки).pdf

Обратите внимание, что для выполнения внешней сортировки с использованием метода прямого слияния необходимо разместить только две переменные в основной памяти - для размещения следующих записей из файлов B и C. Для файлов A, B и C будет O (logn) раз прочитал и столько раз написал [1].

4.2.Естественное слияние

При использовании метода прямого слияния не учитывается, что исходный файл может быть частично отсортирован, т.е. содержать упорядоченные подпоследовательности записей. Серия - это подпоследовательность записей a (i), a (i + 1), ..., a (j), такая, что a (k) <= a (k + 1) для всех i <= k <j, a (i) <a (i-1) и a (j)> a (j + 1). Метод естественного слияния основан на распознавании рядов при распределении и их использовании при последующем слиянии [1].

Как и в случае прямого слияния, сортировка выполняется в несколько этапов, каждый из которых сначала распределяет файл A в файлы B и C, а затем объединяет B и C в файл A. Распределение распознает первую серию записей и перезаписывает ее в файл B, второй находится в файле C и т. д. При слиянии первая серия записей файла B объединяется с первой серией файла C, вторая серия B - со второй серией C и так далее. Если просмотр одного файла заканчивается раньше, чем просмотр другого (из-за разного количества эпизодов), то оставшаяся часть незапрошенного файла копируется в конец файла A. Процесс заканчивается, когда в файле A остается только одна серия [3]. Пример сортировки файлов показан на [рисунках 8 и 9] в приложении.

Очевидно, что число операций чтения / перезаписи файлов с использованием этого метода будет не хуже, чем с помощью метода прямого слияния, и в среднем будет лучше. С другой стороны, число сравнений увеличивается за счет тех, которые необходимы для распознавания концов ряда. Кроме того, поскольку длина ряда может быть произвольной, максимальный размер файлов B и C может быть близок к размеру файла A [4].

4.3.Улучшение эффективности внешней сортировки за счет использования основной памяти

Понятно, что чем дольше серия содержит файл до начала применения внешней сортировки, тем меньше требуется слияний и тем быстрее заканчивается сортировка. Поэтому, прежде чем применять какой-либо из внешних методов сортировки, основанных на серии, исходный файл считывается по частям в основную память, один из наиболее эффективных алгоритмов внутренней сортировки (обычно Quicksort или Heapsort) применяется к каждой части и сортируется, части (образующие серию) записываются в новый файл (в старом не могут, потому что он чисто последовательный) [6].

Кроме того, конечно, при выполнении выделений и слияний используется буферизация блоков файла (ов) в основной памяти. Возможный прирост производительности зависит от наличия достаточного количества буферов достаточного размера [6].

Заключение

Проблема сортировки в программировании не решена полностью. Хотя существует большое количество алгоритмов сортировки, целью программирования является не только разработка алгоритмов сортировки элементов, но и разработка наиболее эффективных алгоритмов сортировки.

Рассмотренные в данной курсовой работе методы сортировки имеют как достоинства, так и недостатки. Выбор алгоритма сортировки зависит от конкретной задачи.

Таким образом, сортировка большого количества элементов пузырьковым методом, методом вставки или выделения займет много времени, поскольку время выполнения сортировки находится в квадратичной зависимости от количества элементов массива. Для больших объемов данных эти сортировки будут медленными, и, начиная с определенного значения, они будут слишком медленными для использования на практике. Тем не менее, они идеально подходят для сортировки небольшого количества предметов. Кроме того, сортировка по вкладышу имеет два преимущества. Во-первых, он имеет естественное поведение, то есть он работает быстрее для упорядоченного массива и длится дольше всего, когда массив упорядочен в противоположном направлении. Это делает сортировку вставками полезной для упорядочивания почти отсортированных массивов. Во-вторых, элементы с одинаковыми ключами не переставляются: если список элементов отсортирован с использованием двух ключей, то после завершения сортировки путем вставки он все равно будет упорядочен по двум ключам.

Наконец, некоторые из простых методов могут быть расширены до лучших методов или использованы для улучшения более сложных. Например, такой как метод Hoare и метод Shell.

Библиография

Книги:

1. Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д., Структура данных и алгоритмы: Пер. с англ.: Учебное пособие – М.: Издательский дом «Вильямс», 2000 г. – 384 с., илл.

2. Вирт Никлаус,Алгоритмы и структуры данных: Пер. с англ. – М.: Издательство ДМК пресс», 2013 г. – 272 с., илл.

3. Кнут Д. Э., Искусство программирования. Том 1. Основные алгоритмы. — СПб.: Вильямс, 2015. — 720 с.

4. Кнут Д. Э. Искусство программирования, Том 3. Сортировка и поиск. — М.: Издательский дом «Вильямс», 2010.

5. Луридас, Панос, Алгоритмы для начинающих: теория и практика для разработчика – М., Издательство ЭКСМО», 2018 г. – 608 с., илл.

6. Томас, X. Кормен, Чарльз И. Лейзерсон, Алгоритмы. Построение и анализ. — СПб.: Вильямс, 2016. — 1328 с.

Статьи:

1. Антонова И. И., Карих О. А. Оценка эффективности параллельных алгоритмов задачи сортировки данных // Промышленные АСУ и контроллеры. — 2010. — № 3. — С. 23—25.
2. Дупленко A. Г. Сравнительный анализ алгоритмов сортировки данных в массивах // Молодой ученый. — 2013. — № 8. — С. 50-53.
3. Мартынов В.А., Миронов В.В. Параллельные алгоритмы сортировки данных с использованием технологии MPI // Вестник Сыктывкарского университета. Серия 1: Математика. Механика. Информатика. — 2012. — № 16. — С. 130-135.
4. Никитин Ю. Б. Сложность алгоритмов сортировки на частично упорядоченных множествах: автореферат дис.... канд. физ.-мат. наук: 01.01.09 / Никитин Юрий Борисович. — Москва, 2001. — 80 с.

Приложения

Рис.1. Демонстрация сортировки по неубыванию методом «пузырька»

Рис.2. Демонстрация сортировки вставками по неубываниюдля массива [5,2,4,3,1]