Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

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

В основі методу зовнішнього сортування збалансованим багатошляховим злиттям є розподіл серій початкового файлу по m допоміжних файлів В1, В2, …, Вm і їх злиття в m допоміжних файлів С1, С2, …, Сm. На наступному кроці здійснюється злиття файлів С1, С2, …, Сm у файли В1, В2, …, Вm і т.ін., поки в В1 або С1 не утворюється одна серія.

Багатошляхове злиття є природним розвитком ідеї звичного (двошляхового) злиття, ілюстрованого а рисунку 35. Приклад тришляхового злиття показан на рисунку 36.

На рисунку 37 показаний простий приклад застосування сортування багатошляховим (багатофазним) злиттям.

Рисунок 36 – а) Тришляхове злиття. Початок.

Рисунок 36 – б) Тришляхове злиття. Закінчення.

Рисунок 37 – Багатофазне злиття.

Він, зазвичай, дуже тривіальний, щоб продемонструвати декілька кроків виконання алгоритму, проте достатній як ілюстрація загальної ідеї методу. Як показує цей приклад, у міру збільшення довжини серій допоміжні файли з великими номерами (починаючи з номера n) перестають використовуватися, оскільки їм ≪не дістається≫ жодної серії. Перевагою сортування збалансованим багатофазним злиттям є те, що кількість проходжень алгоритму оцінюється як Θ (log n) (n – кількість записів у початковому файлі), де логарифм береться по n. Порядок кількості копіювань записів - (log n). Зазвичай, кількість порівнянь не буде меншою, ніж при застосуванні методу простого злиття.

При використанні розглянутого вище методу збалансованого багатошляхового зовнішнього сортування на кожному кроці приблизно половина допоміжних файлів використовується для введення даних і приблизно стільки ж для виведення злитих серій. Ідея багатофазного сортування полягає у тому, що з наявних m допоміжних файлів (m-1) файл служить для введення злитих послідовностей, а один – для виведення утворених серій. Як тільки один з файлів введення стає порожнім, його починають використовувати для виведення серій, одержуваних при злитті серій нового набору (m-1) файлів. Отже є перший крок, при якому серії початкового файлу розподіляються по m-1 допоміжному файлу, а потім виконується багатошляхове злиття серій з (m-1) файлу, поки в одному з них не утвориться одна серія.

Очевидно, що при довільному початковому розподілі серій по допоміжним файлам алгоритм може не зійтися, оскільки в одному непорожньому файлі існуватиме більше, ніж одна серія. Припустимо, наприклад, що використовується три файли В1, В2 і В3, і при початковому розподілі у файл В1 вміщені 10 серій, а у файл В2 – 6. При злитті В1 і В2 до моменту, коли ми дійдемо до кінця В2, в В1 залишаться 4 серії, а у В3 потраплять 6 серій. Продовжиться злиття В1 і В3, і при завершенні перегляду В1 у В2 містимуться 4 серії, а у В3 залишаться 2 серії. Після злиття В2 і В3 в кожному із файлів В1 і В2 міститиметься по 2 серії, які зіллються і утворять 2 серії в В3 при тому, що В1 і В2 – порожні. Отже, алгоритм не зійшовся (таблиця 11).

Таблиця 11 – Приклад початкового розподілу серій, при якому трифазне зовнішнє сортування не приводить до потребного результату

К-ть серій у файлі В1	К-ть серій у файлі В2	К-ть серій у файлі В3

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

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

1. Поясніть особливості внутрішніх та зовнішніх методів сортування.

2. Назвіть методи внутрішнього сортування

3. Назвіть методи зовнішнього сортування.

4. Визначте алгоритмічну складність сортування методом Хоара.

5. Визначте алгоритмічну складінсть пірамідального сортування.

Тести для закріплення матеріалу

1. Назвати складові частини алгоритмів сортування

а) порівняння, що визначає впорядкованість пари елементів;

б) перестановка, що змінює місцями пари елементів;

в) пошук, який ставить найбільший елемент на початок;

г) власне алгоритм сортування, що здійснює порівняння і перестановку елементів доти, поки всі елементи множини не будуть впорядковані.

2. Перерахуйте методи внутрішнього сортування

а) включенням;

б) Шелла;

в) обмінне;

г) природне злиття;

д) багатофазне злиття;

е) пірамідальне;

є) вибором;

ж) поділом;

з) сортування деревом.

3. Перерахуйте методи зовнішнього сортування

а) включенням;

б) Шелла;

в) обмінне;

г) природне злиття;

д) багатофазне злиття;

е) пірамідальне;

є) вибором;

ж) поділом;

з) сортування деревом.

4. За фраґментом програми визначте метод сортування

for(i=1,i<=n-1;i++)

for(j=i+1 ;<=n;j++)

if(a[i]<a[j])

{

b=a[i];

a[i]=a[j];

a[j]=b;

}

а) бульбашки;

б) включення;

в) Шелла:

г) поділу.

5. За фраґментом програми визначте метод сортування

for(i=1,i<=n;i++)

for(j=i ;<=n-1;j++)

if(a[i]<a[i+1])

{

b=a[i];

a[i]=a[i+1];

a[i+1]=b;

}

а) бульбашки;

б) включення:

в) Шелла;

г) поділу.

6. За фраґментом програми визначте її призначення

Type tree=^tr;

Tr=record;

k:integer; s:string; l,r:tree; end;

function mmm(k:integer;var d,res:tree):boolean;

var p,q:tree; b:boolean;

begin b:=false; p:=d;

if d<>nil then repeat q:=p; if р^.k=k then b:=true

else begin q:=p; if k<р^.k then р:=р^.l else p:=p^.r

end

until b or (p=nil); mmm:=b; res:=q;end;

а) видалення елемента з списку;

б) видалення елемента в дереві;

в) пошук елемента в списку;

г) пошук елемента в дереві.'

7. За фраґментом програми визначте метод сортування:

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

if(i<(int)n/2)

а1[і]=а[і];

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[j]<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]; a[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))

{a[i]=a1[k]; i++;k++;continue;}

if(a2[j]<a1[k])

{a[i]=a1[k]; i++;k++;continue;}

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

{a[i]=a2[l]; i++;l++;continue;}

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

{a[i]=a1[k]; i++;k++; a[i]=a2[l]; i++; l++; continue;}

}

а) бінарний;

б) включення;

в) Шелла;

г) пірамідальний.

8. За фраґментом програми визначте метод сортування:

while (j<znach-1)

{

for (i=0;i<znach-1;i++)

if (strcmp(mas[i],mas[i+1])>0)

{

pidmin=mas[i];

mas[i]=mas[i+1];

mas[i+1]=pidmin;

}

j++;

}

а) бінарний;

б) включення;

в) Шелла;

г) поділу.

9. За фраґмєнтом програми визначте метод сортування:

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

k[i]=0;

for(i=0; i<rowArr-1; i++)

{

for (j=i+1; j<rowArr; j++)

{

if (ar_s[i]<ar_s[j])

{

k[i]++;

}

else k[j]++;

}

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

ar_s1[k[i]]=ar_s[i];

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

ar_s[i]=ar_s1[i];

а) включення;

б) Шелла;

в) поділу;

г) підрахунку.

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

ЛЕКЦІЯ № 9

Тема: Класичні задачі комбінаторіки

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Природне злиття	\|

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.01 сек.