Курсовая работа: Порівняльний аналіз ефективності та складності алгоритмів сортування файлів і послідовностей

При використанні методу прямого злиття не приймається в увагу те, що вихідний файл може бути лише частково відсортованим, тобто містити впорядковані підпослідовності записів. Серією називається підпослідовність записів ai, a(i+1),..., aj така, що ak <= a(k+1) для всіх i <= k < j, ai < a(i-1) і aj > a(j+1). Метод злиття впорядкованих серій ґрунтується на розпізнаванні серій при розподілі і їхньому використанні при наступному злитті.

Як і у випадку прямого злиття, сортування виконується за кілька кроків, у кожному з яких спочатку виконується розподіл файлу A по файлах B і C, а потім злиття B і C у файл A. При розподілі розпізнається перша серія записів і записується у файл B, друга - у файл C і т.д. При злитті перша серія записів файлу B зливається з першою серією файлу C, друга серія B із другою серією C і т.д. Якщо перегляд одного файлу закінчується раніше, ніж перегляд іншого (через різне число серій), те залишок недопереглянутого файлу цілком копіюється в кінець файлу A. Процес завершується, коли у файлі A залишається тільки одна серія. Приклад сортування файлу показаний на малюнках 1 та 2.

Рис. 1. Перший крок

Рис. 2. Другий крок

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

Реалізація методу мові програмування Turbo Pascal. Нехай маємо типізований файл додатних цілочисельних даних, використовуючи метод злиття впорядкованих серій (природне злиття) відсортувати цей файл по зростанню.

Примітка: Для генерування початкового файлу тут і надалі в курсовій програмі використовується файл Generat.pas, що формує бінарні файли. Лістінг даної програми поданий в додатках.

Program Natural_sort;

type Item=record

key:longint;

end;

TFile=file of Item;

var

f0:TFile;

procedure merge(k:integer;var f1,f2,g1,g2:TFile);

var outSwitch:boolean;

Winner:integer;

Used:array[1..2] of integer;

Fin:array[1..2]of boolean;

current:array[1..2]of Item;

procedure GetItem(i:integer);

begin

if(Used[i]=k)or((i=1)and eof(f1))or((i=2)and eof(f2)) then Fin[i]:=True

else if i=1 then read(f1,Current[1])

else read(f2,Current[2]);

Used[i]:=Used[i]+1;

end;