[ЗМІСТ] [Далі] [Назад] [Початок розділу]
8.2.2. Сортування файлів
Файл,
як правило, має достатньо великий розмір і його не можна розмістити у
оперативній пам’яті у вигляді масива, щоб відсортувати одним з розглянутих
методів. Тоді застосовують методи зовнішнього сортування. Частіше за все для
сортування файлів використовують метод природного злиття. Цей метод
використовує для сортування файла три (або два) допоміжних файла.
Розглянемо
спочатку використання 2 допоміжних файлів. Нехай необхідно відсортувати
послідовний файл f1. Його
розбивають на два файли f2 та
f3, які складаються з
зростаючих підпослідовностей елементів файла f1. Першу зростаючу підпослідовність записують у файл f2, другу – у файл f3, третю
- знову у f2 тощо. Після завершення розбиття виконують
злиття впорядкованих підпослідовностей з файлів f2 та f3 у файл f1. Спочатку зливають першу пару
підпосліодовностей з f2 та f3, потім другу і т.д.
Злиття відбувається аналогічно злиттю для масивів за виключенням того, що
довжина послідовностей не фіксована. Після завершення злиття знову виконують
розбіиття f1 на f2 та f3, потім знову злиття. Процес завершують, коли у
файлі f1 утворюється одна
зростаюча підпослідовність.
Нехай файл,
який треба відсортувати, задано описами типів:
тип t = запис
key: t;
p: s
кз;
fl = файл із t;
де s – довільний тип, а для типу t визначені стандартні відношення: {=, <>, <, >, >=, <=}. Сортування файла треба виконати за значеннями ключа key. Позначимо цей файл C, а допоміжні файли – A та B. Тоді на високому рівні алгоритм можна представити так:
відкрити(C);
якщо Ø eof(C) то
повт
розбити
файл C на файли A та B;
злити файли A та B у n послідовностей у файлі C;
до n=1
кр
Дію „розбити файл C на файли A та B” оформлюємо у
вигляді процедури Divide. У цій процедурі x – попередній запис, y – поточний запис, ToA – змінна, що вказує поточний файл для розбиття (A або B).
процедура Divide(змін C, A, B: fl)
це;
змін x,y: t;
ToA: boolean;
поч
відкрити(C); створити(A); створити(B);
{файл C не порожній, тому можемо читати}
читати(C,x);
ToA <- Іст;
поки
Øeof(C)
повт
якщо
ToA то писати(A,x)
інакше
писати(B,x) кр;
читати(C,y);
якщо
y.key < x.key то {завершилась зростаюча підпослідовність}
ToA := ØToA
кр;
x <- y
кц;
{після завершення циклу обов’язково залишився один запис з C}
{його треба дописати у A або B}
якщо
ToA то писати(A,x)
інакше
писати(B,x) кр;
закрити(C); закрити(A); закрити(B);
кп;
Дію
„злити файли A та B у n послідовностей у файлі C” оформлюємо у вигляді процедури Merge3. У цій процедурі x – останній записаний у файл C запис; y – поточний запис, який треба писати у файл C; xa – останній прочитаний запис файла A; xb – останній
прочитаний запис файла B; EndOfA, EndOfB – змінні, які вказують на те, що не тільки файл (A або B) закінчився, але й усі записи цього файла
оброблено та записано у файл C; FromA – змінна, що
вказує, з якого файла треба взяти наступний запис для файла C. Коли обидва файли не оброблено, то треба
брати запис файла A у одному
з трьох випадків:
1)
якщо
він менший відповідного запису файла B та більший останнього записаного у C;
2)
якщо
він менший відповідного запису файла B та відповідний запис файла B менший останнього записаного у C (це означає кінець впорядкованої послідовності);
3)
якщо
він більший останнього записаного у C, а відповідний запис файла B менший останнього записаного у C.
Такий підхід дозволяє отримати у файлі C зростаючі послідовності максимально можливої довжини.
процедура Merge3(змін A, B, C: fl;
змін n: нат) це
змін
xa,xb,x,y: t;
EndOfA, EndOfB, FromA: бул;
поч
відкрити(A); відкрити(B); створити(C);
n <- 1;
{файл A не порожній}
EndOfA <- Хиб;
читати(A,xa); x <- xa;
EndOfB <- eof(B);
якщо
ØEndOfB
то
читати(B,xb);
якщо
xb.key<xa.key то x <- xb кр;
кр;
{злити пари впорядкованих послідовностей з A та B у C}
поки
ØEndOfA
Ú ØEndOfB повт
якщо
EndOfA то FromA <- Хиб
інякщо
EndOfB то FromA <- Іст
інакше
FromA <- xa.key<=xb.key & xa.key>=x.key Ú
xa.key<=xb.key & xb.key<x.key Ú
xa.key>=x.key & xb.key<x.key;
кр;
якщо
FromA то
y <- xa;
якщо
Øeof(A) то читати(A,xa)
інакше EndOfA <- Іст кр;
інакше
y <- xb;
якщо
Øeof(B) то читати(B,xb)
інакше EndOfB <- Іст кр;
кр;
якщо
y.key < x.key то n <- n+1 кр;
писати(C,y);
x <- y
кц;
закрити(C); закрити(A); закрити(B);
кп;
Остаточно отримуємо:
Алг NaturalMerge3 це
тип t = запис
key: t;
p: s
кз;
fl = файл із t;
процедура Divide(змін C, A, B: fl)
це;
змін x,y: t;
ToA: boolean;
поч
відкрити(C); створити(A); створити(B);
читати(C,x);
ToA <- Іст;
поки
Øeof(C)
повт
якщо
ToA то писати(A,x)
інакше
писати(B,x) кр;
читати(C,y);
якщо
y.key < x.key то
ToA := ØToA
кр;
x <- y
кц;
якщо
ToA то писати(A,x)
інакше
писати(B,x) кр;
закрити(C); закрити(A); закрити(B);
кп;
процедура Merge3(змін A, B, C: fl;
змін n: нат) це
змін
xa,xb,x,y: t;
EndOfA, EndOfB, FromA: бул;
поч
відкрити(A); відкрити(B); створити(C);
n <- 1;
EndOfA <- Хиб;
читати(A,xa); x <- xa;
EndOfB <- eof(B);
якщо ØEndOfB то
читати(B,xb);
якщо
xb.key<xa.key то x <- xb кр;
кр;
поки
ØEndOfA
Ú ØEndOfB повт
якщо
EndOfA то FromA <- Хиб
інякщо
EndOfB то FromA <- Іст
інакше
FromA <- xa.key<=xb.key & xa.key>=x.key Ú
xa.key<=xb.key & xb.key<x.key Ú
xa.key>=x.key & xb.key<x.key;
кр;
якщо
FromA то
y <- xa;
якщо
Øeof(A) то читати(A,xa)
інакше EndOfA <- Іст кр;
інакше
y <- xb;
якщо
Øeof(B) то читати(B,xb)
інакше EndOfB <- Іст кр;
кр;
якщо
y.key < x.key то n <- n+1 кр;
писати(C,y);
x <- y
кц;
закрити(C); закрити(A); закрити(B);
кп;
змін n: нат;
поч
відкрити(C);
якщо Ø eof(C) то
повт
Divide(C, A, B);
Merge3(A, B, C, n);
до n=1
кр
ка.
Послідовність
сортування файла по кроках (вертикальні риски позначають границі впорядкованих
послідовностей):
Початковий файл C
23 55|47|35|10 90|84|30
i=1
Файл
A 23 55|35 84
Файл
B 47|10 90|30
n=3
Файл
C 23 47 55|10 35 84 90|30
i=2
Файл
A 23 47 55|30
Файл
B 10 35 84 90
n=2
Файл
C 10 23 35 47 55 84 90|30
i=3
Файл
A 10 23 35 47 55 84 90
Файл
B 30
n=1
Файл
C 10 23 30 35 47 55 84 90
Тут i позначає номер кроку
циклу повт ... до.
Якщо подивитись на процес сортування з використанням
2 допоміжних файлів, то можна побачити, що розбиття файла на дві частини нічого
не дає для сортування, а тільки готує дані. Сортування просувається лише під
час злиття файлів. Тому, з метою позбутися розбиття, замість трьох файлів
використовують чотири (три з них - допоміжні). Нехай знову необхідно
відсортувати послідовний файл f1. Беруть порожній файл f4 та виконують злиття пар впорядкованих послідовностей з f1, f4 у файли f2 та f3. Першу пару зростаючих підпослідовностей зливають у файл f2, другу – у файл f3, третю
- знову у f2 тощо. Після завершення виконують злиття
впорядкованих підпослідовностей з файлів f2 та f3 у файли f1 та f4 і т.д. Процес завершують, коли у файлі f1 утворюється одна зростаюча
послідовність. Позначимо файл, що треба відсортувати, C, а допоміжні файли – A, B та D. Тоді на високому
рівні алгоритм можна представити так:
відкрити(C); створити(D);
якщо Ø eof(C) то
повт
злити файли C та D у n послідовностей у файлах A та B;
злити файли A та B у n послідовностей у файлах C та D;
до n=1
кр
Для
уточнення дій злиття файлів
можна використати модифіковану процедуру Merge3. Причому, модифікація виявляється зовсім
незначною: пари послідовностей з непарними номерами будемо писати у перший з
результуючих файлів, а з парними – у другий. Процедура розбиття тепер не
потрібна. Отримуємо алгоритм:
Алг NaturalMerge4 це
тип t = запис
key: t;
p: s
кз;
fl = файл із t;
процедура Merge4(змін A, B, C, D: fl; змін
n: нат) це
змін
xa,xb,x,y: t;
EndOfA, EndOfB, FromA: бул;
поч
відкрити(A); відкрити(B); створити(C);
створити(D);
n <- 1;
EndOfA <- Хиб;
читати(A,xa); x <- xa;
EndOfB <- eof(B);
якщо ØEndOfB то
читати(B,xb);
якщо
xb.key<xa.key то x <- xb кр;
кр;
поки
ØEndOfA
Ú ØEndOfB повт
якщо
EndOfA то FromA <- Хиб
інякщо
EndOfB то FromA <- Іст
інакше
FromA <- xa.key<=xb.key & xa.key>=x.key Ú
xa.key<=xb.key & xb.key<x.key Ú
xa.key>=x.key & xb.key<x.key;
кр;
якщо
FromA то
y <- xa;
якщо
Øeof(A) то читати(A,xa)
інакше EndOfA <- Іст кр;
інакше
y <- xb;
якщо
Øeof(B) то читати(B,xb)
інакше EndOfB <- Іст кр;
кр;
якщо
y.key < x.key то n <- n+1 кр;
якщо
n mod 2 = 1 то
писати(C,y)
інакше
писати(D,y) кр;
x <- y
кц;
закрити(C); закрити(D); закрити(A); закрити(B);
кп;
змін n: нат;
поч
відкрити(C); створити(D);
якщо Ø eof(C) то
повт
Merge4(C, D, A, B, n);
Merge4(A, B, C, D, n);
до n=1
кр
ка.
Послідовність
сортування файла по кроках:
Початковий файл C
23 55|47|35|10 90|84|30
i=1
Файл A 23 55|35 84
Файл B 47|10 90|30
n=3
Файл C 23 47 55|30
Файл D 10 35 84 90
i=2
Файл A 10 23 35 47 55 84 90
Файл B 30
n=1
Файл C 10 23 30 35 47 55 84 90
Файл
D
Весь процес завершується за два кроки циклу повт ...
до.
Як і
для масивів, для сортування
файлів було виконано тестування.
Було взято текстові файли, що складаються з цілих чисел. Побудова файлів
проводилась аналогічно побудові масивів. Результати тестування для кожного
розміру файла наведено у таблиці.
1024 4096 16384
NaturalMerge3
0.00 0.05 0.50
0.16 0.17 2.08
0.72 0.71 9.44
NaturalMerge4
0.11 0.11 0.05
0.16 0.17 0.16
0.71 0.71 0.83
Результати тестування показують, що для файлів з
випадкових чисел сортування злиттям з використанням чотирьох файлів (NaturalMerge4) дає набагато кращий результат, ніж сортування з використанням трьох
файлів. Якщо ж порівнювати з масивами, то сортування файлів на порядок
повільніше, ніж сортування масивів того ж розміру швидкими методами.
Задачі та вправи
Вправа
8.1. Визначити рекурсивну процедуру сортування масивів методом злиття.