![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Припустимо, що є послідовний файл А, що складається з записів а1,a2,…,an (знову для простоти припустимо, що n є ступенем числа 2). Вважатимемо, що кожен запис складається лише з одного елементу, що є ключем сортування. Для сортування використовуються два допоміжні файли В і С (розмір кожного з них буде n/2).
Сортування складаєтся з послідовності кроків, в кожному з яких виконується розподіл стану файлу А у файли В і С, а потім злиття файлів В і С у файл А. (Помітимо, що процедура злиття для файлів ілюструється рисунком 33). На першому кроці для розподілу послідовно читається файл А, і записи а1, а3, …, а (n-1) пишуться у файл В, а записи а2, а4, …, аn – у файл С (початковий розподіл). Початкове злиття здійснюється над парами (а1,а2), (а3,а4), …, (а(n-1),аn), ш результат записується у файл А. На другому кроці знову послідовно читається файл А, і у файл В записуються послідовні пари з непарними номерами, а у файл С – з парними. При злитті утворюються і пишуться у файл А впорядковані четвірки записів. І так далі. Перед виконанням останнього кроку файл А міститиме дві впорядковані послідовності розміром n/2 кожна. При розподілі перша з них потрапить у файл В, а друга – у файл С. Після злиття файл А міститиме повність впорядковану послідовність записів. У таблиці 10 показаний приклад зовнішнього сортування простим злиттям. Заз начимо, що для виконання зовнішнього сортування методом простого злиття в основній памяті вимагається розташувати всього дві змінні – для розміщення записів з файлів В і С.
Таблиця 10 – Приклад зовнішнього сортування простим злиттям
Початковий стан файла | 8 23 5 65 44 33 1 6 |
Перший крок | |
Розподіл | |
Файл В | 8 5 44 1 |
Файл С | 23 65 33 6 |
Злиття: файл А | 8 23 5 65 33 44 1 6 |
Другий крок Розподіл | |
Файл В | 8 23 33 44 |
Файл С | 5 65 1 6 |
Злиття: файл А | 5 8 23 65 1 6 33 44 |
Третій крок Розподіл | |
Файл В | 5 8 23 65 |
Файл С | 1 6 33 44 |
Злиття: файл А | 1 5 6 8 23 33 44 65 |
Дата публикования: 2014-11-26; Прочитано: 687 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!