Сортировка слиянием паскаль. Сортировка слиянием
Процедура слияния требует два отсортированных массива. Заметив, что массив из одного элемента по определению является отсортированным, мы можем осуществить сортировку следующим образом:
разбить имеющиеся элементы массива на пары и осуществить слияние элементов каждой пары, получив отсортированные цепочки длины 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
могут потребовать слегка отличающихся
значений времени для выполнения
компиляции, что в свою очередь приводит
к некоторой зависимости времени
выполнения от характера входных данных,
однако число сравнений и других
операций не зависит от того, как упорядочен
входной файл. Сортировка слиянием (англ. merge sort
) - алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например - потоки) в определённом порядке. Эта сортировка - хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
3.Нисходящая сортировка слиянием.
- массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице;
- далее выполняется операция алгоритма, называемая слиянием. Два единичных массива сливаются в общий результирующий массив, при этом из каждого выбирается меньший элемент (сортировка по возрастанию) и записывается в свободную левую ячейку результирующего массива. После чего из двух результирующих массивов собирается третий общий отсортированный массив, и так далее. В случае если один из массивов закончиться, элементы другого дописываются в собираемый массив;
- в конце операции слияния, элементы перезаписываются из результирующего массива в исходный.
Реализация алгоритма на различных языках программирования:
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).
При написании статьи были использованы открытые источники сети интернет:
Кто-то сказал однажды, что
Я не стремился доказать это высказывание. Я стремился опровергнуть свою тупость.
Допустим у нас есть два массива чисел, отсортированных по возрастанию. Int a1 = new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500};
int a2 = new int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000};
Int a3 = new int;
Что это такое? В интернете есть ответ, есть описание алгоритма, но я его не понял с одного присеста и решил разобраться сам. Для этого необходимо понять базовый принцип алгоритма, чтобы можно было по памяти воссоздать алгоритм применительно к своей задаче. 10, 21
10, 21, 11, 23
После второго прохода в буфере будет 21, 23 и 11. Что с ними делать – непонятно, сравнить более двух элементов можно, но уже не так просто. Давайте тогда условимся, что будем брать в этот буфер по одному элементу от каждого массива. Так как проще сравнивать два элемента между собой, да и вообще у нас две сущности – два массива. Тогда после второго прохода в буфере будет 21 и 11, потому что «представитель» первого массива в буфере уже есть – это 21. Сравниваем их и меньший отправляем в результирующий массив. Тогда после второго прохода будем иметь в результирующем массиве: 10, 11
На третьем проходе берем в буфер из второго массива 41, потому что «представитель» первого массива в буфере так и остался. Сравниваем 21 и 41, и наконец-то убираем из буфера 21. После третьего прохода будем иметь в результирующем массиве: 10, 11, 21
10, 11, 21, 23
10, 11, 21, 23, 24, 40, 41, 50, 65, 75, 76, 78, 77, 86, 98, 101, 190, 900, 1100, 1200, 2100, 2200, 2300, 2400, 2500,
Пусть первый массив (для примера возьмем из него несколько элементов) имеет следующее расположение элементов: 2100, 23, 40, 24, 2, 1.
2150, 23, 40
2100, 23
40
24, 2
1
23, 2100
40
2, 24
1
23, 40, 2100
1, 2, 24
1, 2, 23, 24, 40, 2100
После разбиения следует обратное слияние, при котором в один момент времени (или за проход цикла) выбираются по одному элементу от каждого массива и сравниваются между собой. Наименьший (или наибольший) элемент отправляется в результирующий массив, оставшийся элемент остается актуальным для сравнения с элементом из другого массива на следующем шаге. Int a1 = new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500};
int a2 = new int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000};
int a3 = new int;
int i=0, j=0;
for (int k=0; k A1 и a2 – массивы, которые надо слить; Первые два условия проверяют, что бы индексы не вышли за переделы количества элементов в массивах. Третье и четвертое условия обеспечивают перемещение в массив наименьшего элемента из первого массива и из второго соответственно. Private void SortUnsorted(int a, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
SortUnsorted(a, lo, mid);
SortUnsorted(a, mid + 1, hi);
int buf = Arrays.copyOf(a, a.length);
for (int k = lo; k <= hi; k++)
buf[k] = a[k];
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = buf[j];
j++;
} else if (j > hi) {
a[k] = buf[i];
i++;
} else if (buf[j] < buf[i]) {
a[k] = buf[j];
j++;
} else {
a[k] = buf[i];
i++;
}
}
}
A – массив; Алгоритм сортировки слиянием
был предложен праотцом современных компьютеров – Джоном фон Нейманом. Сам метод является устойчивым, т. е. он не меняет одинаковые по значению элементы в списке. В основе сортировки слиянием лежит принцип «разделяй и властвуй». Список разделяется на равные или практически равные части, каждая из которых сортируется отдельно. После чего уже упорядоченные части сливаются воедино. Несколько детально этот процесс можно расписать так: 1. массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице; 2. далее, выполняется операция алгоритма, называемая слиянием. Два единичных массива сливаются в общий результирующий массив, при этом из каждого выбирается меньший элемент (сортировка по возрастанию) и записывается в свободную левую ячейку результирующего массива. После чего из двух результирующих массивов собирается третий общий отсортированный массив, и так далее. В случае если один из массивов закончиться, элементы другого дописываются в собираемый массив; 3. в конце операции слияния, элементы перезаписываются из результирующего массива в исходный. Подпрограмма MergeSort
рекурсивно разбивает и сортирует массив, а Merge
отвечает за его слияние. Так можно записать псевдокод основной подпрограммы: Подпрограмма MergeSort
(A
, first
, last
) A
– массив first
, last
– номера первого и последнего элементов соответственно Если first
<last
то Вызов MergeSort
(A
, first
, (first
+last
)/2) //сортировка левой части Вызов MergeSort
(A
, (first
+last
)/2+1, last
) //сортировка правой части Вызов Merge
(A
, first
, last
) //слияние двух частей Эта подпрограмма выполняется только в том случае, если номер первого элемента меньше номера последнего. Как уже говорилось, из подпрограммы MergeSort
вызывается подпрограмма Merge
, которая выполняет операцию слияния. Перейдем к рассмотрению последней. Работа Merge
заключается в образовании упорядоченного результирующего массива путем слияния двух также отсортированных массивов меньших размеров. Вот псевдокод этой подпрограммы: Подпрограмма Merge
(A
, first
, last
) start
, final
– номера первых элементов левой и правой частей mas
– массив, middle
- хранит номер среднего элемента middle
=(first+last)/2 //вычисление среднего элемента start
=first
//начало левой части final
=middle
+1 //начало правой части Цикл j
=first
до last
выполнять //выполнять от начала до конца Если ((start
<=middle
) и ((final
>last
) или (A
[start
]<A
[final
]))) то mas
[j
]=A
[start
] увеличить start
на 1 mas
[j
]=A
[final
] увеличить final
на 1 Цикл j
=first
до last
выполнять //возвращение результата в список A
[j
]=mas
[j
] Разберем алгоритм сортировки слиянием на следующем примере (рис. 6.10). Имеется неупорядоченная последовательность чисел: 2, 6, 7, 1, 3, 5, 0, 4. После разбивки данной последовательности на единичные массивы, процесс сортирующего слияния (по возрастанию) будет выглядеть так: Рисунок 6.10 – Пример сортировки слиянием Массив был разделен на единичные массивы, которые алгоритм сливает попарно до тех пор, пока не получится один массив, все элементы которого стоят на своих позициях. Код программы на C++: void Merge(int *A, int first, int last) //функция, сливающая массивы int middle, start, final, j; int *mas=new int; middle=(first+last)/2; //вычисление среднего элемента start=first; //начало левой части final=middle+1; //начало правой части for(j=first; j<=last; j++) //выполнять от начала до конца if ((start<=middle) && ((final>last) || (A
mas[j]=A; mas[j]=A; for (j=first; j<=last; j++) A[j]=mas[j]; //возвращение результата в список void MergeSort(int *A, int first, int last) //рекурсивная процедура сортировки if (first MergeSort(A, first, (first+last)/2); //сортировка левой части MergeSort(A, (first+last)/2+1, last); //сортировка правой части Merge(A, first, last); //слияние двух частей void main() //главная функция cout<<"Размер массива > "; cin>>n; for (i=1; i<=n; i++) cout< "; MergeSort(A, 1, n); //вызов сортирующей процедуры cout<<"Упорядоченный массив: "; //вывод упорядоченного массиваСортировка естественным слиянием
Delphi (сортировка произвольных типов данных - простое слияние)
D
Python 2.7 (функциональная реализация)
...any scientist who couldn"t explain to an eight-year-old what he was doing was a charlatan.
Оказывается, это был Курт Воннегут.
Необходимо слить их в один упорядоченный массив.
Это задача для сортировки слиянием.Начали за здравие
Давайте пойдем постепенно и воспользуемся тем, что лежит на поверхности: будем брать поочередно по одному элементу из каждого массива, сравнивать их и «сливать» в один массив. Меньший элемент будем ставить первым, больший – вторым. Тогда после первого прохода все нормально:
А после второго прохода уже не очень:
Понятно, что надо сравнивать элементы еще и с уже добавленными.Начнем еще раз
Пусть у нас будет некий временный буфер из сравниваемых на каждом шаге элементов. После первого прохода в него попадут 21 и 10. После сравнения мы переместим из буфера в результирующий массив меньший элемент 10 и оставим больший элемент 21, потому что не знаем, что будет за ним.
А в буфере – 21.
На четвертом проходе будем сравнивать два значения из буфера - 41 и 23. В результирующем массиве будет:
То есть только сейчас – на четвертом, а не на втором проходе - результат получился правильным. Получается, что в цикле надо помнить текущий индекс для каждого массива, а сам цикл может быть длиной равной сумме длин массивов.Подходим к концу, но вдруг
Что будем делать, когда результирующий массив будет состоять из:
В буфере будет 3000 из второго массива, а в первом - все элементы кончатся? Так как массивы у нас отсортированы, то просто берем 3000 из буфера и оставшееся 5000. То есть нужно для каждого индекса выполнять проверку – не превысили ли мы количество элементов в каждом из массивов.Усложним задачу
А если у нас не отсортированные массивы? Обычно задача сводится к тому, чтобы отсортировать один массив. Тогда сортировка слиянием тоже может быть использована.
Будем его сортировать. Раз легче сравнивать по два элемента, то разобьем поровну массив на два:
и
24, 2, 1.
Получится по три элемента. Много! Разобьем поровну каждый массив, получится четыре массива:
Отсортируем теперь каждый из массивов простым сравнением первого и второго элементов (там где они есть):
И будем сливать обратно по предыдущему алгоритму – через буфер. После первого слияния получим два массива:
И снова сливаем – уже в один массив:
Так мы отсортировали слиянием массив.В сухом остатке
Таким образом, сортировка слиянием подразумевает разбиение массива поровну до тех пор пока из одного массива не получится несколько мелких - размером не более двух элементов. Два элемента легко сравнить между собой и упорядочить в зависимости от требования: по возрастанию или убыванию.Выразим в коде (Java)
Пример сортировки по возрастанию двух отсортированных массивов:
Здесь:
a3 – результирующий массив;
i и j – индексы для массивов a1 и a2 соответственно, которые указывают на текущие элементы на каждом шаге и образуют тот самый буфер. Функция сортировки слиянием
Оформим приведенный код как рекурсивную функцию, которая станет разделять массивы до тех пор, пока это возможно, с параметрами, соответствующими целому массиву при первом вызове, его половинам при втором и третьем вызовах и т. д.
Здесь:
lo – позиция первого элемента в массиве (для первой итерации = 0);
hi – позиция последнего элемента в массиве (для первой итерации = a.length - 1).