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

Сортування злиттям, як правило, застосовуються в тих випадках, коли вимагається відсортувати послідовний файл, що не вміщауться в основній пам'яті.

Нехай є два відсортованих у порядку зростання масиви р[1], р[2],...,р[n] і q[1],q[2],..., q[n] і є порожній масив r[1], r[2],..., r[2*n], який ми хочемо заповнити значеннями масивів p і q у порядку зростання. Для злиття виконуються такі дії: порівнюються р[1] і q [1], і менше зі значень записується в r[1]. Припустимо, що це значення р[1 ]. Тоді р[2] порівнюється з q[1], і менше із значень записується в r[2]. Припустимо, що це значення q[1]. Тоді на наступному кроці порівнюються значення р[2] і q[2] і т.ін., поки ми не досягнемо меж одного з масивів. Тоді залишок іншого масиву просто дописувається в ≪хвіст≫ масиву r.

Алгоритм сортуванням злиттям подано на рисунку 33.

Для випадку масиву, що використовується в наших прикладах, послідовність кроків показана в таблиці 9.

При застосуванні сортування зі злиттям кількість порівнянь ключів і кількість пересилань оцінюється як Θ (n*log n). Але слід врахо-вувати, що для виконання алгоритму для сортування масиву розміру n потрібно 2n елементів пам'яті.

Таблиця 9 – Приклад сортування злиттям.

Початковий стан масиву	8 23 5 65 44 33 1 6
Крок 1	6 8 1 23 5 33 44 65
Крок 2	6 8 44 65 1 5 23 33
Крок 3	1 5 6 8 23 33 44 65

Рисунок 33 – Блок-схема методу сортування злиттям.

Void sort_bin()

{

int i,j,k=0,l=0;int t=(int)n/2+n%2;

int resCmp=0;

student a1[30],a2[30],tmp;

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

{

if(i<(int)n/2)

a1[i]=a[i];

else

a2[i-(int)n/2]=a[i];

}

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

for(j=0;j<(int)n/2-1;j++)

{

if(a1[i]>a1[j+1])

{

tmp=a1[j];

a1[j]=a1[j+1];

a1[j+1]=tmp;

}

}

for(i=0;i<(int)n/2+n%2;i++)

for(j=0;j<(int)n/2+n%2-1;j++)

{

if(a2[j]>a2[j+1])

{

tmp=a2[j];

a2[j]=a2[j+1];

a2[j+1]=tmp;

}

}

i=0;

while(i<n)

{

if ((k= =(int)n/2)&&(l!=t))

{

a[i]=a2[l];

i++;l++;continue;

}

if ((k!=(int)n/2)&&(l==t))

{

а[і]=а1[k];

i++;k++;continue;

}

if(a2[l]>a1[k])

{

а[і]=а1[k];

i++;k++;continue;

}

if(a1[k]>a2[l])

{

a[i]=a2[l];

i++;l++; continue;

}

if(a1[k]==a2[l])

{

a[i]=a1[k];

i++;k++;

a[i]=a2[l];

i++;l++; continue;

}

}

Контрольні питання

ЛЕКЦІЯ № 8

Тема: Алгоритми сортування: методи зовнішнього сортування

Ціль: розглянути методи зовнішнього сортування та їх застосування

План