Сортування злиттям: алгоритм, переваги і особливості

Кучер В.Г.

Природне злиття

Цей метод не обмежує довжину серій, а вибирає максимально можливі.

Алгоритм сортування:

  • Починається зчитування вихідної послідовності з файлу f. Перший отриманий елемент записується в файл f1.
  • Якщо наступна запис задовольняє умові сортування, вона записується туди ж, якщо немає – то в другий допоміжний файл f2.
  • Таким чином розподіляються усі запису вихідного файлу, а в f1 утворюється впорядкована послідовність, яка і визначає поточний розмір серії.
  • Файлів f1 і f2 зливаються.
  • Цикл повторюється.
    • Цікаве:  Методи прогнозування: класифікація, характеристика, приклад

    З-за нефіксованого розміру серії доводиться позначати закінчення послідовності спеціальним символом. Тому при злитті збільшується кількість порівнянь. Крім того, розмір одного з допоміжних файлів може наближатися до розміру початкового.

    У середньому метод природного злиття працює ефективніше в порівнянні з простим злиттям при зовнішній сортування.

    Сторінка: 1 2 3 4 5 6 7 8 9 10