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

Пусть имеется некоторый последовательный файл А, который включает в себя записи а1, а2,…, аn. Каждая такая запись состоит из одного ключевого элемента. Для сортировки прямым слиянием необходимы два вспомогательных файла В и С, размер каждого из них равен n/2. В таблице 5 показан пример внешней сортировки простым слиянием.

Таблица 5

Внешняя сортировка простым слиянием

Данный метод сортировки состоит из последовательных шагов. На каждом таком шаге выполняется распределение файла А в файлы В и С, а затем осуществляется слияние файлов В и С в исходный файл А. Файл А содержит записи: 8 23 5 95 44 33 2 6. Размер файла А=8, таким образом, размер вспомогательных файлов В и С равен n/2=4. Сначала осуществляется начальное распределение: последовательно считываются записи файла А, записи a1, a3, ..., a(n-1) пишутся в файл B, а записи a2, a4, ..., an - в файл C. То есть файл В содержит элементы: 8 5 44 2, а файл С: 23 95 33 6. На втором шаге снова осуществляется последовательное считывание файла А, при этом в файл В записываются последовательные пары с нечетными номерами, а в файл С – с четными. В процессе слияния образуются упорядоченные четверки записей. Они записываются в файл А.

И так продолжается до последнего шага. Перед последним шагом, файл А будет содержать две упорядоченные подпоследовательности размером n/2 каждая. В процессе очередного распределения первая из них попадает в вспомогательный файл В, а вторая в С. В результате слияния исходный файл А будет содержать полностью упорядоченную последовательность записей.

Стоит отметить, при данном методе сортировки необходимы всего две переменные, расположенные в основной памяти. Данные переменные необходимы для размещения очередных записей из файлов В и С. Все файлы (А, В и С) будут прочитаны и записаны по O(log n) раз.

3.2 Естественное слияние

Недостатком предыдущего метода можно считать то, что при прямом слияние не рассматривается то факт, что исходный файл может быть уже частично отсортирован. Устранить данный недостаток призван метод естественного слияния. Он основан на распознавании упорядоченных подпоследовательностей при распределении и их использование при дальнейшем слиянии. При этом методе сортировка выполняется за несколько шагов, как и при методе прямого слияния. На каждом шаге сначала выполняется распределение исходного файла А по вспомогательным В и С, а потом слияние вспомогательных в исходный файл. При распределении распознается первая серия записей и переписывается в файл B, вторая - в файл C и т.д. В процессе слияние осуществляется сливание первой серии файла В с первой серией файла С, второй серии файла В со второй серией С и т.д. В случае, если по причине разного размера серий, просмотр одного файла закончился раньше, чем просмотр другого, то остаток большего файла записывается в конец исходного файла целиком. Процесс сортировки методом естественного слияния заканчивается, когда в исходном файле А остается одна серия. Пример данной сортировки представлен на рисунках 1 и 2.

 
Рисунок 1 – Первый шаг

 
Рисунок 2 – Второй шаг

При использовании метода естественного слияния число чтений и записи файлов будет меньше, чем при использовании метода прямого слияния. Но с другой стороны увеличивается число сравнений, это обуславливается распознаванием концов серий. Кроме того, поскольку длина серий может быть произвольной, то максимальный размер файлов B и C может быть близок к размеру файла A.

2.3 Сбалансированное многопутевое слияние

В основе сбалансированного многопутевого слияния лежит распределение серий исходного файла по нескольким вспомогательным, то есть по по m вспомогательным файлам B1, B2, ..., Bm и их слияние в m вспомогательных файлов C1, C2, ..., Cm. На следующем шаге производится слияние файлов C1, C2, ..., Cm в файлы B1, B2, ..., Bm и т.д., пока в B1 или C1 не образуется одна серия. Сбалансированное многопутевое слияние является развитием идеи двухпутевого слияния, использованного в предыдущих методах сортировки. Простой пример использования данного метода представлен на рисунке 3.

Рисунок 3 – Многопутевое слияние

Данный метод сортировки имеет следующие преимущества: число проходов алгоритма оценивается как O(log n) (n - число записей в исходном файле), где логарифм берется по основанию n. Порядок числа копирований записей равен O(log n). Но число сравнений не будет меньше, чем при использовании метода простого слияния.

Таким образом, чем более длинные серии содержит файл перед началом применения внешней сортировки, тем меньше потребуется слияний и тем быстрее закончится сортировка. Поэтому до начала применения любого из методов внешней сортировки, основанных на применении серий, начальный файл частями считывается в основную память, к каждой части применяется один из наиболее эффективных алгоритмов внутренней сортировки. Кроме того, конечно, при выполнении распределений и слияний используется буферизация блоков файла(ов) в основной памяти. Возможный выигрыш в производительности зависит от наличия достаточного числа буферов достаточного размера.

ЗАКЛЮЧЕНИЕ

Важность сортировки основана на том факте, что на ее примере можно показать многие основные фундаментальные приемы и методы построения алгоритмов. Сортировка является хорошим примером огромного разнообразия алгоритмов, которые выполняют одну и ту же задачу. Кроме того, многие из них имеют определенные преимущества друг перед другом. За счет усложнения алгоритма можно добиться существенного увеличения эффективности и быстродействия алгоритма по сравнению с более простыми методами. Как правило, термин сортировка понимают, как процесс перестановки объектов некоторого множества в определенном порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве.

Различают методы внутренней и внешней сортировки. К методу внутренней сортировки относят методы сортировки массив.

Методы сортировки массивов можно разделить на три основных класса в зависимости от лежащего в их основе метода:

• сортировка пузырьком;
• сортировка выбором;
• сортировка включением.

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

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

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

Методы внешней сортировки используются, когда исходный файл, содержащий записи, не может быть полностью помещен в основную память. Существуют следующие методы внешней сортировки: метод прямого слияния, метод естественного слияния, метод сбалансированного многопутевого слияния. Чем более длинные серии содержит файл перед началом применения внешней сортировки, тем меньше потребуется слияний и тем быстрее закончится сортировка. Поэтому до начала применения любого из методов внешней сортировки, основанных на применении серий, начальный файл частями считывается в основную память, к каждой части применяется один из наиболее эффективных алгоритмов внутренней сортировки.

В ходе выполнения курсовой работы рассмотрены этапы эволюции методов сортировки данных, выполнен сравнительный анализ и изучены основные методы сортировки данных.

Получены навыки ведения самостоятельных теоретических и практических исследований и навыки правильного оформления научно-исследовательской работы. Также приобретен опыт обработки, анализа и систематизации результатов практических исследований по направлению обучения.

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Алексеев Е.Р., Чеснокова О.В., Кучер Т.В., Самоучитель по программированию на Free Pascal и Lazarus. - Донецк.: ДонНТУ, Технопарк ДонНТУ УНИТЕХ, 2013. – 503 с.
2. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 2011. - 360 с.
3. Гагарина Л.Г., Алгоритмы и структуры данных: Учебное пособие. – М.: ИНФРА-М, 2013. – 304 с.: ил, ISBN 978-5-16-003-682-3.
4. Гагарина Л.Г., Алгоритмы и структуры данных: Учебное пособие. – М.: ИНФРА-М, 2012. – 304 с.: ил, ISBN 978-5-16-003-682-3.
5. Демидов Д.В., Основы программирования на языке Pascal в примерах: Учебное пособие. – М.: НИЯУ МИФИ, 2010. – 172 с.
6. Демидов Д.В., Основы программирования на языке Pascal в примерах: Учебное пособие. – М.: НИЯУ МИФИ, 2010. – 172 с.
7. Дупленко А. Г. Сравнительный анализ алгоритмов сортировки данных в массивах // Молодой ученый. — 2013. — № 8. — 80 с.
8. Кауфман В.Ш. Языки программирования. Концепции и принципы. – М.: ДЖК Пресс, 2011. – 464 с.
9. Красиков И.В. Алгоритмы. Просто как дважды два. – М.: Эксмо, 2013. – 256 с. ISBN 978-5-699-21047-3.
10. Кулаков В.Г., Алгоритмический язык Паскаль: Учебное пособие. – М.: МГИЭМ, 2014. – 41 с.
11. Лозовая С.Ю., Решение типовых задач по программированию: практическое пособие: НИУ БелГУ; НИУ БелГУ.-Белгород: ИПК НИУ "БелГУ", 2011. - 148 с.
12. Марапулец Ю.В., Программирование на языках высокого уровня: Учебное пособие. – КамчатГТУ, 2014. – 189 с. ISBN 978-5-328-00185-4.
13. Павловская Т.А. Паскаль. Программирование на языке высокого уровня: Учебник для вузов. – СПб.: Питер, 2012. – 393с.
14. Павловская Т.А., Паскаль. Программирование на языке высокого уровня: Учебник для вузов. – СПб.: Питер, 2015. – 464с.
15. Попов И.И., Основы алгоритмизации и программирования: Учебное пособие. – 3-е издание – М.: Форум, 2014. – 432 с.
16. Потопахин В.В. Искусство алгоритмизации: Учебное пособие. – М.: ДЖК Пресс, 2011. – 320 с., ил., ISBN 978-5-94074-621-8.
17. Потопахин В.В., Искусство алгоритмизации: Учебное пособие. – М.: ДЖК Пресс, 2011. – 320 с., ил., ISBN 978-5-94074-621-8.
18. Потопахин В.В., Современное программирование с нуля. – М.: ДЖК Пресс, 2010. – 240 с., ил.
19. Решение 50 типовых задач по программированию на языке Pascal – 2012 [Электронный ресурс] – URL: http://el-prog.narod2.ru/ (дата обращения: 17.10.2016).
20. Сулейманов Р.Р., Методика решения учебных задач средствами программирования: Методическое пособие – М: БИНОМ. Лаборатория знаний 2010, с. 112, ISBN:978-5-9963-0112-6.
21. Язык Pascal. Программирование для начинающих. – 2011 [Электронный ресурс] - URL: http://pas1.ru/pascaltextbook (дата обращения: 15.10.2016).