Сортування природним злиттям
У разі простого злиття часткова впорядкованість даних, що сортуються, не дає жодної переваги. Це тим, що у кожному проході зливаються серії фіксованої довжини. При природному злитті довжина серій не обмежується, а визначається кількістю елементів у вже впорядкованих підпослідовності, що виділяються на кожному проході.
Сортування, при якому завжди зливаються дві найдовші з можливих послідовностей, є природним злиттям. У цьому сортуванні об'єднуються серії максимальної довжини.
Алгоритм сортування природним злиттям
Крок 1. Вихідний файл f розбивається на два допоміжні файли f1 і f2. Розподіл відбувається так: по черзі зчитуються записи ai вихідної послідовності (невпорядкованої) таким чином, що якщо значення ключів сусідніх записів задовольняють умові f(ai) f(ai+1), то записи ai+1 копіюються до другого допоміжного файлу f2. Процедура повторюється до тих пір, поки всі записи вихідної послідовності не будуть розподілені файлами.
Крок 2. Допоміжні файли f1 і f2 зливаються до файлу f, при цьому серії утворюють упорядковані послідовності.
Крок 3. Отриманий файл f знову обробляється, як зазначено у кроках 1 та 2.
Крок 4. Повторюючи кроки, зливаємо впорядковані серії до того часу, поки повністю впорядкований весь файл.
Символ "`" означає ознаку кінця серії.
Ознаками кінця сортування природним злиттям є такі умови:
- кількість серій дорівнює 1 (визначається на фазі злиття).
- при однофазному сортуванні другий за рахунком допоміжний файл після розподілу серій залишився порожнім.
Природне злиття, у якого після фази розподілу кількістьсерій у допоміжних файлах відрізняється один від одного не більше ніж на одиницю, називаєтьсязбалансованим злиттям, в іншому випадку -незбалансоване злиття.
Таким чином, кількість читань або перезаписів файлів при використанні методу природного злиття буде не гірше, ніж при застосуванні методу простого злиття, а в середньому навіть краще. Але в цьому методі збільшується кількість порівнянь за рахунок тих, які потрібні для розпізнавання кінців серій. Крім цього, максимальний розмір допоміжних файлів може бути близьким до розміру вихідного файлу, оскільки довжина серій може бути довільною.
Ключові терміни
Зовнішнє сортування - це сортування даних, які розташовані на зовнішніх пристроях і не вміщуються в оперативну пам'ять.
Двошляхове злиття – це сортування, в якому дані розподіляються на два допоміжні файли.
Двофазна сортування - це сортування, в якому окремо реалізується дві фази: розподіл та злиття.
Довжина серії – це кількість елементів у серії.
Природне злиття - це сортування, при якому завжди зливаються дві найдовші з можливих серій.
Багатошляхове злиття – це сортування, у якому дані розподіляються на N (N > 2) допоміжних файлів.
Незбалансоване злиття - це природне злиття, у якого після фази розподілу кількість серій у допоміжних файлах відрізняється один від одного більш ніж на одиницю.
Однофазна сортування - це сортування, в якій об'єднані фази розподілу та злиття в одну.
Просте злиття - це одне із сортувань на основі злиття, в якій довжина серій фіксується на кожному кроці.
Розподіл – це процес розділення впорядкованих серій на два та кілька допоміжних файлів.
Збалансоване злиття - це природне злиття, у якого після фази розподілу кількість серій у допоміжних файлах відрізняється один від одного не більше ніж на одиницю.
Серія (упорядкований відрізок) – це послідовність елементів, яка впорядкована ключем.
Злиття - це процес об'єднання двох (або більше) впорядкованих серій в одну впорядковану послідовність за допомогою циклічного вибору елементів доступних в даний момент.
Фаза - це дії з одноразової обробки всієї послідовності елементів.
Короткі підсумки
1. Зовнішні сортування застосовуються до даних, які зберігаються у зовнішній пам'яті. Зовнішні сортування застосовуються, якщо обсяг даних, що сортуються, перевищує допустиме місце в ОЗУ.
2. Зовнішні сортування, порівняно із внутрішніми, характеризуються програшем у часі за рахунок звернення до зовнішніх носіїв.
3. До найбільш відомих алгоритмів зовнішніх сортувань відносяться: сортування злиттям (просте злиття та природне злиття); покращені сортування (багатофазне сортування та каскадне сортування).
4. Алгоритми зовнішніх сортувань відрізняються за реалізацією числом фаз та шляхів.
5. Просте злиття є одним із сортувань на основі злиття, в якому довжина серій фіксується на кожному кроці.
6. Природне злиття є сортуванням, при якому завжди зливаються дві найдовші з можливих серій.
7. Число читань або перезаписів файлів при використанні методу природного злиття буде не гірше, ніж при застосуванні методу простого злиття, а в середньому навіть краще. Однак у даному методізбільшується кількість порівнянь з допомогою розпізнавання кінців серій.