Главная » Java, Структуры данных и алгоритмы » Сортировка слиянием

0

Читатель уже убедился, насколько удобно при описании алгоритмов пользоваться возможностями рекурсии (например, методики проходов дерева, представленные в главе 6). В этом разделе представляется методика сортировки под названием сортировка методом слияния, которая легко описывается с помощью рекурсии. Этот алгоритм тоже создан на основе проектной алгоритмической модели, названной «разделяй и властвуй», одновременно удобной и универсальной.

 «Разделяй и властвуй»

выполнена на базе проектной алгоритмической модели «разделяй и властвуй». Эта парадигма может быть описана стандартной терминологией в виде трех стадий процесса:

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

2)                      рекурсия — рекурсивно разрешаются проблемы для уже полученных составляющих;

3)                       слияние -»- полученные результаты действий над составляющими вводимого данного «сливаются» в единый результат.

Алгоритм сортировки методом слияния использует подход «разделяй и властвуй» для решения задач сортировки.

Использование механизма «разделяй и властвуй» для сортировки

Напомним, что при сортировке имеется набор п объектов, обычно расположенных в списке, векторе, массиве или последовательности вместе с компаратором, определяющим их общий порядок. Задача состоит в создании упорядоченного представления этих объектов. Для универсальности будем считать, что в качестве исходных данных имеется последовательность объектов S, и возвращается эта последовательность в сортированном порядке. Разновидности других линейных структур типа списка, вектора или массива достаточно просты, поэтому они оставлены для рассмотрения в упражнениях (М-10.3 и М-10.12). Для решения поставленной задачи с последовательностью из п объектов требуются три стадии:

1)                       разделение — если в S отсутствуют элементы или имеется только один элемент, S немедленно возвращается — она уже упорядочена. Если же S содержит как минимум два элемента, все элементы из S распределяем в две последовательности S\ и S2, каждая из которых будет хранить половину элементов S. То есть S\ содержит первую [п/2] половину элементов S, а 5*2 — оставшуюся 1п/2] половину элементов

2)                       рекурсия — рекурсивно сортируем последовательности S\ и Sk;

3)                       слияние — объединяем сортированные последовательности S\ и S2 в одну сортированную последовательность S.

Напомним, что понятие [~x~| означает наименьшее значение х, то есть наименьшее целое число т, такое, что х < т. Понятие |_xj означает наибольшее целое число к, такое, что к < х.

16 Зак 2456

Алгоритм ввода слиянием можно визуально представить с помощью бинарного дерева Г, называемого деревом сортировки методом слияния (merge-sort tree). При этом каждый узел отображает рекурсивный вызов алгоритма сортировки слиянием и этому узлу соответствует последовательность S, обрабатывается вызовом указанного алгоритма в узле. Дочерние элементы узла v соответствуют рекурсивным вызовам, обрабатывающим части последовательности S в виде S\ и S2. Простые узлы дерева Т представляют отдельные элементы последовательности S, соответствующие экземплярам алгоритма, где рекурсивные вызовы не выполняются.

На рис. 10.1 приводится порядок работы алгоритма сортировки методом слиянием в сортировочном дереве. Пошаговое изменение дерева показано на рис. 10.2-10.5.

Визуальное представление позволяет проанализировать время выполнения алгоритма сортировки. В. частности, поскольку размер последова-

(а)

 

(Ь)

Рис. 10.1. Дерево сортировки методом слияния Тдля выполнения алгоритма сортировки методом слияния в последовательности из 8 элементов: (а) обработка входной последовательности в каждом узле дерева Т\ (Ь) выходная последовательность, генерируемая в каждом узле дерева Т

цельности при каждом рекурсивном вызове уменьшается ориентировочно вдвое, высота сортировочного дерева составит приблизительно log п (напомним, что основание логарифма применяется равным 2, если другое не оговаривается специально).

Рис. 10.2. Визуальное отображение сортировки методом слияния. Каждый узел дерева отображает рекурсивный вызов сортировки. Узлы, отмеченные пунктиром, означают вызовы, которые пока не осуществлены. Узлы, показанные жирной чертой, указывают текущие вызовы. Пустые узлы, обозначаемые тонкой линией, — выполненные вызовы. Оставшиеся узлы (помеченные тонкой линией, но не пустые) представляют вызовы, ожидающие возврата результатов обработки дочерних элементов

Рис. /0.J (продолжение рис. 10.2). Визуальное отображение сортировки методом слияния. Стадия «Властвуй» приведена в пункте (h)

Утверждение 10.1. Высота дерева при выполнении сортировки слиянием последовательности размером п составляет ["log п |.

Данное утверждение докажем в упражнении М-10.1, а сейчас просто применим его для анализа алгоритма сортировки методом слияния.

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

Рис: 10.4 (продолжение рис. lt).3). Визуальное представление выполнения сортировки методом слияния. Стадия «Властвуй» привбдена в пунктах (о) и (q)

деления и рекурсии достаточно просты. Разделение последовательности размером п представляет собой разбиение ее на две части, в первой из которых будут находиться элементы до индекса [п/2\ а во второй — все остальные. Рекурсивные обращения будут просто передавать эти меньшие последовательности как параметры. Более сложным является стадия слияния двух отсортированных последовательностей в одну. Поэтому до проведения анализа подробно объясним, как это происходит.-

Рис. /0.5 (продолжение рис. 10.4). Визуальное отображение сортировки методом слияния. Несколько вызовов между (s) и (t) пропущено. Стадия «Властвуй» приведена в пунктах (t) и (v)

Слияние двух сортированных последовательностей

Алгоритм merge, показанный во фрагменте кода 10.1, объединяет две последовательности S\ и 52, итеративнс) удаляя наименьший элемент > из одной из них и добавляя его в конец получаемой последовательности S до тех пор, пока одна из них не опустеет. С этого момента оставшиеся элементы второй последовательности копируются в результативную последовательность S.

Время выполнения алгоритма merge анализируется следующим образом. Допустим, п\ и ni — количество элементов в S\ и Si соответственно. Допустим также, что последовательности S\, S2 и S реализованы так, что доступ к первой и последней позиции, ввод и удаление из них занимает 0(1) времени. Это соответствует реализациям, основанным на кольцевых массивах или двусвязных списках (раздел 5.3). Алгоритм merge имеет три промежуточных цикла (while loop). Исходя из сделанных допущений, операции внутри каждого из них занимают 0(1) времени. Ключевым моментом анализа является то, что в процессе каждой итерации цикла из S\ или S2 удаляется один элемент. Поскольку ввод не осуществляется,

предполагается, что общее количество итераций трех циклов составит п\ + «2. Таким образом, время выполнения алгоритма merge составит 0(п\ + «2), из чего следует утверждение 10.2.

Утверждение 10.2. Слияние двух сортированных последовательностей S\ и 5*2 занимает 0(п\ + щ) времени, где п\ — размер Si, а П2 — размер S2.

Алгоритм merge(5i, S2, S):

Input: последовательности S\ и 5*2, отсортированные в неубывающем порядке, и пустая последовательность S.

Output: последовательность S, содержащая элементы из S\ и 5*2, ставших в результате пустыми.

while Si не пуста and S2 не пуста do

if S^firstO-elementO < S2.fjrst().element() then {переместить первый элемент Si в конец S]

S.insertLast(S1 .remove(S1 .first())) else

{переместить первый элемент S2 в конец S]

S.insertLast(S2.remove(S2.first())) {переместить первый элемент Si в конец S} while не пуста do

S.insertLast(S2.remove(S1.first())) {переместить первый элемент S2 в конец S} while S2 не пуста do

S.insertLast(S2.remove(S2.first

Фрагмент кода 10.1. Алгоритм merge для слияния двух сортированных последовательностей

Пример выполнения алгоритма merge приведен на рис. 10.6.

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

Проведя анализ наиболее важного компонента сортировки — алгоритма merge, приступим к анализу врембни выполнения всего алгоритма сортировки слиянием. Допустим, исходная последовательность имеет п элементов. Для простоты ограничимся случаем, когда п является степенью 2. Доказательство верности результата анализа при любом п оставлено для упражнения М-10.4.

Аналогично вышеприведенному анализу допустим, что последовательность S и вспомогательные последовательности S\, S2, полученные при рекурсивных вызовах сортировки, реализованы так, что доступ к первой и последней позиции, ввод и удаление из них занимает 0(1) времени. Это возможно при реализации на основе кольцевого массива и двусвязного списка (раздел 5.3) или непосредственного использования любой из этих структур данных.                                                                                              1

Рис. 10.6: Выполнение алгоритма merge из фрагмента кода 10.1

Как было отмечено ранее, проводим анализ алгоритма сортировки на основе дерева сортировки методом слияния Т (рис. 10.2—10.5). Необходимое для прохождения каждого узла v дерева Т время будет называться временем выполнения рекурсивного вызова, ассоциируемого с v, исключая время ожидания окончания рекурсивных вызовов дочерних элементов узла v. Другими словами, время, требуемое на один узел v, включает в себя время выполнения стадий деления и слияния, но не учитывает времени выполнения рекурсии. Выше отмечалось, что процедура деления достаточно проста и выполняется за время, пропорциональное размеру последовательности из v. Кроме того, из утверждения 10.2 следует, что стадия слияния, состоящая из объединения двух сортированных последовательностей, также выполняется за линейное время. Это означает, что время, затрачиваемое на узел v, составляет 0(п/20, где i обозначает глубину узла v, так как размер последовательности, обрабатываемый рекурсивным вызовом, ассоциируемым с v, равен я/2′.

Рассматривая более обший случай дерева, как показано на рис. 10.7, можно заметить, что из определения «времени, затрачиваемого на один узел» следует, что общее время выполнения алгоритма сортировки слиянием равно общему времени, затраченному на все узлы дерева Т. Заметьте, что Г имеет ровно 2′ узлов на глубине /. Из этого замечания вытекает, что общее время, затраченное на все узлы дерева Т на глубине /, составляет 0(2′ • п/20, что есть 0(п). Согласно утверждению 10.1, высота дерева Тсоставляет Hog п\. Таким образом, поскольку время, затраченное на каждый уровень [log п \ + 1 дерева Т, равно 0(п), получим следующий результат.

Утверждение 10.3. Алгоритм сортировки методом слияния сортирует последовательность размером п элементов в худшем случае за 0(п log п) времени.

Другими словами, алгоритм сортировки слиянием асимптотически стремится к быстрому выполнению алгоритма пирамидальной сортировки.

Рис. 10.7. Время выполнения дерева сортировки Т В узлах приведены значения размера

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии