Головна

Двоколійному спрощене злиття.

  1.  Природне двоколійних злиття - ЄДС

Алгоритм М. (двоколійних злиття)

Цей алгоритм здійснює злиття двох упорядкований файлів х1, х2, ..., Хm і у1, у2, ..., Уn в один файл z1, z2, ..., Zm + n.

(Початкова установка) Встановити i: = 1, j: = 1, k: = 1.

(Знайти найменший елемент) Якщо хi ? уj, То перейти до кроку М3; в іншому випадку перейти до М5.

(Вивести хi) Встановити zk: = Хi, K: = k + 1, i: = i + 1. Якщо i ? m, то повернутися до кроку М2.

(Вивести уj, ..., Уn) Встановити (zk, ..., Zm + n): = (Уj, ..., Уn) І завершити роботу алгоритму.

(Вивести уi) Встановити zk: = Уi, K: = k + 1, j: = j + 1. Якщо j ? n, то повернутися до кроку М2.

(Вивести хi, ..., Хm) Встановити (zk, ..., Zm + n): = (Хi, ..., Хm) І завершити роботу алгоритму.

Ця проста процедура злиття найкращий варіант, якщо m »n. (Але якщо m набагато менше n, можна розробити набагато ефективніші алгоритми сортування).

Мал. 5 Сортування природним двоколійному злиттям

Можна помітити, що метод сортування вставками - це є злиття двох подфайлов, у одного з якого n = 1! Отже, завдання сортування можна звести до злиття, зливаючи все довші подфайли до тих пір, поки не буде відсортований весь файл. Для прискорення процесу вставок, можна розглянути вставку кількох елементів за раз (n> 1), групуючи їх. Такий метод злиття - один з найперших методів сортування, запропонований в 1945 Джоном фон Нейманом і носить назву природне двоколійних злиття.

 Блок-схема, відповідна алгоритму Е. (Мається на увазі використання оператора GOTO)  


 Сортування підрахунком |  Сортування природним двоколійному злиттям.

 Прості схеми сортування |  Сортування простий вставкою. |  Сортування за допомогою простого вибору |  Тимчасова складність методів сортування |  Метод Шелла (сортування з спадному кроком). |  Швидке сортування |  пірамідальна сортування |  Пірамідальна сортування. |  Сортування простим (фіксованим) двоколійному злиттям. |

© um.co.ua - учбові матеріали та реферати