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