• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Багатофазне сортування

Збалансоване багатошляхове злиття

Природне злиття

Пряме злиття

План

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

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

Нехай є два відсортованих у порядку зростання масиви р[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 – Приклад сортування злиттям.

Рисунок 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

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

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

Прийнято називати ≪зовнішнім≫ сортування послідовних файлів, розташованих у зовнішній пам'яті і дуже великих, щоб можна було повністю перемістити їх в основну пам'ять і застосувати один з розглянутих у попередньому розділі методів внутрішнього сортування. Найчастіше зовнішнє сортування застосовується в системах керування базами даних при виконанні запитів, і від ефективності вживаних методів істотно залежить продуктивність СУБД.

Мусимо пояснити, чому йдеться саме про послідовні файли, тобто про файли, які можна читати запис за записом в послідовному режимі, а писати можна тільки після останнього запису. Методи зовнішнього сортування з'явилися, коли найбільш поширеними пристроями зовнішньої пам'яті були магнітні стрічки. Для стрічок послідовний доступ був абсолютно природним. Коли відбувся перехід до пристроїв, що запам'ятовують, з магнітними дисками, що забезпечують ≪прямий≫ доступ до будь-якого блоку інформації, здавалося, що послідовні файли втратили свою актуальність.Проте це припущення було помилковим.

Вся річ у тому, що практично всі використовувані на сьогодні дискові пристрої забезпечені рухомими магнітними головками. При виконанні обміну з дисковим накопичувачем виконується підведення головок до потрібного циліндра, вибір потрібної головки (доріжки), прокручування дискового пакету до початку необхідного блоку і,нарешті, читання або запис блоку. Серед всіх цих дій найбільший час займає підведення головок. Саме цей час визначає загальний час виконання операції. Єдиним доступним прийомом оптимізації доступу до магнітних дисків є якомога ≪ближче≫ розташування файла на накопичувачіблоків, що послідовно адресуються. Але і в цьому випадку рух головок буде мінімізованим у тому випадку, коли файл читається або пишеться в послідовному режимі. Саме з такими файлами при потребі сортування працюють сучасні СУБД.

Зазначимо, що насправді швидкість виконання зовнішнього сортування залежить від розміру буферу (або буферів) основної пам'яті, яка може бути використана для цих цілей.

Читайте також:

1. Багатофазне сортування
2. Контроль-сортування (дефектація).
3. Медичне сортування та медична евакуація при НС
4. МЕДИЧНЕ СОРТУВАННЯ.
5. Порозрядне сортування для списків.
6. Сортування
7. Сортування - це процес, який дозволяє впорядкувати множину подібних даних у порядку зростання або убування.
8. Сортування вибором
9. Сортування вибором
10. Сортування вибором.
11. Сортування включеннями

Переглядів: 2529