Слияние и сортировка слиянием. Сортировка слиянием по-простому
Подробности Категория: Сортировка и поискСортировка слиянием (англ. merge sort ) - алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например - потоки) в определённом порядке. Эта сортировка - хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
- массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице;
- далее выполняется операция алгоритма, называемая слиянием. Два единичных массива сливаются в общий результирующий массив, при этом из каждого выбирается меньший элемент (сортировка по возрастанию) и записывается в свободную левую ячейку результирующего массива. После чего из двух результирующих массивов собирается третий общий отсортированный массив, и так далее. В случае если один из массивов закончиться, элементы другого дописываются в собираемый массив;
- в конце операции слияния, элементы перезаписываются из результирующего массива в исходный.
Реализация алгоритма на различных языках программирования:
C++
/** * @brief Сортировка элементов от l до r массива buf * @param buf - сортируемый массив * @param l - левая граница. При первой итерации l = 0 * @param r - правая граница. При первой итерации r = buf.size() - 1 * * В результате сортируются все элементы массива buf от l до r включительно. */ templateСуществует также итеративный алгоритм сортировки, избавленный от рекурсивных вызовов. Такой алгоритм называют «Восходящей сортировкой слиянием».
// Слияние двух упорядоченных массивов
// m1 - Первый массив
// m2 - Второй массив
// l1 - Длина первого массива
// l2 - Длина второго массива
// Возвращает объединённый массив
template
Пример: char a = "ASORTINGEXAMPLE"; mergeSort(a, 16); Альтернативная версия алгоритма Сортировки Слиянием.
Template
C#
Static Int32 Merge_Sort(Int32 massive)
{
if (massive.Length == 1)
return massive;
Int32 mid_point = massive.Length / 2;
return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray()));
}
static Int32 Merge(Int32 mass1, Int32 mass2)
{
Int32 a = 0, b = 0;
Int32 merged = new int;
for (Int32 i = 0; i < mass1.Length + mass2.Length; i++)
{
if (b < mass2.Length && a < mass1.Length)
if (mass1[a] > mass2[b])
merged[i] = mass2;
else //if int go for
merged[i] = mass1;
else
if (b < mass2.Length)
merged[i] = mass2;
else
merged[i] = mass1;
}
return merged;
}
static void Main(string args)
{
Int32 arr = new Int32;
//заполняем массив случайными числами
Random rd = new Random();
for(Int32 i = 0; i < arr.Length; ++i) {
arr[i] = rd.Next(1, 101);
}
System.Console.WriteLine("The array before sorting:");
foreach (Int32 x in arr)
{
System.Console.Write(x + " ");
}
//сортировка
arr = Merge_Sort(arr);
System.Console.WriteLine("\n\nThe array after sorting:");
foreach (Int32 x in arr)
{
System.Console.Write(x + " ");
}
System.Console.WriteLine("\n\nPress the
C#
//предыдущий пример сортирует лишь целые числа. Следующий - работает со всеми типами данных. static IComparable Merge_Sort(IComparable massive) { if (massive.Length == 1) return massive; int mid_point = massive.Length / 2; return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray())); } static IComparable Merge(IComparable mass1, IComparable mass2) { int a = 0, b = 0; IComparable merged = new IComparable; for (int i = 0; i < mass1.Length + mass2.Length; i++) { if (b.CompareTo(mass2.Length) < 0 && a.CompareTo(mass1.Length) < 0) if (mass1[a].CompareTo(mass2[b]) > 0) merged[i] = mass2; else merged[i] = mass1; else if (b < mass2.Length) merged[i] = mass2; else merged[i] += mass1; } return merged; } static void Main(string args) { IComparable arr = new IComparable; Random rd = new Random(); for (int i = 0; i < arr.Length; ++i) arr[i] = rd.Next(1, 101); Console.WriteLine("Массив перед сортировкой:"); foreach (int x in arr) System.Console.Write(x + " "); arr = Merge_Sort(arr); Console.WriteLine("\n\nМассив после сортировки:"); foreach (int x in arr) System.Console.Write(x + " "); Console.WriteLine("\n\nДля выхода нажмитеPerl
@out=(5,2,8,9,4,2,7,9,4,1,6,9,0); sub sortM{ my($array,$first,$last)=@_; if($last>$first){ my$middle=int(($last+$first)/2); sortM($array,$first,$middle); sortM($array,$middle+1,$last); my$j=0; $work[$j++]=$$array[$_]for($first..$last); $middle=int(($first+$last)/2)if($middle>$last); my$n=$middle-$first+1; for($i=$first,$j=0,$k=$n;$i<=$last;$i++){ if(($j<$n)&&(($k==(($last-$first)+1))||($work[$j]lt$work[$k]))){ $$array[$i]=$work[$j++] }else{ $$array[$i]=$work[$k++]; } } } } sortM(\@out,0,$#out+1);
Паскаль (сортировка текстовых файлов)
Сортировка простым слиянием
Procedure MergeSort(name: string; var f: text);
Var a1,a2,s,i,j,kol,tmp: integer;
f1,f2: text;
b: boolean;
Begin
kol:=0;
Assign(f,name);
Reset(f);
While not EOF(f) do
begin
read(f,a1);
inc(kol);
End;
Close(f);
Assign(f1,"{имя 1-го вспомогательного файла}");
Assign(f2,"{имя 2-го вспомогательного файла}");
s:=1;
While (s Procedure MergeSort(name: string; var f: text);
Var s1,s2,a1,a2,where,tmp: integer;
f1,f2: text;
Begin
s1:=5; s2:=5; {Можно задать любые числа, которые запустят цикл while}
Assign(f,name);
Assign(f1,"{имя 1-го вспомогательного файла}");
Assign(f2,"{имя 2-го вспомогательного файла}");
While (s1>1) and (s2>=1) do
begin
where:=1;
s1:=0; s2:=0;
Reset(f); Rewrite(f1); Rewrite(f2);
Read(f,a1);
Write(f1,a1," ");
While not EOF(f) do
begin
read(f,a2);
If (a2 Unit uMergeSort;
interface
type
TItem = Integer; //Здесь можно написать Ваш произвольный тип
TArray = array of TItem;
procedure MergeSort(var Arr: TArray);
implementation
function IsBigger(d1, d2: TItem) : Boolean;
begin
Result:= (d1 > d2); //Сравниваем d1 и d2. Не обязательно так. Зависит от Вашего типа.
//Сюда можно добавить счетчик сравнений
end;
//Процедура сортировки слияниями
procedure MergeSort(var Arr: TArray);
var
tmp: TArray; //Временный буфер
//Слияние
procedure merge(L, Spl, R: Integer);
var
i, j, k: Integer;
begin
i:= L;
j:= Spl + 1;
k:= 0;
//Выбираем меньший из первых и добавляем в tmp
while (i <= Spl) and (j <=R) do
begin
if IsBigger(Arr[i], Arr[j]) then
begin
tmp[k] := Arr[j];
Inc(j);
end
else
begin
tmp[k] := Arr[i];
Inc(i);
end;
Inc(k);
end;
//Просто дописываем в tmp оставшиеся эл-ты
if i <= Spl then //Если первая часть не пуста
for j:= i to Spl do
begin
tmp[k] := Arr[j];
Inc(k);
end
else //Если вторая часть не пуста
for i:= j to R do
begin
tmp[k] := Arr[i];
Inc(k);
end;
//Перемещаем из tmp в arr
Move(tmp, Arr[L], k*SizeOf(TItem));
end;
//Сортировка
procedure sort(L, R: Integer);
var
splitter: Integer;
begin
//Массив из 1-го эл-та упорядочен по определению
if L >= R then Exit;
splitter:= (L + R) div 2; //Делим массив пополам
sort(L, splitter); //Сортируем каждую
sort(splitter + 1, R); //часть по отдельности
merge(L, splitter, R); //Производим слияние
end;
//Основная часть процедуры сортировки
begin
SetLength(tmp, Length(Arr));
sort(0, Length(Arr) - 1);
SetLength(tmp, 0);
end;
end. Void mergeSort(int array) {
static void merge(int array, int q) {
int leftArray = array.dup ~ int.max;
int rightArray = array.dup ~ int.max;
int i = 0;
int j = 0;
int length = array.length;
for (int k = 0; k < length; ++k) {
array[k] = (leftArray[i] <= rightArray[j]) ? leftArray : rightArray;
}
}
if (array.length > 1) {
int q = array.length / 2;
mergeSort(array);
mergeSort(array);
merge(array, q);
}
} Def merge(right, left, result):
result.append((left if left < right else right).pop(0))
return merge(right=right, left=left, result=result) if left and right else result+left+right
merge_sort = (lambda arr: arr if len(arr) == 1 else merge(merge_sort(arr),
merge_sort(arr[:len(arr)/2]), )) Недостатком сортировки слиянием является использование дополнительной памяти. Но когда работать приходиться с файлами или списками, доступ к которым осуществляется только последовательно, то очень удобно применять именно этот метод. Также, к достоинствам алгоритма стоит отнести его устойчивость и неплохую скорость работы O(n*logn).
При написании статьи были использованы открытые источники сети интернет:
Было подсчитано, что до четверти времени централизованных компьютеров уделяется
сортировке данных. Это потому, что намного легче найти значение в массиве, который
был заранее отсортирован. В противном случае поиск немного походит на поиск иголки
в стоге сена. Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов
сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в
себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает,
что поисковые алгоритмы очень востребованы. Но есть одно "но". Поисковые алгоритмы работают намного быстрее с базами данных, которые
уже отсортированы. В этом случае требуется только линейный поиск. В то время как компьютеры находятся без пользователей в некоторые моменты времени,
алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи,
осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели
поиска. В этой статье приведены примеры реализации стандартных алгоритмов сортировки. Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации
найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент.
Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так
должно происходить, пока элементы, находящиеся на первых местах в массивe, не окажутся в
надлежащем порядке. Код C++
void
SortAlgo::selectionSort(int
data, int
lenD)
{
int
j = 0;
int
tmp = 0;
for
(int
i=0; i При пузырьковой сортировке сравниваются соседние элементы и меняются местами, если
следующий элемент меньше предыдущего. Требуется несколько проходов по данным. Во время
первого прохода сраваются первые два элемента в массиве. Если они не в порядке, они
меняются местами и затем сравнивается элементы в следующей паре. При том же условии они
так же меняются местами. Таким образом сортировка происходит в каждом цикле пока не будет
достигнут конец массива. Код C++
void
SortAlgo::bubbleSort(int
data, int
lenD)
{
int
tmp = 0;
for
(int
i = 0;i При сортировке вставками массив разбивается на две области: упорядоченную и
и неупорядоченную. Изначально весь массив является неупорядоченной областью.
При первом проходе первый элемент из неупорядоченной области изымается и помещается
в правильном положении в упорядоченной области. На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной
области сокращается на 1. Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в
правильное положение в упорядоченной области. Это сделано путем сдвига всех
элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i]
вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i]. Код C++
void
SortAlgo::insertionSort(int
data, int
lenD)
{
int
key = 0;
int
i = 0;
for
(int
j = 1;j Код C++
void
SortAlgo::mergeSort(int
data, int
lenD)
{
if
(lenD>1){
int
middle = lenD/2;
int
rem = lenD-middle;
int
* L = new int
;
int
* R = new int
;
for
(int
i=0;i Быстрая сортировка использует алгоритм "разделяй и властвуй". Она начинается с разбиения
исходного массива на две области. Эти части находятся слева и справа от отмеченного
элемента, называемого опорным. В конце процесса одна часть будет
содержать элементы меньшие, чем опорный, а другая часть будет содержать элементы больше
опорного. Код C++
void
SortAlgo::quickSort(int
* data, int const
len)
{
int const
lenD = len;
int
pivot = 0;
int
ind = lenD/2;
int
i,j = 0,k = 0;
if
(lenD>1){
int
* L = new int
;
int
* R = new int
;
pivot = data;
for
(i=0;i Для упрощения кода и улучшения читаемости мы введем метод Swap , который будет менять местами значения в массиве по индексу. Void Swap(T items, int left, int right)
{
if (left != right)
{
T temp = items;
items = items;
items = temp;
}
}
Сортировка пузырьком - это самый простой алгоритм сортировки. Он проходит по массиву несколько раз, на каждом этапе перемещая самое большое значение из неотсортированных в конец массива. Например, у нас есть массив целых чисел: При первом проходе по массиву мы сравниваем значения 3 и 7. Поскольку 7 больше 3, мы оставляем их как есть. После чего сравниваем 7 и 4. 4 меньше 7, поэтому мы меняем их местами, перемещая семерку на одну позицию ближе к концу массива. Теперь он выглядит так: Этот процесс повторяется до тех пор, пока семерка не дойдет почти до конца массива. В конце она сравнивается с элементом 8, которое больше, а значит, обмена не происходит. После того, как мы обошли массив один раз, он выглядит так: Поскольку был совершен по крайней мере один обмен значений, нам нужно пройти по массиву еще раз. В результате этого прохода мы перемещаем на место число 6. И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз. При следующем проходе обмена не производится, что означает, что наш массив отсортирован, и алгоритм закончил свою работу. Public void Sort(T items)
{
bool swapped;
do
{
swapped = false;
for (int i = 1; i < items.Length; i++) {
if (items.CompareTo(items[i]) > 0)
{
Swap(items, i - 1, i);
swapped = true;
}
}
} while (swapped != false);
}
Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее - нет. Важный момент: сортировка вставками обрабатывает элементы массива по порядку. Поскольку алгоритм проходит по элементам слева направо, мы знаем, что все, что слева от текущего индекса - уже отсортировано. На этом рисунке показано, как увеличивается отсортированная часть массива с каждым проходом: Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным. Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать: Алгоритм начинает работу с индекса 0 и значения 3. Поскольку это первый индекс, массив до него включительно считается отсортированным. На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно. Следующим проверяется значение 4. Так как оно меньше семи, мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex . Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки. Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так: Теперь часть массива, начиная от нулевого элемента и заканчивая элементом с индексом 2, отсортирована. Следующий проход начинается с индекса 3 и значения 4. По мере работы алгоритма мы продолжаем делать такие вставки. Когда больше нет возможностей для вставок, массив считается полностью отсортированным, и работа алгоритма закончена. Public void Sort(T items)
{
int sortedRangeEndIndex = 1;
while (sortedRangeEndIndex < items.Length)
{
if (items.CompareTo(items) < 0)
{
int insertIndex = FindInsertionIndex(items, items);
Insert(items, insertIndex, sortedRangeEndIndex);
}
sortedRangeEndIndex++;
}
}
private int FindInsertionIndex(T items, T valueToInsert)
{
for (int index = 0; index < items.Length; index++) {
if (items.CompareTo(valueToInsert) > 0)
{
return index;
}
}
throw new InvalidOperationException("The insertion index was not found");
}
private void Insert(T itemArray, int indexInsertingAt, int indexInsertingFrom)
{
// itemArray = 0 1 2 4 5 6 3 7
// insertingAt = 3
// insertingFrom = 6
//
// Действия:
// 1: Сохранить текущий индекс в temp
// 2: Заменить indexInsertingAt на indexInsertingFrom
// 3: Заменить indexInsertingAt на indexInsertingFrom в позиции +1
// Сдвинуть элементы влево на один.
// 4: Записать temp на позицию в массиве + 1.
// Шаг 1.
T temp = itemArray;
// Шаг 2.
itemArray = itemArray;
// Шаг 3.
for (int current = indexInsertingFrom; current > indexInsertingAt; current--)
{
itemArray = itemArray;
}
// Шаг 4.
itemArray = temp;
}
Сортировка выбором - это некий гибрид между пузырьковой и сортировкой вставками. Как и сортировка пузырьком, этот алгоритм проходит по массиву раз за разом, перемещая одно значение на правильную позицию. Однако, в отличие от пузырьковой сортировки, он выбирает наименьшее неотсортированное значение вместо наибольшего. Как и при сортировке вставками, упорядоченная часть массива расположена в начале, в то время как в пузырьковой сортировке она находится в конце. Давайте посмотрим на работу сортировки выбором на нашем неотсортированном массиве. При первом проходе алгоритм с помощью метода FindIndexOfSmallestFromIndex пытается найти наименьшее значение в массиве и переместить его в начало. Имея такой маленький массив, мы сразу можем сказать, что наименьшее значение - 3, и оно уже находится на правильной позиции. На этом этапе мы знаем, что на первой позиции в массиве (индекс 0) находится самое маленькое значение, следовательно, начало массива уже отсортировано. Поэтому мы начинаем второй проход - на этот раз по индексам от 1 до n — 1. На втором проходе мы определяем, что наименьшее значение - 4. Мы меняем его местами со вторым элементом, семеркой, после чего 4 встает на свою правильную позицию. Теперь неотсортированная часть массива начинается с индекса 2. Она растет на один элемент при каждом проходе алгоритма. Если на каком-либо проходе мы не сделали ни одного обмена, это означает, что массив отсортирован. После еще двух проходов алгоритм завершает свою работу: Public void Sort(T items)
{
int sortedRangeEnd = 0;
while (sortedRangeEnd < items.Length)
{
int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd);
Swap(items, sortedRangeEnd, nextIndex);
sortedRangeEnd++;
}
}
private int FindIndexOfSmallestFromIndex(T items, int sortedRangeEnd)
{
T currentSmallest = items;
int currentSmallestIndex = sortedRangeEnd;
for (int i = sortedRangeEnd + 1; i < items.Length; i++)
{
if (currentSmallest.CompareTo(items[i]) > 0)
{
currentSmallest = items[i];
currentSmallestIndex = i;
}
}
return currentSmallestIndex;
}
До сих пор мы рассматривали линейные алгоритмы. Они используют мало дополнительной памяти, но имеют квадратичную сложность. На примере сортировки слиянием мы посмотрим на алгоритм типа «разделяй и властвуй» (divide and conquer)
. Алгоритмы этого типа работают, разделяя крупную задачу на более мелкие, решаемые проще. Мы пользуемся ими каждый день. К примеру, поиск в телефонной книге - один из примеров такого алгоритма. Если вы хотите найти человека по фамилии Петров, вы не станете искать, начиная с буквы А и переворачивая по одной странице. Вы, скорее всего, откроете книгу где-то посередине. Если попадете на букву Т, перелистнете несколько страниц назад, возможно, слишком много - до буквы О. Тогда вы пойдете вперед. Таким образом, перелистывая туда и обратно все меньшее количество страниц, вы, в конце концов, найдете нужную. Насколько эффективны эти алгоритмы? Предположим, что в телефонной книге 1000 страниц. Если вы открываете ее на середине, вы отбрасываете 500 страниц, в которых нет искомого человека. Если вы не попали на нужную страницу, вы выбираете правую или левую сторону и снова оставляете половину доступных вариантов. Теперь вам надо просмотреть 250 страниц. Таким образом мы делим нашу задачу пополам снова и снова и можем найти человека в телефонной книге всего за 10 просмотров. Это составляет 1% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске. При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке. Давайте посмотрим на такой массив: Разделим его пополам: И будем делить каждую часть пополам, пока не останутся части с одним элементом: Теперь, когда мы разделили массив на максимально короткие участки, мы сливаем их в правильном порядке. Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив. Для работы алгоритма мы должны реализовать следующие операции: Стоит отметить, что в отличие от линейных алгоритмов сортировки, сортировка слиянием будет делить и склеивать массив вне зависимости от того, был он отсортирован изначально или нет. Поэтому, несмотря на то, что в худшем случае он отработает быстрее, чем линейный, в лучшем случае его производительность будет ниже, чем у линейного. Поэтому сортировка слиянием - не самое лучшее решение, когда надо отсортировать частично упорядченный массив. Public void Sort(T items)
{
if (items.Length <= 1)
{
return;
}
int leftSize = items.Length / 2;
int rightSize = items.Length - leftSize;
T left = new T;
T right = new T;
Array.Copy(items, 0, left, 0, leftSize);
Array.Copy(items, leftSize, right, 0, rightSize);
Sort(left);
Sort(right);
Merge(items, left, right);
}
private void Merge(T items, T left, T right)
{
int leftIndex = 0;
int rightIndex = 0;
int targetIndex = 0;
int remaining = left.Length + right.Length;
while(remaining > 0)
{
if (leftIndex >= left.Length)
{
items = right;
}
else if (rightIndex >= right.Length)
{
items = left;
}
else if (left.CompareTo(right) < 0)
{
items = left;
}
else
{
items = right;
}
targetIndex++;
remaining--;
}
}
Быстрая сортировка - это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги: Давайте посмотрим на работу алгоритма на следующем массиве: Сначала мы случайным образом выбираем ключевой элемент: Int pivotIndex = _pivotRng.Next(left, right);
Теперь, когда мы знаем ключевой индекс (4), мы берем значение, находящееся по этому индексу (6), и переносим значения в массиве так, чтобы все числа больше или равные ключевому были в правой части, а все числа меньше ключевого - в левой. Обратите внимание, что в процессе переноса значений индекс ключевого элемента может измениться (мы увидим это вскоре). Перемещение значений осуществляется методом partition . На этом этапе мы знаем, что значение 6 находится на правильной позиции. Теперь мы повторяем этот процесс для правой и левой частей массива. У нас осталось одно неотсортированное значение, а, поскольку мы знаем, что все остальное уже отсортировано, алгоритм завершает работу. Random _pivotRng = new Random();
public void Sort(T items)
{
quicksort(items, 0, items.Length - 1);
}
private void quicksort(T items, int left, int right)
{
if (left < right)
{
int pivotIndex = _pivotRng.Next(left, right);
int newPivot = partition(items, left, right, pivotIndex);
quicksort(items, left, newPivot - 1);
quicksort(items, newPivot + 1, right);
}
}
private int partition(T items, int left, int right, int pivotIndex)
{
T pivotValue = items;
Swap(items, pivotIndex, right);
int storeIndex = left;
for (int i = left; i < right; i++)
{
if (items[i].CompareTo(pivotValue) < 0)
{
Swap(items, i, storeIndex);
storeIndex += 1;
}
}
Swap(items, storeIndex, right);
return storeIndex;
}
На этом мы заканчиваем наш цикл статей по алгоритмам и структурам данных для начинающих. За это время мы рассмотрели связные списки, динамические массивы, двоичное дерево поиска и множества с примерами кода на C#. Как мы уже видели на примере быстрой сортировки, большую часть рекурсивных алгоритмов можно усовершенствовать, обрабатывая файлы небольших размеров специальным образом. В силу рекурсивного характера функции часто вызываются именно для небольших файлов, поэтому улучшение их обработки приводит к улучшению всего алгоритма. Следовательно, как и для быстрой сортировки, переключение на сортировку вставками подфайлов небольших размеров даст улучшение времени выполнения типичной реализации сортировки слиянием на 10-15%. Следующее полезное усовершенствование - это устранение времени копирования данных во вспомогательный массив, используемый слиянием. Для этого следует так организовать рекурсивные вызовы, что на каждом уровне процесс вычисления меняет ролями входной и вспомогательный массивы. Один из способов реализации такого подхода заключается в создании двух вариантов программ: одного для входных данных в массиве aux и выходных данных в массиве a, а другого - для входных данных в массиве a и выходных данных в массиве aux, обе эти версии поочередно вызывают одна другую. Другой подход продемонстрирован в программе 8.4, которая вначале создает копию входного массива, а затем использует программу 8.1 и переключает аргументы в рекурсивных вызовах, устраняя таким образом операцию явного копирования массива. Вместо нее программа поочередно переключается между выводом результата слияния то во вспомогательный, то во входной файл. (Это достаточно хитроумная программа.) Программа 8.4. Сортировка слиянием без копирования
Данная рекурсивная программа сортирует массив b, помещая результат сортировки в массив a. Поэтому рекурсивные вызовы написаны так, что их результаты остаются в массиве b, а для их слияния в массив a используется программа 8.1. Таким образом, все пересылки данных выполняются во время слияний. template Данный метод позволяет избежать копирования массива ценой возвращения во внутренний цикл проверок исчерпания входных файлов. (Вспомните, что устранение этих проверок в программе 8.2 преобразовало этот файл во время копирования в бито-нический.) Положение можно восстановить с помощью рекурсивной реализации той же идеи: нужно реализовать две программы как слияния, так и сортировки слиянием: одну для вывода массива по возрастанию, а другую - для вывода массива по убыванию. Это позволяет снова использовать битоническую стратегию и устранить необходимость в сигнальных ключах во внутреннем цикле. Поскольку при этом используются четыре копии базовых программ и закрученные рекурсивные переключения аргументов, такая супероптимизация может быть рекомендована только экспертам (ну или студентам), но все-таки она существенно ускоряет сортировку слиянием. Экспериментальные результаты, которые будут рассмотрены в разделе 8.6, показывают, что сочетание всех предложенных выше усовершенствований ускоряет сортировку слиянием процентов на 40, однако все же она процентов на 25 медленнее быстрой сортировки. Эти показатели зависят от реализации и от машины, но в разных ситуациях результаты похожи. Другие реализации слияния, использующие явные проверки исчерпания первого файла, могут привести к более (но не очень) заметным колебаниям времени выполнения в зависимости от характера входных данных. Для случайно упорядоченных файлов после исчерпания подфайла размер другого подфайла будет небольшим, а затраты на пересылку во вспомогательный файл все так же пропорциональны размеру этого подфайла. Можно еще попытаться улучшить производительность сортировки слиянием в тех случаях, когда файл в значительной степени упорядочен, и пропускать вызов merge при полной упорядоченности файла, однако для многих типов файлов данная стратегия неэффективна. Упражнения
8.16. Реализуйте абстрактное обменное слияние, использующее дополнительный объем памяти, пропорциональный размеру меньшего из сливаемых файлов. (Этот метод должен сократить наполовину потребность сортировки в памяти.) 8.17. Выполните сортировку слиянием больших случайно упорядоченных файлов и экспериментально определите среднюю длину другого подфайла на момент исчерпания первого подфайла как функцию от N (сумма длин двух сливаемых подфайлов). 8.18. Предположим, программа 8.3 модифицирована так, что не вызывает метод merge при a[m] < a
. Сколько сравнений экономится в этом случае, если сортируемый файл уже упорядочен? 8.19. Выполните модифицированный алгоритм, предложенный в упражнении 8.18, для больших случайно упорядоченных файлов. Экспериментально определите среднее количество пропусков вызова merge в зависимости от N (размер исходного сортируемого файла). 8.20. Допустим, что сортировка слиянием должна быть выполнена на h-сортированном файле для небольшого значения h. Какие изменения нужно внести в подпрограмму merge, чтобы воспользоваться этим свойством входных данных? Поэкспериментируйте с гибридами сортировки методом Шелла и сортировки слиянием, основанными на этой подпрограмме. 8.21. Разработайте реализацию слияния, уменьшающую требование дополнительной памяти до max(M, N/M)
за счет следующей идеи. Разбейте массив на N/M
блоков размером M (для простоты предположим, что N кратно M). Затем, (1) рассматривая эти блоки как записи, первые ключи которых являются ключами сортировки, отсортируйте их с помощью сортировки выбором, и (2) выполните проход по массиву, сливая первый блок со вторым, затем второй блок с третьим и так далее. 8.22. Докажите, что метод, описанный в упражнении 8.21, выполняется за линейное время. 8.23. Реализуйте битоническую сортировку слиянием без копирования. Как было сказано в "Рекурсия и деревья" , у каждой рекурсивной программы имеется нерекурсивный аналог, который хотя и выполняет эквивалентные действия, но может делать это в другом порядке. Нерекурсивные реализации сортировки слиянием заслуживают детального изучения в качестве образцов философии алгоритмов " разделяй и властвуй " . Рассмотрим последовательность слияний, выполняемую рекурсивным алгоритмом. Из примера, приведенного на рис.
8.2 , видно, что файл размером 15 сортируется следующей последовательностью слияний: 1-и-1 1-и-1 2-и-2 1-и-1 1-и-1 2-и-2 4-и-4 1-и-1 1-и-1 2-и-2 1-и-1 2-и-1 4-и-3 8-и-7. Порядок выполнения слияний определяется рекурсивной структурой алгоритма. Но подфайлы обрабатываются независимо, поэтому слияния могут выполняться в различном порядке. На рис.
8.4 показана восходящая стратегия, при которой последовательность слияний такова: 1-и-1 1-и-1 1-и-1 1-и-1 1-и-1 1-и-1 1-и-1 2-и-2 2-и-2 2-и-2 2-и-1 4-и-4 4-и-3 8-и-7.
В каждой строке показан результат вызова метода merge при выполнении восходящей сортировки слиянием. Вначале выполняются слияния 1-и-1
: при слиянии A и S
получается A S
; при слиянии O и R
получается O R
и т.д. Из-за нечетности размера файла последнее E не принимает участие в слиянии. На втором проходе выполняются слияния 2-и-2
: A S
сливается с O R
, и получается A O R S
и т.д., до последнего слияния 2-и-1
. После этого выполняются слияния 4-и-4
, 4-и-3
и завершающее 8-и-7
. В обоих случаях выполняются семь слияний 1-и-1
, три слияния 2-и-2
и по одному слиянию 2-и-1, 4-и-4, 4-и-3 и 8-и-7
, но они выполняются в различном порядке. Восходящая стратегия предлагает сливать наименьшие из оставшихся файлов, проходя по массиву слева направо. Последовательность слияний, выполняемая рекурсивным алгоритмом, определяется деревом " разделяй и властвуй " , показанным на рис.
8.3 : мы просто выполняем обратный проход по этому дереву. Как было показано в "Элементарные структуры данных" , можно разработать нерекурсивный алгоритм, использующий явный стек, который даст ту же последовательность слияний. Однако совсем не обязательно ограничиваться только обратным порядком: любой проход по дереву, при котором обход поддеревьев узла завершается перед посещением самого узла, дает правильный алгоритм. Единственное ограничение заключается в том, что сливаемые файлы должны быть предварительно отсортированы. В случае сортировки слиянием удобно сначала выполнять все слияния 1-и-1
, затем все слияния 2-и-2
, затем все 4-и-4
, и так далее. Такая последовательность соответствует обходу дерева по уровням, который поднимается по дереву снизу вверх. В "Рекурсия и деревья" мы уже видели на нескольких приме -рах, что при рассуждении в стиле снизу-вверх имеет смысл переориентировать мышление в сторону стратегии " объединяй и властвуй " , когда сначала решаются небольшие подзадачи, а затем они объединяются для получения решения большей задачи. В частности, нерекурсивный вариант вида " объединяй и властвуй " сортировки слиянием в программе 8.5 получается следующим образом: вначале все элементы файла рассматриваются как упорядоченные подсписки длиной 1. Потом для них выполняются слияния 1-и-1
, и получаются упорядоченные подсписки размером 2, затем выполняется серия слияний 2-и-2
, что дает упорядоченные подсписки размером 4, и так далее до упорядочения всего списка. Если размер файла не является степенью 2, то последний подсписок не всегда имеет тот же размер, что и все другие, но его все равно можно слить. Если размер файла является степенью 2, то множество слияний, выполняемых восходящей сортировкой слиянием, в точности совпадает с множеством слияний, выполняемым рекурсивной сортировкой слиянием, однако последовательность слияний будет другой. Восходящая сортировка слиянием соответствует обходу дерева " разделяй и властвуй " по уровням, снизу вверх. В противоположность этому, рекурсивный алгоритм называется нисходящей сортировкой слиянием - в силу обратного обхода дерева сверху вниз. Если размер файла не равен степени 2, восходящий алгоритм дает другое множество слияний, как показано на рис.
8.5 . Восходящий алгоритм соответствует дереву " объединяй и властвуй " (см. упражнение 5.75), отличному от дерева " разделяй и властвуй " , которое соответствует нисходящему алгоритму. Можно сделать так, чтобы последовательность слияний, выполняемых рекурсивным методом, была такой же, как и для нерекурсивного метода, однако для этого нет особых причин, поскольку разница в производительности невелика по отношению к общим затратам. Если размер файла не равен степени 2, то структуры слияний для восходящей сортировки слиянием совершенно не похожи на структуры слияний для нисходящей сортировки (
рис.
8.3). При восходящей сортировке размеры всех файлов (возможно, за исключением последнего) равны степени 2. Эти различия помогают понять базовую структуру алгоритмов, но почти не влияют на производительность. Леммы 8.1-8.4 справедливы и для восходящей сортировки слиянием, при этом имеют место следующие дополнительные леммы: Лемма 8.5.
Все слияния на каждом проходе восходящей сортировки слиянием манипулируют файлами, размер которых равен степени 2, за исключением, возможно, размера последнего файла. Это факт легко доказать методом индукции. Лемма 8.6.
Количество проходов при восходящей сортировке слиянием по файлу из N элементов в точности равно числу битов в двоичном представлении N (без ведущих нулей). Размер подсписков после к проходов равен 2 k , т.к. на каждом проходе восходящей сортировки слиянием размер упорядоченных подфайлов удваивается. Значит, количество проходов, необходимое для сортировки файла из N элементов, есть наименьшее к такое, что , что в точности равно , т.е. количеству битов в двоичном представлении N. Этот результат можно доказать и методом индукции или с помощью анализа структурных свойств деревьев " объединяй и властвуй " . ¦ Программа 8.5. Восходящая сортировка слиянием
Восходящая сортировка слиянием состоит из последовательности проходов по всему файлу с выполнением слияний вида m-и-m и с
удвоением m на каждом проходе. Последний подфайл имеет размер m лишь тогда, когда размер файла является четным кратным m, так что последнее слияние имеет тип m-и-х
, для некоторого х, меньшего или равного m. Подводя итоги, отметим, что нисходящая и восходящая сортировки - это два простых алгоритма сортировки, основанных на операции слияния двух упорядоченных подфайлов в результирующий объединенный упорядоченный файл. Оба алгоритма тесно связаны между собой и даже выполняют одно и то же множество слияний, если размер исходного файла является степенью 2, но они отнюдь не идентичны. На рис.
8.7 демонстрируются различия динамических характеристик алгоритмов на примере большого файла. Каждый алгоритм может использоваться на практике, если экономия памяти не важна, и желательно гарантированное время выполнения в худшем случае. Оба алгоритма представляют интерес как прототипы общих принципов построения алгоритмов: " разделяй и властвуй " и " объединяй и властвуй " . Восходящая сортировка слиянием (слева) выполняет серию проходов по файлу, которые сливают упорядоченные подфайлы, пока не останется только один. Каждый элемент файла, за исключением, возможно, последнего, участвует в каждом проходе. В отличие от этого, нисходящая сортировка слиянием (справа) вначале упорядочивает первую половину файла, а затем берется за вторую половину (рекурсивно), поэтому диаграмма ее работы существенно отличается. Упражнения
8.24. Покажите, какие слияния выполняет восходящая сортировка слиянием (программа 8.5) для ключей E A S Y Q U E S T I O N
. 8.25. Реализуйте восходящую сортировку слиянием, которая начинает с сортировки вставками блоков по M элементов. Определите эмпирическим путем значение M, для которого разработанная программа быстрее всего сортирует произвольно упорядоченные файлы из N элементов, при
N = 10 3 , 10 4 , 10 5 и 10 6
. 8.26. Нарисуйте деревья, которые отображают слияния, выполняемые программой 8.5 для N = 16, 24, 31, 32, 33 и 39
. 8.27. Напишите программу рекурсивной сортировки слиянием, выполняющую те же слияния, что и восходящая сортировка слиянием. 8.28. Напишите программу восходящей сортировки слиянием, выполняющую те же слияния, что и нисходящая сортировка слиянием. (Это упражнение намного труднее, чем упражнение 8.27). 8.29. Предположим, что размер файла является степенью 2. Удалите рекурсию из нисходящей сортировки слиянием так, чтобы получить нерекурсивную сортировку слиянием, выполняющую ту же последовательность слияний. 8.30. Докажите, что количество проходов, выполняемых нисходящей сортировкой слиянием, также равно количеству битов в двоичном представлении числа N (см. лемму 8.6). Процедура
слияния требует два отсортированных
массива. Заметив, что массив из одного
элемента по определению является
отсортированным, мы можем осуществить
сортировку следующим образом: разбить
имеющиеся элементы массива на пары и
осуществить слияние элементов каждой
пары, получив отсортированные цепочки
длины 2 (кроме, быть может, одного
элемента, для которого не нашлось пары); разбить
имеющиеся отсортированные цепочки на
пары, и осуществить слияние цепочек
каждой пары; если
число отсортированных цепочек больше
единицы, перейти к шагу 2. Проще
всего формализовать этот алгоритм
рекурсивным способом (в следующем
разделе мы реализуем этот алгоритм
итерационным способом). Функция
сортирует
участок массива от элемента с номером
a до элемента с номером b: Поскольку
функция сортирует лишь часть массива,
то при слиянии двух фрагментов ей не
остаётся ничего, кроме как выделять
временный буфер для результата слияния,
а затем копировать данные обратно: void
MergeSort(char* M, int c) if(c<2)return;//
если размер меньше 2 то он упорядочен MergeSort(M,c/2);//отсортировать
рекурсивно первую //половину MergeSort(M+c/2,c-c/2);//
оставшуюся часть char*
T=(char*)malloc(c*sizeof(char)); Merge(M,c/2,M+c/2,c-c/2,T);//объеденить
в один for(int
i=0;i Листинг
2. Реализация сортировки слиянием
Имея
в своем распоряжении процедуру слияния,
нетрудно воспользоваться ею в качестве
основы для рекурсивной процедуры
сортировки. Чтобы отсортировать
заданный файл, мы делим его на две части,
выполняем рекурсивную сортировку обеих
частей, после чего производим их слияние.
Реализация этого алгоритма представлена
в программе 8.3; пример иллюстрируется
на рис. 8.2. Этот
алгоритм является одним из широко
известных примеров использования
принципа "разделяй
и властвуй"
при
разработке эффективных алгоритмов. Рисунок
8.2 Пример нисходящей сортировки слиянием Нисходящая
сортировка слиянием аналогична принципу
управления сверху вниз, в рамках которого
руководитель организует работы таким
образом, что получив большую задачу, он
разбивает ее на подзадачи, которые
должны независимо решать его подчиненные.
Если каждый руководитель будет решать
свою задачу, разбивая ее на две равные
части с последующим объединением
решений, полученных его подчиненными
и последующей передачей результата
своему начальству, то примерно также
организована сортировка слиянием.
Работа недалеко продвинется, пока
кто-то, кто не имеет в своем подчинении
исполнителей, не получит и не выполнит
свою задачу (в рассматриваемом случае
это слияние двух файлов размером I);
однако руководство выполняет значительную
часть работы, соединяя результаты работы
подчиненных в единое целое. Сортировка
слиянием играет важную роль благодаря
простоте и оптимальности заложенного
в нее
метода (время
ее выполнения пропорционально.Vlog/V),
который допускает возможность
реализации, обладающей устойчивостью.
Эти утверждения сравнительно нетрудно
доказать. Можно
воспользоваться древовидной структурой,
чтобы получить наглядное представление
о структуре рекурсивных вызовов
рекурсивного алгоритма, что поможет
понять все варианты рассматриваемого
алгоритма и провести его анализ. Что
касается сортировки слиянием, то
структура рекурсивных вызовов целиком
зависит от размеров ввода. Для любого
заданного N
мы
строим дерево, получившее название
"дерево
разделяй и властвуй"
описывает размер подфайлов, подвергаемых
обработке в процессе выполнения программы
8.3 Программа
8.3. Нисходящая сортировка слиян
ием Эта
базовая реализация сортировки слиянием
является примером рекурсивной программы,
прототипом которой служит принцип
"разделяй и властвуй". Она выполняет
сортировку массива а,..., а[г] путем
деления его на две части а,...,а[m]
и а,...,а(г]
с последующей их сортировкой независимо
друг от друга (через рекурсивные
вызовы) и слияния полученных упорядоченных
подфайлов с тем, чтобы в конечном итоге
получить отсортированный исходный
файл. Функция может потребовать
использования вспомогательного файла,
достаточно большого, чтобы принять
копию входного файла, однако эту
абстрактную операцию удобно рассматривать
как обменное слияние. Структурные
свойства сбалансированных деревьев,
построенных по принципу "разделяй и
властвуй", имеют непосредственное
отношение к анализу сортировки слиянием.
Например, общее количество операций
сравнения, выполняемых алгоритмом,
в точности равно сумме всех меток узлов. Рисунок
8.3. Деревья,построенный по принципу
«разделяй и влавствуй». Эти
диаграммы иллюстрируют размеры подзадач,
возникающих в процессе выполнения
нисходящей сортировки слиянием. В
отличие от деревьев, соответствующих,
например, быстрой.
сортировке,
эти схемы определяются только размерами
исходного файла,
а
не значениями ключей, присутствующих
в файле. Верхняя диаграмма показывает,
как сортируется файл, состоящий их 32
элементов.
Мы (рекурсивно) сортируем два файла по
16
элементов,
затем выполняем их слияние. Файлы
сортируются по 16 мементов с выполнением
(рекурсивной) сортировки файлов по 8
элементов и т.д. Для файлов, размер
которых нельзя представить в виде
степени 2, схема оказывается несколько
более сложной, в чем нетрудно убедиться
из нижней диаграммы Сортировка
слиянием требует выполнения примерно
NlogN
операций сравнения для сортировки
любого файла из N элементов
.
Каждое
слияние типа (N
/2)
на
(N
/2)
требует
N
сравнений
(это значение будет для разных файлов
отличаться на 1 или на 2, в зависимости
от того, как используются служебные
метки). Следовательно, общее количество
сравнений при сортировке в полном объеме
может быть описано стандартным
сбалансированным рекуррентным
соотношением: Mn
=
M
[
n
/
2]
+
M
[
n
\
2]
+
N,
где M1=0.
Такое рекуррентное соотношение описывает
также сумму меток узлов и длину внешнего
пути). Это утверждение нетрудно проверить,
когда N
является
степенью числа 2 доказать методом
индукции для произвольного N.
Сортировка
слиянием использует дополнительное
пространство, пропорциональное N.
Мы
можем предпринять некоторые шаги, дабы
уменьшить размеры используемого
дополнительного пространства за
счет существенного усложнения алгоритма.Cортировка
слиянием также эффективна, если
сортируемый файл организован как связный
список. В этом случае указанное
свойство сохраняется, однако для связей
расходуется дополнительное пространство
памяти. В случае массивов, как отмечалось
в разделе можно выполнять обменное
слияние однако эта стратегия вряд ли
оправдывается на практике. Сортировка
слиянием устойчива, если устойчив
используемый при этом метод слияния.
Это
утверждение легко проверить методом
индукции. Для реализации метода слияния,
предложенного в программе 8.1,
легко показать, что относительная
позиция дублированных ключей не
нарушается. Однако, чем сложнее алгоритм,
тем выше вероятность того, что эта
устойчивость будет нарушена Потребность
ресурсов со стороны сортировки слиянием
не чувствительна по отношению к исходному
порядку входного файла.
В
наших реализациях входные данные
определяют разве что порядок, в котором
элементы обрабатываются во время
слияний. Каждый проход требует пространства
памяти и числа шагов, пропорциональных
размеру подфайла. что обусловливается
необходимостью затрат на перемещение
данных во вспомогательный файл.
Соответствующие две ветви оператора
if
могут потребовать слегка отличающихся
значений времени для выполнения
компиляции, что в свою очередь приводит
к некоторой зависимости времени
выполнения от характера входных данных,
однако число сравнений и других
операций не зависит от того, как упорядочен
входной файл.Сортировка естественным слиянием
Delphi (сортировка произвольных типов данных - простое слияние)
D
Python 2.7 (функциональная реализация)
Сортировка выбором (Selection sort)
Пузырьковая сортировка (Bubble sort)
Сортировка вставками (Insertion sort)
Сортировка слиянием (Merge sort)
Быстрая сортировка (Quick sort)
Пузырьковая сортировка
Сортировка вставками
Сортировка выбором
Сортировка слиянием
Разделяй и властвуй
Сортировка слиянием
Быстрая сортировка
Заключение
Восходящая сортировка слиянием
Рис.
8.4.
Рис.
8.5.
Рис.
8.7.
3.Нисходящая сортировка слиянием.