ПОШУК, СОРТУВАННЯ ТА ПОНЯТТЯ СКЛАДНОСТІ У ПРОГРАМУВАННІ

Складність алгоритму повинна бути якомога меншою.

4. Ефективні алгоритми сортування

4.1. Сортування злиттям

В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву.

Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається – тоді решта іншої колони додається до нової.

Нехай у масиві Y з елемента Y[m] починається впорядкована ділянка довжиною s, а з елемента Y[m+s] – впорядкована ділянка довжини r. Наприклад,

Y…13…1324…88

…mm+1 m+s-1m+sm+s+1…m+s+r

Результатом злиття повинна бути ділянка довжини r+s у масиві X:

X…1234…13…88

…mm+1m+2m+3 … m+s+r

За дії означень (17.1) таке злиття двох ділянок у масиві 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