НОУ ІНТУІТ, Лекція, Алгоритми сортування масивів
Сортування природним злиттям
У разі простого злиття часткова впорядкованість даних, що сортуються, не дає жодної переваги. Це тим, що у кожному проході зливаються серії фіксованої довжини. При природному злитті довжина серій не обмежується, а визначається кількістю елементів у вже впорядкованих підпослідовності, що виділяються на кожному проході.
Сортування, при якому завжди зливаються дві найдовші з можливих послідовностей, є природним злиттям. У цьому сортуванні об'єднуються серії максимальної довжини.
Алгоритм сортування природним злиттям
Крок 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) допоміжних файлів.
Незбалансоване злиття- це природне злиття, у якого після фази розподілу кількість серій у допоміжних файлах відрізняється один від одного більш ніж на одиницю.
Однофазна сортування- це сортування, в якій об'єднані фази розподілу та злиття в одну.
Простезлиття - це одне з сортувань на основі злиття, в якій довжина серій фіксується на кожному кроці.
Розподіл– це процес розділення впорядкованих серій на два та кілька допоміжних файлів.
Збалансоване злиття- це природне злиття, у якого після фази розподілу кількість серій у допоміжних файлах відрізняється один від одного не більше ніж на одиницю.
Серія (упорядкований відрізок)- це послідовність елементів, яка впорядкована за ключом.
Злиття- це процес об'єднання двох (або більше) упорядкованих серій в одну впорядковану послідовність за допомогою циклічного вибору елементів доступних в даний момент.
Фаза- це дії з одноразової обробки всієї послідовності елементів.