Курсовая работа: Порівняльний аналіз ефективності та складності алгоритмів сортування файлів і послідовностей
while not eof(g1) do
begin
read(g1,buf);
write(f0,buf);
end
else
while not eof(f1) do
begin
read(f1,buf);
write(f0,buf);
end;
Close(f0);Close(g1);Close(f1);
erase(f1);erase(g1);erase(f2);erase(g2);
erase(f3);erase(g3);erase(f4);erase(g4);
end;
begin
assign(f0,'a-file.bin');
NMergeSort(f0);
end.
4. Багатофазне злиття
Розглядувані вище прийоми дають змогу створити більш ефективний алгоритм, ніж попередні. Так, ми бачили що при збалансованому злитті зникають операції простого копіювання, оскільки розподілення і злиття об’єднані в одну фазу. Нове вдосконалення заклечається в тому, що коли відмовитися від строгого поняття проходу, то саме поняття можна тлумачити і реалізовувати по іншому. Цей метод був створений Р.Л. Гілстадом і названий багатофазним сортуванням.
Спочатку проілюструємо його на прикладі роботи із трьома файлами. В кожний момент елементи зливаються із двох файлів у третій. Як тільки один із вхідних файлів стане вичерпаним, він стає вихідним для злиття з іншим файлом, який ще не вичерпався і з тим, що якого був вихідним.
Оскільки ми знаємо, що n серій на кожному вхідному файлі перетворюються в n серій на вихідному, нам потрібно тільки вести список числа серій на кожному файлі.
Зрозуміло, що принципова структура багатофазного злиття основною частиною програми n-шляхового злиття: наявний внутрішній цикл, в тілі якого зливаються серії, поки не будуть вичерпані всі вхідні дані, внутрішній цикл, в тілі якого зливаються по одній серії з кожної вхідної лєнти (файлу), і сам внутрішній цикл, в тілі якого вибирається начальний ключ і елемент передається в вихідний файл. Принципові відмінності в наступному:
1. На кожному проході маємо тільки один вихідний фай замість n/2.
2. Замість перемикання n/2 вхідних і n/2 вихідних файлів після кожного проходу файли передуються. Це досягається з допомогою карти файлових індексів t.
3. Число вхідних файлів міняється від серії до серії; спочатку кожної серії воно визначається по індексам фіктивних серій. Якщо >0 для всіх і, то n-1 фіктивних серій зливаються в одну фіктивну серію при допомозі простого збільшення індекса вихідного файлу. В протилежному випадку зі всіх файлів, у яких індекс =0, зливається по одній серії, а для всіх решти файлів індекс зменшується, що означає вилучення однієї фіктивної серії. Число вхідних файлів ми позначимо через k.
4. Неможливо встановити закінчення фази при допомозі стану закінчення файлу (n- 1) лєнти, оскільки можуть знадобитися подальші злиття, в яких залучені фіктивні серії з цієї ленти. Замість цього теоретично необхідне число серій визначається на коефіцієнту ai Коефіцієнти ai були обраховані на фазі розподілення; тепер їх можна обрахувати в зворотному порядку.
Реалізація методу багатофазного злиття на Turbo Pascal. Нехай маємо файл цілих чисел, відсортувати його використовуючи багатофазне злиття.