вихідне положення: d c a b;
перший прохід: c d a b;
другий прохід: a c d b;
третій прохід: a b c d.
Нижче приводиться алгоритм сортування включенням:
{ сортування включенням }
procedure Inser(var item: DataArray; count:integer);
var
i, l: integer;
x: DataItem;
begin
for i := 2 to count do
begin
x := item[i];
j := i-1;
while (x<item[j]) and (j>0) do
begin
item[j+1] := item[j];
j := j-1;
end;
item[j+1] := x;
end;
end; { кінець сортування включенням }
На відміну від сортування бульбашковим методом і сортування вибором число операцій порівняння для сортування включенням залежить від вихідної упорядкованості масиву елементів. Якщо вихідний масив вже упорядкований, то число операцій порівняння дорівнює n-1.
Якщо масив упорядкований у зворотному порядку, то число операцій порівняння дорівнює 1/2 (n2 +n)-1, даючи в середньому значення 1/4 (n2+n-2).
Число операцій обміну буде наступним:
для кращого випадку: 2 (n-1);
у середньому: 1/4 (n2+9n-10);
для гіршого випадку: 1/2 (n2+3n-4).
Таким чином, число операцій обміну для гіршого випадку буде настільки ж великим, як і для сортувань бульбашковим методом і сортувань вибором. Число операцій обміну для середнього випадку буде лише на небагато менше. Однак сортування включенням має дві переваги. По-перше, вона має природне поводження, тобто вона виконується швидше для упорядкованого масиву і довше всего виконується, коли масив упорядкований у зворотному напрямку. Це робить сортування включенням корисної для упорядкування майже відсортованих масивів. По-друге, елементи з однаковими ключами не переставляються: якщо список елементів сортується з використанням двох ключів, те після завершення сортування включенням він як і раніше буде упорядкований по двох ключах.
Незважаючи на те, що число порівнянь може бути досить невеликим для визначених наборів даних, постійні зрушення масиву вимагають виконання великого числа операцій пересилань.
Однак, сортування включенням має природне поводження, вимагаючи найменше число операцій обміну для майже упорядкованого списку і найбільше число операцій обміну, коли масив упорядкований у зворотному напрямку.
В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву.
Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається – тоді решта іншої колони додається до нової.
Нехай у масиві Y з елемента Y[m] починається впорядкована ділянка довжиною s, а з елемента Y[m+s] – впорядкована ділянка довжини r. Наприклад,
| Y | … | 1 | 3 | … | 13 | 2 | 4 | … | 88 |
| … | m | m+1 | m+s-1 | m+s | m+s+1 | … | m+s+r |
Результатом злиття повинна бути ділянка довжини r+s у масиві X:
| X | … | 1 | 2 | 3 | 4 | … | 13 | … | 88 |
| … | m | m+1 | m+2 | m+3 | … | m+s+r |
Таке злиття двох ділянок у масиві Y у ділянку масиву X задає процедура
procedure mrg( var Y : ArT; m, s, r : Indx; var X : ArT);
var mr, k : Indx; i, j : Extind;
begin
mr := m + s; { mr – початок правої частини }
i := m; j := mr; { i та j пробігають ліву й праву ділянки масиву Y}
for k := m to m + s + r - 1 do{заповнення X[m], … , X[m+s+r-1]}
if i > m + s - 1 then
begin X[k] := Y[j]; j := j + 1 end else
if j > mr + r - 1 then
begin X[k] := Y[i]; i := i + 1 end else
if Y[i] < Y[j] then
begin X[k] := Y[i]; i := i + 1 end else
begin X[k] := Y[j]; j := j + 1 end
end
Тепер розглянемо сортування масиву A злиттям. На першому кроці елементи A[1], … , A[n] копіюються в допоміжний масив B[1], … , B[n]. Його елементи розглядаються парами B[1] і B[2], B[3] і B[4] тощо як упорядковані послідовності довжиною lp = 1 і зливаються за допомогою процедури mrg в масив A. Тепер там є впорядковані ділянки довжиною 2. За непарного n останній елемент A[n] залишається без змін як послідовність довжиною 1.
На наступному кроці після копіювання в масив B зливаються пари упорядкованих ділянок B[1]B[2] і B[3]B[4], B[5]B[6] і B[7]B[8] тощо. З'являються впорядковані ділянки довжиною 4. Нехай t=nmod4 – довжина залишку масиву після останньої повної четвірки елементів. При t=1 або t=2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t=3 зливаються упорядкована пара B[n-1]B[n-2] та ділянка B[n] у ділянку довжиною t.
Кроки повторюються з подвоєнням довжин упорядкованих ділянок lp, поки lp < n.
Розглянемо сортування злиттям масиву <11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> довжини n=11. Упорядковані послідовності в ньому вказуються в дужках <>, а пари таких, що зливаються, відокремлені ";":
< <11><10> ; <9><8> ; <7><6> ; <5><4> ; <3><2> ; <1> >, lp=1
< <10, 11><8, 9> ; <6, 7><4, 5> ; <2, 3><1> >, lp=2
< <8, 9, 10, 11><4, 5, 6, 7>;<1, 2, 3> >, lp=4
< <4, 5, 6, 7, 8, 9, 10, 11><1, 2, 3> >, lp=8
<1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11>, lp=16, lp n.
Як бачимо, нам знадобилося 4 кроки злиття для того, щоб одержати впорядований масив.
Такий спосіб сортування описується процедурою Mrgsort:
procedure Mrgsort (var A : ArT; n : Indx);
var B : ArT; lp, npp, cpp, bpp, tl : integer;
begin
lp := 1;
while lp < n do
begin
B := A; { копіювання }
npp := n div (2*lp); { кількість пар ділянок }
tl := n mod (2*lp); { довжина залишку }
for cpp := 1 to npp do { cpp – номер пари }
begin
bpp := (cpp - 1)*2*lp + 1;
{ індекс першого елемента лівої ділянки пари}
mrg ( B, bpp, lp, lp, A );
end;
{ обробка залишку }
if tl > lp then
mrg ( B, n - tl + 1, lp, tl - lp, A );
{ за tl <= lp залишок був упорядкований }
{ на попередньому кроці }
lp := lp*2
end
{ lp >= n : масив упорядковано на останньому кроці }
end
Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2k. Якщо 2k=n, то масив упорядковано. Якщо 2k>n, але 2k-1<n, то при виконанні останнього кроку мають місце співвідношення
lp = 2k-1 = 2k / 2 > n/2, npp = 0, tl = n > lp,
і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив.
Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k<2n, тобто k<1+logn, і це означає, що тіло циклу while виконується 1+ log2n =O(logn) разів. Отже, складність алгоритму оцінюється як O(nlogn).
Запишемо в таблицю значення виразів n, n(n-1)/2, n(1+log2n ) та округлене відношення r двох останніх:
| n | n(n-1)/2 | n(1+ log2n ) | r |
| 10 | 45 | 40 | 1 |
| 100 | 4950 | 700 | 7 |
| 1000 | 499500 | 10000 | 50 |
| 10000 | 49995000 | 140000 | 350 |
Як бачимо, кожне зростання n у 10 разів веде до зростання n(n-1)/2 та n(1+log2n) приблизно в 100 й 14 разів відповідно, і за n=10000 сортування злиттям виконується в сотні разів скоріше, ніж бульбашкове!
Зауважимо, що в наведеному алгоритмі сортування злиттям копіювання масиву в допоміжний указано лише для того, щоб ідею алгоритму було простіше сприйняти. Цей алгоритм нескладно переробити так, щоб замість копіювання в додатковий масив відбувалося злиття в нього упорядкованих ділянок. Отже, на кроках з номерами 1, 3, 5, … має відбуватися злиття в допоміжний масив, а на кроках 2, 4, 6, … – злиття в протилежному напрямку. Переробка алгоритму залишається вправою.
Сортування злиттям можна задати рекурсивно: масив поділяється на дві приблизно рівні частини, які після сортування (тим самим способом – ось рекурсія!) зливаються. Коли ж довжина частини масиву зменшується до 1, відбувається просто повернення з рекурсії. Цей алгоритм уточнюється наступною процедурою Mrgrec. На відміну від процедури Merges, вона має два параметри-масиви (той, що сортується, та допоміжний), а також два числові параметри (початок і кінець частини масиву, яка сортується). Крім того, спочатку відбувається злиття ділянок основного масиву в допоміжний, а потім копіювання в основний:
procedure Mrgrec(var A, B : ArT; l, r : integer);
var m, k : integer;
begin
if l>=r then exit;
m:=(l+r) div 2;
Mrgrec(A, B, l, m); Mrgrec(A, B, m+1,r);
mrg(A, l, m-l+1, r-m, B);
for k:=l to r do A[k]:=B[k];
end;
Ця процедура набагато коротше нерекурсивної процедури Merges, але виконання її довше. Власне сортування починається лише після повернення з викликів, у яких l=r, а це практично "середина дистанції".
Завершуючи описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування.
Серйозним недоліком цього алгоритму є необхідність додаткового масиву такої ж довжини, як і в основного. За великих довжин можлива ситуація, коли на один масив пам'яті вистачає, а на два – ні.
1.9 Удосконалені алгоритми сортування. Сортування Шелла
Усі розглянуті дотепер алгоритми сортування мають дуже серйозний недолік, а саме, час їхнього виконання пропорційно квадратові числа елементів.
Для великих обсягів даних ці сортування будуть повільними, а починаючи з деякої величини, вони будуть занадто повільними, щоб їх можна було використовувати на практиці. Кожен програміст чув або розповідав "страшні" історії про "сортування, що виконувалася три дні". На жаль, ці історії часто не були вигадкою.
Якщо сортування виконується занадто довго, то причиною цього може бути використовуваний алгоритм. Розглянемо два дуже гарні сортування. Перше зветься сортування Шелла, а друге називається швидким сортуванням, алгоритм якого визнаний найкращим. Ці сортування виконуються дуже швидко.
Сортування Шелла одержав свою назву по імені його творця Д.Л.Шелла. Однак, цю назву можна вважати вдалою, тому що виконувані при сортуванні дії нагадують укладення морських черепашок одну на одну.