Введение
Необходимость отсортировать какие-либо величины возникает в программировании довольно часто. К примеру, входные данные подаются «вперемешку», а программе удобнее обрабатывать упорядоченную последовательность. Существуют ситуации, когда предварительная сортировка данных позволяет сократить содержательную часть алгоритма в разы, а время его работы – в десятки раз.
Сколь бы хорошими и эффективными не был выбранный вами алгоритм, но если в качестве подзадачи он использует «плохую» сортировку, то вся работа по его оптимизации оказывается бесполезной. Неудачно реализованная сортировка входных данных способна заметно понизить эффективность алгоритма в целом.
Данная курсовая работа посвящена рассмотрению одного из важных методов сортировки данных – сортировке методом слияний. Сортировка методом слияний является одним из наиболее известных алгоритмов внешних сортировок – сортировок, требующих для работы внешней памяти компьютера.
Данные, хранящиеся на внешних устройствах, имеют больший объём, что не позволяет их целиком переместить в оперативную память, отсортировать с использованием одного из алгоритмов внутренней сортировки, а затем вернуть их во внешнее устройство.
Цель данной курсовой работы: рассмотрение алгоритмов сортировок методом слиянием.
В ходе этой курсовой работы рассмотрены следующие вопросы:
– понятие сортировки и алгоритма сортировки;
– критерии оценивания алгоритмов сортировок;
– классификация алгоритмов сортировок;
– рассмотрение и анализ основных понятий сортировок слияниями;
– описание общей схемы слияний;
– описание методов простого и естественного слияний;
– описание программ, реализующих алгоритмы сортировки простым слиянием и естественным слиянием.
Для демонстрации данных алгоритмов выбран С – высокоуровневый и современный язык программирования, предназначенный для решения широкого класса задач. Эти алгоритмы рассмотрены в среде программирования Microsoft Visual Studio 2021.
Двухпутевое слияние
Алгоритм двухпутевого слияния заключается в следующем. Начальная последовательность делится на пару последовательностей:
Рисунок 2. Последовательность. Автор24 — интернет-биржа студенческих работ
Рисунок 3. Последовательность. Автор24 — интернет-биржа студенческих работ
Полученные последовательности затем проходят процесс объединения в единую последовательность, которая содержит упорядоченные пары:
Рисунок 4. Последовательность. Автор24 — интернет-биржа студенческих работ
Эту операцию следует выполнять до момента, пока сформированная последовательность не станет по размерам равна сортируемой.
Естественное неймановское слияние
На неймановский алгоритм повлияли конструктивные особенности компьютеров 40-х годов. Выглядело это так:
- Всего используется три магнитные ленты — основная, на которой записаны неотсортированные данные и две вспомогательные.
- Данные последовательно считываются с основной ленты.
- Пока последовательно считываемые данные представляют из себя упорядоченный подмассив, они переписываются на одну из вспомогательных лент.
- Как только завершается очередной отсортированный подмассив (т.е. на основной ленте встречается элемент, меньший чем предыдущий), на вспомогательной ленте ставится указатель (конец подмассива) и происходит переключение на другую вспомогательную ленту.
- Пункты 2-4 повторяются снова, только данные переносятся уже на другую вспомогательную ленту. При завершении очередного упорядоченного подмассива на основной ленте происходит поочерёдное переключение то на одну вспомогательную ленту, то на другую.
- Когда все данные с основной ленты считаны, происходит обработка вспомогательных лент.
- С обеих вспомогательных лент поочерёдно считываются данные.
- При этом очередные данные с двух лент сравниваются между собой. По результатами сравнения на основную ленту записывается меньший элемент из пары.
- Так как границы массивов на вспомогательных лентах отмечены указателями, считывание и сравнение происходит только в пределах отсортированных подмассивов.
- Если на одной из вспомогательных лент закончились элементы очередного подмассива, то с оставшейся ленты остаток подмассива просто переносится на основную ленту.
- Повторяем весь процесс заново до тех пор, пока данные на основной ленте не будут собой представлять полностью упорядоченный массив.
Неймановская сортировка является адаптивным алгоритмом: она не просто фиксирует отсортированные куски массива, но и в первую очередь старается увеличить их, чтобы затем на основе удлинённых упорядоченных подмассивов формировать ещё более длинные упорядоченные подмассивы. Поэтому её ещё называют
адаптивной сортировкой слиянием
Сложность данного алгоритма скромна — O(n2), и, тем не менее, для пионеров ламповых вычислений это был прорыв.
На примере этой первой сортировки слиянием уже виден недостаток этого класса алгоритмов — расходы на дополнительную память. В этом плане почти все сортировки слиянием дополнительно требуют O(n), однако изредка встречаются элегантные исключения.
Прямое слияние боуза-нельсона
Строго говоря, алгоритм Боуза-Нельсона — это сортировочная сеть, а не сортировка. В процессе массив и все его подмассивы делятся пополам и ничто не препятствует тому, чтобы все эти половинки на всех этапах обрабатывались параллельно. Однако можно представить и в виде именно сортировки. А до темы сортировочных сетей мы когда-нибудь доберёмся тоже.
- Массив делится пополам — на левую и правую половины.
- Элементы разбиваются на группы.
- На первой итерации это двойки элементов (1-й элемент левой половины 1-й элемент правой половины, 2-й элемент левой половины 2-й элемент правой половины и т.д.), на второй итерации — четвёрки элементов (1-й и 2-й элементы левой половины 1-й и 2-й элементы правой половины, 3-й и 4-й элементы левой половины 3-й и 4-й элементы правой половины и т.д.), на третьей — восьмёрки и т.д.
- Элементы каждой группы из левой половины являются отсортированным подмассивом, элементы каждой группы из правой половины также являются отсортированным подмассивом.
- Производим слияние отсортированных подмассивов из предыдущего пункта.
- Возвращаемся в пункт 1. Цикл продолжается до тех пор, пока размеры групп меньше размера массива.
Может показаться, что и тут требуется дополнительная память. Но нет! Для более понятного восприятия в анимации левая и правая половины массива расположены друг на другом, чтобы очевиднее было взаимное расположение сравниваемых подмассивов. Однако ввиду строгого деления пополам возможен алгоритм, при котором все сравнения и обмены делаются на месте, без привлечения дополнительных ресурсов по памяти. Что весьма нестандартно для сортировки слиянием.
def bose_nelson(data):
m = 1
while m < len(data):
j = 0
while j m < len(data):
bose_nelson_merge(j, m, m)
j = j m m
m = m m
return data
def bose_nelson_merge(j, r, m):
if j r < len(data):
if m == 1:
if data[j] > data[j r]:
data[j], data[j r] = data[j r], data[j]
else:
m = m // 2
bose_nelson_merge(j, r, m)
if j r m < len(data):
bose_nelson_merge(j m, r, m)
bose_nelson_merge(j m, r - m, m)
return data
Таки есть во всех сортировках слиянием нечто, что роднит их с водородной бомбой. Сначала происходит деление, потом синтез.
Сортировка естественным слиянием
В случае прямого слияния мы не получаем никакого преимущества, если данные уже являются частично упорядоченными. Размер сливаемых при каждом проходе последовательностей не зависит от существования более длинных уже упорядоченных последовательностей, которые можно было бы просто объединить.
Сортировка, при которой всегда сливаются две самые длинные из возможных последовательностей, называется сортировкой естественным слиянием.
Максимальную упорядоченную последовательность будем называть серией.
Пусть имеется начальный файл А. Каждый проход состоит из фазы распределения серий из файла А поровну в файлы В и С и фазы слияния, объединяющей серии из файлов В и С в файл А.
Если просмотр одного файла заканчивается раньше, чем просмотр другого (по причине разного числа серий), то остаток непустого файла целиком копируется в конец файла Л. Процесс завершается, когда в файле А остается только одна серия.
Запишем алгоритм сортировки естественным слиянием.
- 1. Прочитать начальные элементы каждого файла. Если один из файлов пустой, перейти к пункту 5.
- 2. Сравнить два элемента и записать минимальный в выходной файл, а на его место прочитать следующий элемент.
- 3. Если конец серии не достигнут, перейти к пункту 2.
- 4. Если достигнут конец серии, переписать элементы другого файла до окончания серии и перейти к пункту 1.
- 5. Если в другом файле имеются серии (хотя бы одна) переписать элементы этих серий в выходной файл. Закончить выполнение алгоритма.
В отличие от предыдущего алгоритма в рассматриваемом алгоритме необходимо обнаруживать конец серии. Это можно сделать следующим образом. Ключ прочитанной записи сравнивается с ключом следующей записи. Если значение ключа следующей записи меньше, то серия закончена.
Рассмотрим сортировку естественным слиянием на примере (рис. 84). Пусть задан файл А:
Рис. 84. Двухфазная сортировка естественным слиянием
На основе рассмотренного выше алгоритма легко получить алгоритм однофазной сортировки естественным слиянием с четырьмя файлами.
Очевидно, что число чтений/перезаписей файлов при использовании этого метода будет не хуже, чем при применении метода простого слияния, а в среднем даже лучше. С другой стороны, увеличивается число сравнений за счет тех, которые требуются для распознавания концов серий. Кроме того, поскольку длина серий может быть произвольной, то максимальный размер файлов В и С может быть близок к размеру файла А.
Необходимо заметить, что хотя и предполагается, что серии поровну распределяются в оба файла, действительное количество выходных серий в файлах В и С могут различаться больше чем на 1. Например, рассмотрим исходный файл А из шести серий (рис. 85).
Рис. 85. Неравномерное распределение серий
Этот пример показывает, что простое распределение серий по нескольким файлам может дать в результате меньшее число выходных серий, чем входных. Это происходит потому, что первый элемент (7 /)-й серии может быть больше, чем последний элемент (г-7)-й серии, что приведёт к автоматическому слиянию двух серий в одну, что и наблюдается в примере при распределении серий в файл В. Это следует учитывать при последующем слиянии серий, а именно, после достижения конца одного из файлов копировать весь остаток другого файла, а не только одну серию.
Рассмотренные выше алгоритмы сортировки основаны на слиянии. Рассмотрим процесс слияния в общем виде. Пусть имеются два отсортированных в порядке возрастания массива р}, р2, …, р„ и qi, q2, …, q„ и имеется пустой массив г/, г2, Г2п, который мы хотим заполнить значениями массивов р и q в
порядке возрастания.
Для слияния выполняются следующие действия: сравниваются pi и qi, и меньшее из значений записывается в г/. Предположим, что это значение pi. Тогда р2 сравнивается с qi и меньшее из значений заносится в г?. Предположим, что это значение q. Тогда на следующем шаге сравниваются значения /ъ и г/2 и т.д., пока мы не достигнем границ одного из массивов. Тогда остаток другого массива просто дописывается в «хвост» массива г.
Обобщая эту схему, можно получить /г-путевое слияние для упорядоченных последовательностей, размещённых в Р-файлах.
В основе метода внешней сортировки сбалансированным многопутевым слиянием лежит распределение серий исходного файла по т вспомогательным файлам В], В2,Вт и их слияние в т вспомогательных файлов Cj, С2,…, Ст. На следующем шаге производится слияние файлов Сь С2, …, Ст в файлы ВI, В2, Вт и т.д., пока в Bi или С/ не образуется одна серия. Рассмотрим алгоритм Р-путевого слияния
- 1. Установить г: =Р.
- 2. Если г>1, то перейти к следующему пункту, иначе к пункту 5.
- 3. Прочитать начальные элементы оставшихся г непустых последовательностей, записать минимальный элемент в выходной файл, а на его место прочитать следующий элемент из соответствующего файла.
- 4. Если последовательность, из которой читался элемент, станет пустой, уменьшить г на 1. Перейти к пункту 2.
- 5. Переписать оставшиеся элементы непустой последовательности в выходной файл. Закончить выполнение алгоритма.
Многопутевое слияние является естественным развитием идеи обычного (двухпутевого) слияния.
Статьи серии:
Обе упомянутые в сегодняшней статье сортировки теперь доступны в приложении AlgoLab (кто изучает алгоритмы с помощью этого Excel-приложения — обновите файл). А всего через пару дней, с выходом скорого продолжения о сортировках слияния, будут доступны ещё несколько алгоритмов этого класса.
Для сортировки Боуза-Нельсона поставлено ограничение — размер массива должен быть степенью двойки. Если это условие не будет выполнено, то макрос обрежет массив до подходящего размера.
Статья написана при поддержке компании EDISON Software, которая пишет софт 3d-реконструкции и занимается разработкой сложного измерительного оборудования.
