Упорядоченные файлы

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

Для любого i  [1,len(a)] (a_i<=a_i+1)

Для любого i,j  [1,len(a)] (i<=j → a_i<=a_j)

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

Поиск в упорядоченном файле

Found:=

a_i=x

 i[1,len(a)] (a_i>=x)

Идея: достаточно найти первое i, такое что x<=a_i, тогда found:=true  x=a_i, если таковое существует; если такового нет, то found:=false.

Итак, поиск такого первого i: a_i>=x

found1:=i (a_i>=x)

assign(f,’…’);

reset(f);

found1:=false;

while (not found1) and (not eof(f)) do

begin

read(f,a);

if a>=x then found1:=true

end;

if found1 then found:=a=x

else found:=false;

Арифметика упорядоченных файлов

Упражнение: Найти разность, объединение, пересечение упорядоченных файлов. Результат - так же упорядоченный файл.

Мотивация: Упорядочить файл – тяжёлая задача, не имеющая эффективного решения (однопроходного алгоритма). Гораздо проще сохранять упорядоченность файлов. Все алгоритмы – однопроходные.

Разность файлов:

f₃=f₁\f₂

reset(f₁);

reset(f₂);

rewrite(f₃);

while

begin

read(f₁,x);

If {xf₂} then write(f₃,x);

end

Задача решена, если для проверки включения использовать предыдущий алгоритм и учесть, что файл f₁ также упорядочен, а значит поиск в файле f₂ первого элемента b_i>=a_i не портит такого поиска для следующего элемента a_i, то есть b_j>=b_j.

Дихотомический поиск в упорядоченном массиве

Program Binar;

Var a:array[1..n] of integer;

l,r,m:integer;

found:boolean;

Begin

{ввод a}

l:=1;

r:=n;

found:=false;

while (l<=r) and not found do

begin

m:=(l+r) div 2;

if a[m]=x

then found:=true

else if a[m]<x then l:=m+1

else r:=m-1;

end;

end.

{Текст программы взят из книги, а не с лекции, но большой разницы быть не должно, т.к. алгоритм один}

Простые алгоритмы сортировки

Сортировка простым обменом

i (a_i<=a_i+1)

i,j (i<=j → a_i<=a_i+1)

Сортировка вставкой определяется в терминах операции вставки

а:=вставка(а,х)

a₁<=…<=a_n x

Begin

{ввод a}

for k:=2 to n do

begin

x:=a[k];

j:=k-1;

while (j>0) and (x<a[j]) do

begin

a[j+1]:=a[j];

dec(j);

end;

a[j+1]:=x;

end;

End.

{Текст этой программы также взят из книги, абсолютно уверен в несоответствии этой программы и программы на лекции, но идея одна}

На шаге «0» упорядоченная часть состоит из 1 элемента, неупорядоченная – из всех остальных. На i-ом шаге алгоритма берём первый элемент a_i из неупорядоченной части и вставляем его в уже упорядоченную к этому шагу часть; Достаточно n-1 шага.

Найти наибольшее j, такое что a_j<a_i, если оно есть, если нет поставить a_i на место a_j+1, т.е. сдвинуть все элементы начиная с места j+1 на единицу вправо, а потом на освободившееся место поставить a_i.