Головна |
При використанні методу прямого злиття не береться до уваги те, що початковий файл може бути частково відсортованим, тобто містити впорядковані підпослідовності записів.
Серією називається підпослідовність записів аі, а(i+1), ..., aj така, що ak<=a(k+1) для всіх i<= k<j, аі < а(і-1) і aj>a(j+1). Метод природного злиття ґрунтується на розпізнаванні серій при розподілі і їх використанні при подальшому злитті.
Як і у разі прямого злиття, сортування виконується за декілька кроків, в кожному з яких спочатку виконується розподіл файла А по файлам В і С, а потім злиття В і С у файл А. При розподілі розпізнається перша серія записів і переписується у файл В, друга - у файл С і т.ін. При злитті перша серія записів файлу В зливається з першою серією файлу С, друга серія В з другою серією С і т.ін. Якщо перегляд одного файлу закінчується раніше, ніж перегляд іншого (внаслідок різної кількості серій), то залишок не до кінця переглянутого файла повністю копіюється в кінець файла А. Процес завершується, коли у файлі А залишається тільки одна серія. Приклад сортування файла показаний на рисунках 34 і 35.
Рисунок 34 - Зовнішнє пряме сортування злиттям. Перший крок.
Рисунок 35 - Зовнішнє пряме сортування злиттям. Другий крок.
Очевидно, що кількість зчитувань/перезаписів файлів при використанні цього методу буде не більша, ніж при застосуванні методу прямого злиття, а в середньому - менша. З другого боку, збільшується кількість порівнянь за рахунок тих, які потрібні для розпізнавання кінців серій. Крім того, оскільки довжина серій може бути довільною, то максимальний розмір файлів В і С може бути близький до розміру файла А.
Алгоритм проходження графу вшир | Методи обчислення адреси | Методи обчислення адреси | Сортування злиттям | Метод простого включення | Метод Шелла | Сортування вибором | Сортування за допомогою дерева | Сортування злиттям | Багатофазне сортування |