UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75850
останнє поновлення: 2016-12-08
за 7 днів додано 17

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваЗбалансоване злиття (реферат)
Автор
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось1185
Скачало189
Опис
ЗАКАЧКА
Замовити оригінальну роботу

ЗНАЙОМСТВО З СОРТУВАННЯМ ФАЙЛІВ (на прикладі мови Паскаль)

 

1. Збалансоване злиття

 

У попередньому розділі ми розглядали сортування послідовностей, поданих

масивами. Але в реальних задачах виникають послідовності, що

зберігаються в файлах і не можуть уміщатися в оперативній пам'яті у

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

абонентів телефонної мережі. Звичайно, для швидкого пошуку дані про

абонентів мають бути відсортованими. Виникає задача сортування файлів за

умови, що файли цілком не можна подавати в оперативній пам'яті. Таке

сортування називається зовнішнім.

 

Один із найпростіших методів зовнішнього сортування має назву

збалансованого злиття. Розглянемо його ідею.

 

Нехай F1 є файлом однотипних значень. Відрізком у ньому називається

послідовність елементів, упоpядкована за зростанням значень, яка не є

частиною іншої упорядкованої послідовності. Наприклад, у послідовності

<2, 8, 3, 7, 6, 5, 3, 4, 1> є шість відрізків: <2, 8>, <3, 7>, <6>, <5>,

<3, 4>, <1>.

 

Спочатку відpізки по черзі копіюються в допоміжні файли F3 і F4. Це

первинне копіювання називається розподілом. У нашому прикладі маємо <2,

8, 6, 3, 4> в F3 і <3, 7, 5, 1> в F4.

 

Потім паpи перших, других тощо відpізків файлів F3 і F4 зливаються в

довші відpізки та по черзі копіюються в F1 і допоміжний файл F2. У

нашому прикладі маємо <2, 3, 7, 8, 1, 3, 4> в F1 та <5, 6> в F2. Цей

крок називається злиттям. Потім паpи відpізків файлів F1 і F2 зливаються

у файли F3 і F4 тощо доти, поки в результаті чергового злиття не

утвориться єдиний відрізок.

 

Якщо перед черговим кроком злиття було M відрізків, то після нього їх

стає не більше, ніж ? (M+1)/2? . Звідси випливає, що таких кроків не

більше ? log2N? , де N – кількість елементів файла. Оскільки на кожному

кроці злиття відбувається переписування всіх N елементів у інші файли,

то складність такого алгоритму сортування можна оцінити як O(Nlog2N).

 

Можна збільшити кількість допоміжних файлів. Наприклад, якщо зливати не

дві, а три послідовності, то кількість відрізків буде зменшуватися не

менше, ніж утричі, тому кроків злиття буде не більше ? log3N? , що в

log23, тобто приблизно в півтора раза менше. Для цього будуть потрібні 5

допоміжних файлів.

 

Взагалі, використання 2k-1 допоміжних файлів вимагатиме не більше ?

logkN? кроків злиття. Отже, "розширення фронту" злиття є одним із джерел

прискорення сортування.

 

З іншого боку, чим довшими будуть відрізки в початковому файлі, тим

менше кроків злиття буде потрібно. Звідси створення початкового файла з

якомога довшими відрізками також може суттєво прискорити сортування.

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

 

2. Вибір із заміщенням

 

Тут ми опишемо створення файла з якомога довшими відрізками.

Скористаємося методом, що належить Сьюворду та Думі, із удосконаленням

Фрейзера та Уона (посилання див. у книзі [Кн3]). Цей метод грунтується

на використанні дерева сортування.

 

Нехай початковий файл містить значення упорядкованого типу T. За цим

файлом будується результатний файл із неспадаючими відрізками. При

-----> Page:

0 [1] [2] [3]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ