Файл: Анализ алгоритмов сортировок методом слияния.pdf

Введение

Необходимость отсортировать какие-либо величины возникает в программировании довольно часто. К примеру, входные данные подаются «вперемешку», а программе удобнее обрабатывать упорядоченную последовательность. Существуют ситуации, когда предварительная сортировка данных позволяет сократить содержательную часть алгоритма в разы, а время его работы – в десятки раз.

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

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

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

Цель данной курсовой работы: рассмотрение алгоритмов сортировок методом слиянием.

В ходе этой курсовой работы рассмотрены следующие вопросы:

• Понятие сортировки и алгоритма сортировки;
• Критерии оценивания алгоритмов сортировок;
• Классификация алгоритмов сортировок;
• Рассмотрение и анализ основных понятий сортировок слияниями;
• Описание общей схемы слияний;
• Описание методов простого и естественного слияний;
• Описание программ, реализующих алгоритмы сортировки простым слиянием и естественным слиянием.

Для демонстрации данных алгоритмов выбран С++ – высокоуровневый и современный язык программирования, предназначенный для решения широкого класса задач. Эти алгоритмы рассмотрены в среде программирования Microsoft Visual Studio 2010.

1. Алгоритм сортировки слиянием

Алгоритм сортировки слияниями был изобретён венгеро-американским математиком Джоном фон Нейманом в 1945 году. Он является одним из самых быстрых способов сортировки.

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

Несколько детально этот процесс можно расписать так:

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

Слияние – это объединение двух или более упорядоченных массивов в один упорядоченный.

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

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

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

Введём понятие упорядоченного отрезка или серии – это последовательность элементов, для которых не нарушается условие упорядоченности. Количество элементов данной последовательности называется длиной серии. Серия, состоящая из одного элемента, упорядочена всегда. Если длина серии фиксирована, то слияние называется простым. При естественном слиянии всегда сливаются две наиболее длинных серии.

Фаза – это последовательность действий, необходимых для однократной обработки всех элементов.

Проход – это наименьший процесс, реализация которого составляет алгоритм сортировки.

Двухфазная сортировка – это сортировка, в которой отдельно реализуется две фазы: распределение и слияние. Однофазная сортировка – это сортировка, в которой объединены фазы распределения и слияния в одну.

Исходные данные разбиваются на серии, или упорядоченные отрезки, и распределяются на два и более вспомогательных массива. Это распределение идет поочередно: первая серия записывается в первый вспомогательный массив, вторая – во второй и т.д. После того, как произошла запись серии в последний вспомогательный массив, следующая по счёту серия записывается опять в первый вспомогательный массив. После распределения всех серий они объединяются в более длинные упорядоченные отрезки: из каждого вспомогательного массива берется по одной серии, и серии сливаются. Если в каком-то массиве серия заканчиваются, то следующая серия пока не рассматривается. Сформированный более длинный упорядоченный отрезок записывается либо в исходный массив, либо в какой-то из вспомогательных. Далее происходит распределение этих длинных серий во вспомогательные массивы с последующим их слиянием. До тех пор пока все данные не будут упорядочены.

В сортировке слияниями выделяют две основные характеристики:

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

Алгоритм сортировки слияниями

Шаг 1. Разбить имеющиеся элементы массива на пары и осуществить слияние элементов каждой пары, получив отсортированные цепочки длины 2 (кроме, быть может, одного элемента, для которого не нашлось пары).

Шаг 2. Разбить имеющиеся отсортированные цепочки на пары, и осуществить слияние цепочек каждой пары.

Шаг 3. Если число отсортированных цепочек больше единицы, перейти к шагу 2.

Демонстрация сортировки слиянием по возрастанию представлена на рисунке 1.

Рис.1. Демонстрация сортировки слиянием по возрастанию

Прежде чем описывать алгоритм сортировки слиянием введем несколько определений.

Основным понятием при использовании внешней сортировки является понятие серии. Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу.

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

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

Фаза – это действия по однократной обработке всей последовательности элементов.Двухфазная сортировка – это сортировка, в которой отдельно реализуется две фазы: распределение и слияние.Однофазная сортировка – это сортировка, в которой объединены фазы распределения и слияния в одну.

Двухпутевым слиянием называется сортировка, в которой данные распределяются на два вспомогательных файла.Многопутевым слиянием называется сортировка, в которой данные распределяются на N (N > 2) вспомогательных файлов.

1.1 Постановка задачи сортировки

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

Алгоритм сортировки – это алгоритм для упорядочивания некоторого множества элементов. Чаще всего упорядочивание происходит по возрастанию или по убыванию. Алгоритмы сортировки находят широкое применение в различных областях программирования: начиная от работы с огромными объёмами баз данных, заканчивая составлением программ для решения математических задач.

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

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

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

Оценка алгоритмов проводится по следующим параметрам:

• Время сортировки – быстродействие алгоритма.
• Память – характеристика для временного хранения данных во время выполнения алгоритма.
• Устойчивость – неизменность взаимного расположения элементов с равными значениями.
• Естественность поведения – параметр, указывающий эффективен ли алгоритм при сортировке уже отсортированного или частично отсортированного множества данных. Если эта информация будет учтена при работе алгоритма, то он будет менее затратным и более эффективным.

Выделяют алгоритмы внутренней и внешней сортировок. В первом случае для временного хранения данных используется лишь оперативная память компьютера. Во втором случае алгоритм сортировки использует внешнюю память компьютера (как правило, жёсткие диски). Внешняя сортировка разработана для обработки больших списков данных, которые не помещаются в оперативную память. Нелишним будет отметить, что алгоритмы внутренней сортировки значительно эффективнее алгоритмов внешней : на обращение к внутренней памяти компьютера затрачивается намного меньше времени, чем к внешней. Если в какой-либо задаче имеется возможность записать данные из внешней памяти в оперативную, то лучше воспользоваться этой возможностью, и перейти от внешних сортировок к внутренним.

1.2 Алгоритм сортировки простым слиянием

Одна из сортировок на основе слияния называется простым слиянием.

Алгоритм сортировки простым слияния является простейшим алгоритмом внешней сортировки, основанный на процедуре слияния серией.

В данном алгоритме длина серий фиксируется на каждом шаге. В исходном файле все серии имеют длину 1, после первого шага она равна 2, после второго – 4, после третьего – 8, после k -гошага – 2k.

Алгоритм сортировки простым слиянием

Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2.

Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом одиночные элементы образуют упорядоченные пары.

Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.

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

После выполнения i проходов получаем два файла, состоящих из серий длины 2i. Окончание процесса происходит при выполнении условия 2i>=n. Следовательно, процесс сортировки простым слиянием требует порядка O(log n) проходов по данным.

Признаками конца сортировки простым слиянием являются следующие условия:

• Длина серии не меньше количества элементов в файле (определяется после фазы слияния);
• Количество серий равно 1 (определяется на фазе слияния).
• При однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.