Глава 2. Реализация алгоритма сортировки массива методом слияния.
Алгоритм сортировки слиянием был предложен праотцом современных компьютеров – Джоном фон Нейманом. Сам метод является устойчивым, т. е. он не меняет одинаковые по значению элементы в списке. Как уже было сказано, сортировка массива методом слияния – В основе сортировки слиянием лежит принцип «разделяй и властвуй». Список разделяется на равные или практически равные части, каждая из которых сортируется отдельно. После чего уже упорядоченные части сливаются воедино. Несколько детально этот процесс можно расписать так:
массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице;
далее выполняется операция алгоритма, называемая слиянием. Два единичных массива сливаются в общий результирующий массив, при этом из каждого выбирается меньший элемент (сортировка по возрастанию) и записывается в свободную левую ячейку результирующего массива. После чего из двух результирующих массивов собирается третий общий отсортированный массив, и так далее. В случае если один из массивов закончиться, элементы другого дописываются в собираемый массив;
3.в конце операции слияния, элементы перезаписываются из результирующего массива в исходный.
Пример сортировки слиянием.
Сначала делим список на кусочки (по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем и объединяем. В итоге, все элементы отсортированы и объединены вместе.
Для решения задачи сортировки эти три этапа выглядят так:
1.Сортируемый массив разбивается на две части примерно одинакового размера;
2.Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
3.Два упорядоченных массива половинного размера соединяются в один.
Пример работы алгоритма на массиве 3, 7, 8, 2, 4, 6, 15:
Слияние имеет большое практическое применение. Например ,у Вас есть 2 списка
a[l+step]=tmp[step];2
номеров телефонов , отсортированных по возрастанию и их нужно объединить в один список, тоже отсортированный по возрастанию. Перейдем непосредственно к самому алгоритму. Представим , что мы имеем 2 массива M,N , содержащие упорядоченные элементы. Нужно выполнить слияние этих массивов с массивов P. Для этого : вначале сравнивается элемент M[1] с элементом N[1] и меньший из низ записывается в P[1] . Если M[1] меньше N[1] , то при выполнении следующего шага сравниваться уже будут M[2] и N[1], если наоборот - сравнивать будем M[1] и N[2]. И так до тех пор, пока один из начальных массивов не опустошится. Тогда оставшиеся элементы в другом массиве дописываются в массив P.
Попробуем алгоритм в действии. Пусть массив M содержит 3,5,8,11,16, а массив N содержит 1,5,7,9,12,13,18,20 . Смотрим на схему:
Этот алгоритм работает обычно медленней, чем быстрая сортировка, однако у него есть ряд преимуществ: во первых он показывает стабильные результаты при сортировке определённого количества данных, в то время как при быстрой сортировке эти результаты могут довольно сильно различаться. Во-вторых, при большом количестве повторяющихся элементов программа не уходит в глубокую рекурсию. Главный недостаток – использование дополнительной памяти.
3
Существует несколько вариантов сортировки слиянием:
1. Двухпутевое слияние
Имея два упорядоченных входных файла, их можно объединить в один упорядоченный выходной файл просто отслеживая наименьший элемент в каждом файле и входя в цикл, в котором меньший из двух элементов, наименьших в своих файлах, переносится в выходной файл: процесс продолжается до тех пор, пока оба входных файла не будут исчерпаны. Время выполнения линейно зависит от количества элементов в выходном файле, если на каждую операцию поиска следующего наименьшего элемента в файле уходит одно и тоже время, что как раз и имеет место в том случае, когда отсортированные файлы представлены структурой данных, которая поддерживает последовательный доступ с постоянным временем доступа, такой как связный список или массив. Эта процедура представляет собой двухпутевое слияние (two – way merging). Наиболее важным приложением многопутевого слияния является внешняя сортировка.
2. Нисходящая сортировка слиянием
Нисходящая сортировка слиянием аналогична принципу управления сверху вниз, в рамках которого руководитель организует работы таким образом, что получив большую задачу, он разбивает ее на подзадачи, которые должны независимо решать его подчиненные. Однако руководство выполняет значительную часть работы, соединяя результаты работы подчиненных в единое целое.
Сортировка слиянием играет важную роль благодаря простоте и оптимальности заложенного в нее метода, который допускает возможность реализации, обладающей устойчивостью.
3. Восходящая сортировка слиянием
У каждой рекурсивной программы имеется нерекурсивный аналог, который хотя и выполняет эквивалентные вычисления, тем не менее, он делает это по другому.
Порядок выполнения слияний определяется рекурсивной структурой алгоритма. Однако подфайлы обрабатываются независимо и слияния могут выполнятся в различных.
Кратко подводя итоги, отметим, что нисходящие и восходящие сортировки суть два достаточно простых алгоритма, в основу которых положена операция слияния двух упорядоченных подфайлов в результирующий объединенный упорядоченный файл. Оба алгоритма тесно связаны между собой и даже выполняют одно и то же множество слияний, если размер исходно файла является степенью 2, но они отнюдь не идентичны.
