Информатика -продвинутый курс




ВАЖНЕЙШИЕ НЕВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ (ПОИСК И СОРТИРОВКА) - часть 14


В окончательном виде алгоритм сортировки слиянием представлен ниже.

Программа 53

program sortirovka_faila_2;

(сортировка последовательного файла слиянием} const N=8;

type item= integer; var a: arrayd. ,2*n] of item;

i, j, k, L, t, h, m, p, q,^r: integer; f: boolean;

begin

(задание искомого массива}

for i:=l to N do begin write( 'введи элемент а[ ',i,']='}!

readln(a[i]) ;

end;

writein;

(сортировка слиянием) f:=true; p:=l;

repeat

h:=l; т^п; if f then begin

i:=l; j:-n;k:=n+l; L:=2*n end else begin k:=l; L:=n;i:=n+l; j:-2*n

end; . repeat

if m>=p then q:=p else q:»m; m:=m-q;

if m>=p then r:=p else r:=m; m:=in-r;

while (q<>0) and (r00) do begin

if a[i]<a(j] then begin a[k]:=a(i]; k:=k+h; i:=i+l;q:=q-l

end else

begin a[k]:=a[j]; k:=k+h; j:=j-l;r:=r-l end;

end;

while r>0 do begin a[k]:=atj]; k:°k+h; j:=j-l; r:»r-l;

end;

while q>0 do begin

a[k]:=a[i]; k:°k+h; i:=i+l; q:=q-l;

end;

h:=-h; t:=k;k:=L; L:=t;

until m=0;

f:=not(f); p:°2*p;

until p>=n;

if not(f) then for i:=l to n do a[i]:=a[i+n] ;

(вывод результата} . for i:=l to N do begin write(a[i], ' ');

end;

readin;

end.

Рассмотренные два предыдущих примера иллюстрируют большие проблемы сортировки внешних файлов, если в них часты изменения элементов, например, удаления, добавления, корректировки существующих.

В подобных ситуациях эффективными становятся алгоритмы, в которых обрабатываемые элементы представляются в виде структур данных, удобных для поиска и сортировки. В качестве структур данных можно отметить, в частности, линейные списки, очереди, стеки, деревья и т.п. О них было рассказано в предыдущем разделе.




Содержание  Назад  Вперед