|
|
Збалансоване багатошляхове злиття
В основі методу зовнішнього сортування збалансованим багатошляховим злиттям є розподіл серій початкового файлу по 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. Назвіть методи зовнішнього сортування. 4. Визначте алгоритмічну складність сортування методом Хоара. 5. Визначте алгоритмічну складінсть пірамідального сортування.
  ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...  ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...  Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
