![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Сортування злиттям, як правило, застосовуються в тих випадках, коли вимагається відсортувати послідовний файл, що не вміщауться в основній пам'яті.
Нехай є два відсортованих у порядку зростання масиви р[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
Тема: Алгоритми сортування: методи зовнішнього сортування
Ціль: розглянути методи зовнішнього сортування та їх застосування
План
Дата публикования: 2014-11-26; Прочитано: 2139 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!