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

Существует еще один метод сортировки элементов массива, эффективность которого сравнительно велика, - метод слияний.

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

Пусть массив а [1...n ] разбивается на части длиной k, тогда первая часть - а [ 1 ], а [ 2 ],...., а [ k ], вторая - а [ k +1 ], а [ k + 2 ],...., а [ 2k ] и так далее. Если n не делится на k, то в последней части будет менее k элементов.

После того как массивы - части упорядочены, можно объединить их в упорядоченные массивы - части, состоящие не более чем из 2 k элементов, которые далее объединить в упорядоченные массивы длиной не более 4 k, и так далее, пока не получится один упорядоченный массив.

Таким образом, чтобы получить отсортированный массив этим методом, нужно многократно “сливать” два упорядоченных отрезка массива в один упорядоченный отрезок. При этом другие части массива не затрагиваются.

Задача

Дан массив а [ 1...k ] целых чисел и числа k, m, n, такие, что k ≤ m ≤ n. Описать процедуру, которая сливает отрезки массива а [ k + 1 ],..., а [ m ] и а [ m + 1 ],,...., а [ n ] в упорядоченный отрезок а [ k + 1 ],..., а [ n ].

Основная идея решения состоит в сравнении очередных элементов каждой части, выяснении, какой из них меньше, переносе его в массив с, который является вспомогательным, и продвижении по тому массиву - части, из которого взят элемент. Когда одна из частей будет пройдена до конца, остается только перенести в с оставшиеся элементы второй части, сохраняя их порядок.

Рассмотрим пример.

Пусть первая часть (часть а) состоит из 5 элементов:

... 3 5 8 11 16...,

а вторая часть (часть b) - из 8 элементов:

... 1 5 7 9 12 13 18 20...

По условию оба массива - части упорядочены. Нужно сформировать массив с, который будет содержать 13 элементов.

Введем обозначения:

i - номер обрабатываемого элемента части а;

j - номер обрабатываемого элемента части b;

g - номер заполняемого массива части с.

Поскольку заполнение массива с ведется с его начала, на первом шаге значение g =1.

1 - й шаг: на первое место в массиве с претендуют а [k + 1] = 3 и

b [ m + 1 ] = 1 (i = k + 1, j = m + 1). Так как 1 < 3, в массив с нужно занести 1 и перейти к следующему элементу части b, то есть увеличить j на 1 (значение j станет равно m + 2), а также увеличить на 1 значение g (значение g будет равно 2).

2 - й шаг: теперь нужно сравнить а [ k + 1 ] = 3 и b [ m + 2 ] = 5. 3 < 5, следовательно, на второе место в с надо занести а [ k + 1 ] = 3. Затем нужно увеличить на одно значение i и g.

3 - й шаг: на третье место массива с претендуют два одинаковых элемента - а [ k + 2 ] = 5 и b [ m + 2 ] = 5. В этом и подобных случаях договоримся заносить в с первым элемент из части а. Таким образом, с [ 3 ] = а [ k + 2 ], а значение

g = 4, i = k + 3, j остается равным m + 2.

4-11 - й шаги: рассуждая аналогичным образом, нужно занести в с элементы 5, 7, 8, 9, 11, 12, 13, 16.

После выполнения 11 - го шага первая часть будет занесена в с полностью, значение g равно m + 7, значение g = 12.

12 - й шаг: так как часть а закончилась, а “хвост” части b упорядочен по условию, то двенадцатым элементом массива с будет первый элемент “хвоста” b, то есть b [ m + 7 ] = 18.

13 - й шаг: последним элементом массива с будет последний элемент b – 20.

На рисунке схематично изображен процесс заполнения массива c.

часть a

... 3 5 8 11 16...

шаг 2 шаг 3 шаг 6 шаг 8 шаг 11

3>6 5=5 8<9 11<12 16<19

C

1

шаг 1 шаг 4 шаг 5 шаг 7 шаг 9 шаг 10 шаг 12

1<3 5<8 7<8 9<11 12<16 13<16

... часть b

Сейчас можем описать процедуру слияния двух упорядоченных массивов размерностей m-k и n-m соответственно в третий упорядоченный массив, размерности n-k.

Procedure sorting4(k,m,n:integer);

var i,j:integer;

begin

i:=k+1;

j:=m+1;

k:=1;

while (i<=m) and (j<=n) do

{пока не закончилась хотя бы одна часть}

begin

if a[i]<=b[j] then

begin c[k]:=a[i]; inc(i); end

else begin c[k]:=b[j]; inc(j); end;

inc(k);

end;

{один из массивов - частей обработан полностью}

{осталось перенести в с остаток другого массива - части}

while i<=m do

begin c[k]:=a[i]; inc(i); inc(k); end;

while j<=n do

begin c[k]:=b[j]; inc(j); inc(k); end;

end;

Приведем пример программы, использующий эту процедуру в некоторой переработке (вместо a[k+1],..., a[m] используем a[1..k], а вместо a[m+1],..., a[n] используем b[1..m], где k+m = n). Эта программа делит исходный массив на две части, затем каждая часть сортируется методом “пузырьковой” сортировки, после чего части соединяются с помощью данной процедуры в искомый массив. Очевидно, скорость такого метода выше, чем просто использование “пузырьковой ” сортировки.

program n4;

const n=5;

type ar=array[1..n] of integer;

var k,m,i:integer;

a,b,c:ar;

Procedure sorting4;

var s,i,j:integer;

begin

i:=1;

j:=1;

s:=1;

while (i<=k) and (j<=m) do

{пока не закончилась хотя бы одна часть}

begin

if a[i]<=b[i] then

begin c[s]:=a[i]; inc(i); end

else begin c[s]:=b[j]; inc(j); end;

inc(s);

end;

{один из массивов - частей обработан полностью}

{осталость перенести в с остаток другого массива - части}

while i<=k do

begin c[s]:=a[i]; inc(i); inc(s); end;

while j<=m do

begin c[s]:=b[j]; inc(j); inc(s); end;

end;

procedure sorting2(var p:ar;len:integer);

var f,i,t:integer;

{f - номер просмотра (изменяется от 1 до n-1)

i - номер рассматриваемой пары

t - промежуточная переменная для перестановки местами элементов}

begin

for f:=1 to len-1 do

{цикл по номеру просмотра}

for i:=1 to len-f do

if p[i]>p[i+1] then

{перестановка элементов}

begin

t:=p[i];

p[i]:=p[i+1];

p[i+1]:=t;

end;

end;

begin

k:=n div 2;

m:=n-k;

writeln('Введите исходный массив:');

for i:=1 to n do read(c[i]);

for i:=1 to k do a[i]:=c[i];

for i:=1 to m do b[i]:=c[k+i];

sorting2(a,k);

sorting2(b,m);

sorting4;

writeln('Отсортированный массив:');

for i:=1 to n do write(c[i],' ');

writeln;

end.

Обменная сортировка с разделением (сортировка Хоара)

Сортировка методом простого обмена (методом “пузырька”) является в среднем самой неэффективной. Это обусловлено самой идеей метода, который требует в процессе сортировки сравнивать и обменивать между собой только соседние элементы. Можно существенно улучшить метод сортировки, основанный на обмене. Это улучшение приводит к самому лучшему на сегодняшний день методу сортировки массивов, который можно назвать обменной сортировкой с разделением. Он основан на сравнениях и обменах элементов, стоящих на возможно больших расстояниях друг от друга. Предложил этот метод Ч. А. Р. Хоар в 1962 году. Поскольку производительность этого метода впечатляюща, автор назвал его “быстрой сортировкой”.

Идея метода

1. В исходном неотсортированном массиве выбрать некоторый элемент x (барьерный элемент).

2. Переставить элементы массива таким образом, что слева от x оказались элементы массива, меньшие или равные x, а справа - элементы массива, большие x.

Пусть при этом элемент x попадет в позицию k, тогда массив будет иметь вид: (a[1], a[2],..., a[k-1]), a[k], (a[k+1],..., a[n]).

Каждый из элементов a[1], a[2],..., a[k-1] меньше либо равен a[k], каждый из элементов a[k+1],..., a[n] больше a[k]. Отсюда можно сделать вывод, что элемент a[k] стоит на своем месте. А исходный массив при этом разделится на две неотсортированные части, барьером между которыми является элемент a[k].

Для дальнейшей сортировки необходимо применить пункты 1 и 2 для каждой из этих частей. И так до тех пор, пока не останутся подмассивы, состоящие из одного элемента, то есть пока не будет отсортирован весь массив.

Рассмотрим применение метода “быстрой сортировки” на примере.

Исходный массив состоит из 8 элементов:

8 12 3 7 19 11 4 16

В качестве барьерного элемента будем брать средний элемент массива.

Барьерный элемент - 7. Произведя необходимые перестановки для разделения, получим: (4 3) 7 (12 19 11 8 16)

Теперь элемент со значением 7 стоит на своем месте. Далее сортируем подмассивы, элементы которых заключены в скобки. Этот процесс будем повторять до тех пор, пока не получим полностью отсортированный массив.

Левый подмассив: (3) 4 7 (12 19 11 8 16)

3 4 7 (12 19 11 8 16)

Правый подмассив: 3 4 7 (8) 11 (19 12 16)

3 4 7 8 11 (19 12 16)

3 4 7 8 11 12 (19 16)

3 4 7 8 11 12 (16) 19

3 4 7 8 11 12 16 19

Массив отсортирован полностью.

Алгоритм “быстрой сортировки” можно определить как рекурсивную процедуру, параметрами которой являются нижняя и верхняя границы изменения индексов сортируемой части исходного массива:

program n5;var a: array[1..10] of integer;procedure Init;

{формирование массива из фала}

var f: text;

i: integer;

begin

Assign(f,'g:\s.dat');

Reset(f);

for i:=1 to 10 do read(f,a[i]);

close(f);

end;

procedure Print; {печать массива}

var i: integer;

begin

for i:=1 to 10 do write(a[i]:5);

writeln;

end;

procedure Quik_sorting(m,l: integer);

var i,j,x,w: integer;

begin

i:=m;

j:=l;

x:=a[(m+l) div 2];

repeat

while a[i]<x do inc(i);

while a[j]>x do dec(j);

if i<=j then

begin

w:=a[i]; a[i]:=a[j]; a[j]:=w;

inc(i);

dec(j);

end;

until i>j;

if m<j then Quik_sorting(m,j);

if i<l then Quik_sorting(i,l);

end;

begin {основная программа}

writeln('Массив:');

init;

print;

Quik_sorting(1,10);

writeln('отсортированный массив');

print;

end.

Дата добавления: 2014-11-09