Организация и функционирование компьютеров

procedure p1(n: integer) forward;

procedure p2 (i,j: integer);

begin … p1(4); … end;

procedure p1;

begin … p2(5,6); … end;

Заметим, что во втором заголовке процедуры p1 нет необходимости указывать все реквизиты, поскольку они уже специфицированы в первом заголовке.

Другие примеры рекурсивных процедур и функций будут приведены в следующей главе.

4.15. Сортировка массивов и файлов.

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

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

Пусть задан массив a целых чисел длины n. Первый способ сортировки называется сортировкой обменом. Идея алгоритма достаточно проста. Найдем среди элементов массива минимальный и поменяем его с первым элементом, затем найдем минимальный среди оставшихся и поменяем его со вторым элементом и т.д. Фрагмент программы на Паскале выглядит так:

for j:=1 to n-1 do {Для всех элементов массива, кроме последнего, сделать}

begin m := j; {Ищем минимальный элемент (вначале j-й) }

for k:=j+1 to n do

if a[k]

x := a[j]; {Обменять минимальный элемент с j-ым}

a[j] := a[m];

a[m] := x

end;

Второй способ сортировки называется пузырьковым. В первом цикле, начиная с первого, сравниваются соседние элементы массива, и они переставляются, если последующий элемент меньше предыдущего. В конце цикла самый большой элемент автоматически оказывается в конце массива (“всплывает” в конец массива, отсюда название “пузырьковый”). Во втором цикле то же самое проделывается с элементами массива, исключая последний, и т.д. Фрагмент программы на Паскале выглядит так:

for j:=n downto 2 do {Для всех начальных частей массива сделать}

for k:=1 to j-1 do {Сравнить все пары соседних элементов от первого до (j-1)-го}

if a[k]>a[k+1]

begin x := a[k]; {Обменять k-й элемент с (k+1)-ым}

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

a[k+1]:= x

end;

Третий способ сортировки называется сортировкой слиянием. Пусть массив a длины n и массив b длины m уже отсортированы в возрастающем порядке, и пусть мы хоти молучить массив длины (n+m), состоящий из их объединения и также отсортированный. Это делается за один проход по массиву a и массиву b следующим образом:

j:=1; k:=1; i:=1; {Текущими являются первые элементы массивов a, b и c}

while (j

begin

if (jm) or (a[j]

{Массив a не кончился, а массив b кончился, либо массив b не кончился и

текущий элемент массива a меньше или равен текущему элементу массива b}

begin c[i]:=a[j]; {Записываем в массив c элемент массива a}

j:=j+1; {Сдвигаем текущий элемент массива a}