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

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);}

end;

begin

assign(f0,'a-file.bin');

MergeSort(f0);

end.

3. Метод злиття впорядкованих серій

В основі методу зовнішнього сортування багатошляхового злиття (злитя впорядкованих серій) лежить розподіл серій вихідного файлу по m допоміжних файлах B1, B2,..., Bm і їхнє злиття в m допоміжних файлів C1, C2,..., Cm. На наступному кроці виробляється злиття файлів C1, C2,..., Cm у файли B1, B2,..., Bm і т.д., поки в B1 або C1 не утвориться одна серія. Графічно це можна зобразити наступним чином:

Рис. 3. Злиття впорядкованих серій

На малюнку 3 показаний простий приклад застосування сортування збалансованим багатошляховим злиттям. Він, звичайно, занадто тривіальний, щоб продемонструвати кілька кроків виконання алгоритму, однак достатній як ілюстрація загальної ідеї методу. Помітимо, що, як показує цей приклад, у міру збільшення довжини серій допоміжні файли з більшими номерами (починаючи з номера n) перестають використовуватися, оскільки їм «не дістається» ні однієї серії. Перевагою сортування збалансованим багатофазним злиттям є те, що число проходів алгоритму оцінюється як O(log n) (n - число записів у вихідному файлі), де логарифм береться по підставі n. Порядок числа копіювань записів - O(log n). Звичайно, число порівнянь не буде менше, ніж при застосуванні методу простого злиття.

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

Program Vporjadkovane_zluttja;

const max=10000;

maxint=32767;

type

Item=record