Сортировка слияниями

Метод слияний – один из первых в теории алгоритмов сортировки. Он предложен Дж. фон Нейманом в 1945 году.

Рассмотрим следующую задачу. Объединить («слить») упорядоченные фрагменты массива A A [ k ],... A [ m ] и A [ m +1],..., A [ q ] в один A [ k ],..., A [ q ], естественно, тоже упорядоченный (k £ m £ q). Основная идея решения состоит в сравнении очередных элементов каждого фрагмента, выяснении, какой из элементов меньше, переносе его во вспомогательный массив D (для простоты) и продвижении по тому фрагменту массива, из которого взят элемент. При этом следует не забыть записать в D оставшуюся часть того фрагмента, который не успел себя «исчерпать».

Пример. Пусть первый фрагмент состоит из 4-х элементов: 2 4 6 11, а второй – из 8-и: 1 3 5 7 14 17. Рис 1. Иллюстрация слияния упорядоченных фрагментов. иллюстрирует начало объединения упорядоченных фрагментов.

Рис 1. Иллюстрация слияния упорядоченных фрагментов.

Реализация слияния фрагментов:

#include < iostream>

#include < locale.h>

using namespace std;

void Sl(int m[], int k, int q) // или...int *a

{

// k – нижняя граница упорядоченного фрагмента

// q – верхняя граница фрагмента

int i, j, t, mid, d[20];

i=k;

mid=k+(q-k)/2;

j=mid+1;

t=1;

while (i< =mid & & j< =q)

{

if (m[i]< =m[j]) {d[t]=m[i]; i++; }

else { d[t]=m[j]; j++; }

t++;

}

// Один из фрагментов обработан полностью, осталось перенести в D остаток другого фрагмента

while (i< =mid)

{ d[t]=m[i]; i++; t++; }

while (j< =q)

{ d[t]=m[j]; j++; t++; }

for (i=1; i< =t-1; i++) m[k+i-1]=d[i];

}

// Рекурсивная реализация сортировки слиянием

void Sort_Sl(int *m, int i, int j)

{

int t;

if (i< j)

// Обрабатываемый фрагмент массива состоит более, чем из одного элемента

if (j-i==1) {

if (m[j]< m[i])

// Обрабатываемый фрагмент массива состоит из двух элементов*)

{ t=m[i]; m[i]=m[j]; m[j]=t; }; }

else {

// Разбиваем заданный фрагмент на два

Sort_Sl(m, i, i+(j-i)/2); // рекурсивные вызовы процедуры Sort_Sl

Sort_Sl(m, i+(j-i)/2+1, j);

Sl(m, i, j);

}

}

void input(int *m, int & n) // Имя массива является адресом его начала.

{ // Или void input(int m[], int & n)

cout< < " Введите количество элементов массива ";

cin> > n;

for (int i=0; i< n; i++)

{

cout< < " a[" < < i< < " ]=";

cin> > m[i]; // Конструкция a[i] эквивалентна *(a + i)

}

}

void print (int *m, int n)

{

for (int i=0; i< n; i++)

cout< < m[i]< < " ";

cout< < " \n";

}

void main()

{

setlocale(LC_ALL, " rus");

const int nmax=20;

int n, a[nmax];

input(a, n);

cout< < " Исходный массив: \n";

print(a, n);

Sort_Sl(a, 0, n-1);

cout< < " Отсортированный массив: \n";

print(a, n);

}

Первый вызов процедуры – Sort_Sl(a, 0, n-1);, где a – исходный массив из N элементов.

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

9. Быстрая сортировка (сортировка Хоара, 1962) [1]