write(f4,buf);
inc(n);
end;
end;
flag:=true;k:=1;
Close(f1);Close(f2);Close(f0);
Close(f3);Close(f4);
n:=trunc(ln(n)/ln(4))+1;
for i:=1 to n do
begin
if flag then NMerge(k,f1,f2,f3,f4,g1,g2,g3,g4)
else NMerge(k,g1,g2,g3,g4,f1,f2,f3,f4);
flag:= not flag;
k:=k*4;
end;
rewrite(f0);reset(g1);reset(f1);
if not flag then
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. Нехай маємо файл цілих чисел, відсортувати його використовуючи багатофазне злиття.
Program polysort;
{багатофазне сортування з n - лентами}
Const n=6; {число лент}
Type item = record
Key:integer;
End;
Tape = file of item;
Tapeno = 1..n;
Var leng, rand: integer; {використовується для формування файлу}
Eot: Boolean;
Buf: item;
F0: tape; {f0 – вхідна лента із випадковими числами }
F: array [1..n] of tape;
Procedure List (var f: tape; n:tapeno);
Var z: integer;
Begin z:=0;
Writeln(‘TAPE’,n:2);
While not eof(f) do
Begin read(f,buf); write(output,buf.key: 5); z:=z+1;
If z=25 then
Begin writeln(output); z:=0
End;
End;
If z<>0 then writeln(output); reset(f);
End; {LIST}
Procedure Pholyphasesort;
Var I,j,mx,tn:tapeno;
K,level: integer;
A,d: array [tapeno] of integer;
{a[j] – ідеальне число серій на ленті }
{d[j] – число фіктивних серій на ленті}
Dn, x, min, z:integer;
Last: array [tapeno] of integer;
{last[j] – ключ кінцевої серії на ленті}
T,ta: array [tapeno] of tapeno;
{карти номерів ленти}
Procedure selecttape;
Var i: tapeno; z:integer;
Begin
If d[j]<d[j+1] then j:=j+1 else
Begin if d[j]=0 then
Begin level:=level+1; z:=d[1];
For i:=1 to n-1 do
Begin d[i]:=z+a[i+1]-a[i]; a[i]:=z+a[i+1]
End;
End;
J:=1;
End;
D[j]:=d[j]-1;
End;
Procedure copyrun;
Begin {перепис однієї серії з f0 на ленту}
Repeat read(f0,buf); write(f[j],buf);
Until eof(f0) or (buf.key>f0.key);
Last[j]:=buf.key;
End;
Begin {розподіл початкових серій}
For i:=1 to n-1 do
Begin a[i]:=1; d[i]:=1; rewrite(f[i]);
End;
Level:=1; j:=1; a[n]:=0; d[n]:=0;
Repeat selecttape; copyrun
Until eof(f0) or (j=n-1);
While not eof(f) do
Begin selecttape;
If last[j]<=f0.key then
Begin {продовження попередньої серії}
Copyrun;
If oef(f0) then d[j]:=d[j]+1 else copyrun
End
Else copyrun
End;
For i:=1 to n-1 do reset(f[i]);
For i:=1 to n do t[i]:=I;
Repeat {злиття з t[1]…t[n-1] на t[n]}
Z:=a[n-1]; d[n]:=0; rewrite(f[t[n]]);
Repeat k:=0; {злиття однієї серії}
For I:=1 to n-1 do
If d[i]>0 then d[i]:=d[i]-1 else
Begin k:=k+1; ta[k]:=t[i];
End;
If k=0 then d[n]:=d[n]+1 else
Begin {злиття одного дійсного відрізка із t[1]…t[k]}
Repeat i:=1; mx:=1;
Min:=f[ta[1]].key;
While i<k do
Begin I:=i+1; x:=f[ta[i]].key;
If x<min then
Begin min:=x; mx:=i
End;
End;
Read(f[ta[mx]],buf);eot:=eof(f[ta[mx]]);
Write(f[t[n]],buf);
If (buf.key>f[ta[mx]].key)or eot then
Begin Ta[mx]:=ta[k]; k:=k-1
End
Until k=0
End;
Z:=z-1;
Until z=0;
Reset(f[t[n]]); list(f[t[n]],t[n]);
tn:=t[n]; dn:d[n]; z:=a[n-1];
for i:=n downto 2 do
begin t[i]:=t[i-1]; d[i]:=d[i-1]: a[i]:=a[i-1] –z
end;
t[1]:=tn; d[1]:=dn; a[1]:=z;
list (f[t[1]],t[1]); level:=level -1;
until level=0;
end {polyphasesort};
begin
leng:=200; rand:=7789;
repeat rand:=(131071*rand) mod 2147483647;
buf.key:=rand div 2147484; write(f0,buf);
leng:=leng-1
until leng=0;
reset(f0); list(fo,1);
polyphasesort;
end.
Висновки
Як відомо, існує дуже багато методів сортування масивів, які поділяються на прямі і швидкі. Проте, їх практично не можливо застосувати по роботі із великими файлами, коли об’єм даних перевищує об’єм оперативної пам’яті. Саме тому, метою даної курсової програми було розглянути існуючі методи сортування файлів.
Так, ми розглянули найбільш відомі широкому загалу методи: простого злиття, метод природного злиття, метод збалансованого злиття впорядкованих серій та багатофазного злиття.
Оскільки ми не ставили собі за мету вивчити можливість та переваги тих чи інших методів сортування у конкретних задачах, то із поставленою метою, а саме із вивченням і реалізацію найбільш використовуваних у сучасному програмуванні алгоритмів сортування файлів ми справилися повністю.
У відповідності до мети та завдання курсової роботи були виконані наступні кроки:
1. Було проведено детальний аналіз літератури та електронних джерел за темою «сортування файлів та послідовностей», це дало змогу сформувати як теоретичні основи, так і зробити передбачення щодо створення програм демонстраційного характеру.
2. До вибору мови програмування, щодо реалізації даних методів ми підійшли з тієї точки зору, що б вона програма, яку ми б написали була зрозуміла широкому загалу, а саме Turbo Pascal. Вибір даної мови програмування був обумовлений тим, що вона найбільш підходить для навчальних цілей. Оскільки в школах і вузах початки програмування і алгоритмізацію показуються саме з допомогою Turbo Pascal. Вибір цієї мови програмування був зумовлений ще і її гнучкістю і простотою в застосуванні і розумінні. У програмах було зроблено коментарі, які роблять їх більш зрозумілими для розуміння;
3. У курсовій роботі ми не проводили сортування файлів, що б містили складні структури даних. Це пов’язано із тим, що ми виклали найбільш використовувані алгоритми, їх математичні моделі і вже знаючи ці методи, можна досить просто перевести їх використання і подальше удосконалення на практиці.
4. Зрозуміло, що хоча ми і розглянули найбільш відомі методи сортування файлів, існує ще безліч інших способів їх удосконалення. Так наприклад, при багатофазному злитті сортування у вже розбитих серіях можна проводити і за допомогою статичних методів сортування, наприклад за допомогою дерева, чи швидкого сортування, це також пришвидшить роботу алгоритму.
Отже, виконуючи курсову роботу, ми вивчили розділ програмування «сортування послідовностей і файлів», провели аналіз швидкодії важкості реалізації найбільш використовуваних на практиці алгоритмів сортування, навели графічне представлення операцій сортування та створили робочі програми, які наявно демонструють роботу цих методів.
Дану курсову роботу, на нашу думку, можна використовувати в курсі вивчення основних методів і алгоритмів сортування та пошуку даних.
Література
1. Turbo Pascal – Издательская група К.: ВНV, 2000. – 320 с.
2. Абрамов В.Г. Введение в язык Pascal: Учебное пособие для студентов вузов по специальности Прикладная математика. – М.: Наука, 1988. – 200 с.
3. Абрамов С.А., Зима Е.В. Начала программирования на языке Pascal. - М.: Наука, 1987. – 126 с.
4. Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М.: Лаборатория базовых знаний, 2000. – 201 с.
5. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: “Вильямс”, 2000. – 163 с.
6. Вирт Н. Алгоритмы и структуры данных. M.: Мир, 1989. – 142 с.
7. Власик А.П. Практикум з програмування в середовищі Turbo Pascal. Ч 1.- Рівне: НУВГП, 2005. – 179 с.
8. Глушаков С.В. Программирование на Visual C++. – М.: АСТ; Х.: Фоліо, 2003. – 726 с.
9. Грис Д. Наука программирования. M.: Мир, 1984. – 230 с.
10. Джонс Ж., Харроу К. Решение задач в системе Турбо-Паскаль/ Перевод с английского Улановой, Широкого. – М.: Финансы и статистика, 1991. – 709 с.
11. Зуев Е. А. Язык программирования Турбо Паскаль 6.0, 7.0. – М.: Радио и связь, 1993. – 150 с.
12. Кнут Д.Э. Искуство програмирования, том 3. Поиск и сортировка, 3-е изд.: Пер. с англ.: Уч. Пос. – М.:Издательский дом «Вильямс», 2000. – 750 с.
13. Кнут Д.Э. Искуство програмирования, том 3. Поиск и сортировка, 3-е изд.: Пер. с англ.: Уч. Пос. – М.:Издательский дом «Вильямс», 2000. – 750 с.
14. Ковалюк Т.В. Основи програмування. Київ: Видавнича група ВНV, 2005. – 385 с.
15. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000. – 93 с.
16. Культин Н. Б. Программирование в Turbo Pascal 7.0 и Delphi. - Санкт- петербург,1999.
17. Львов М. С., Співаковський О. В. Основи алгоритмізації та програмування. Херсон, 1997.
18. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0. К.: ВЕК, 2000. – 441 с.
19. Окулов С.M. Сортировка и поиск. “Информатика”, №35, 2000. – 73 с.
20. Перминов О. Н. Язык программирования Pascal. – М.: Радио и связь,1989. – 205 с.
21. Фаронов В. В. TurboPascal 7.0. Начальный курс. – М.: “Нолидж”, 2000.
22. Шень А. Программирование: теоремы и задачи. М.: МЦНМО. – 205 с.
23. Щедріна О.І. Алгоритмізація та програмування процедур обробки інформації. К., 2001. – 240 с.
Додаток 1
Лістінг програми генерації початкових бінарних файлів.
program Generat;
type
item=record
key:integer;
end;
filetype=file of item;
var
a,b:file of item;
i:longint;
a_len:integer;
b_len:integer;
x:item;
begin
assign (a,'a-file.bin');
assign (b,'b-file.bin');
write ('Введіть довжину файлу A: ');
readln (a_len);
write ('Введіть довжину файлу B: ');
readln (b_len);
rewrite (a);
randomize;
i:=0;
while i<=a_len do
begin
x.key:=random(a_len);
write(a,x);
inc(i);
end;
close (a);
rewrite (b);
i:=0;
while i<=b_len do
begin
x.key:=random(b_len);
write (b,x);
inc(i);
end;
close (b);
writeln ('Файли утоврені коректно');
readln;
end.