Function имя_функции(параметры);Forward;

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

Например: процедура с именем А вызывает процедуру с именем В, а процедура В, в свою очередь, вызывает процедуру А.

Procedure A(y:тип);Forward; {Опережающее описание процедуры А}

Procedure B(x:тип); { Заголовок процедуры В}

. . . {Раздел описаний процедуры В}

begin

. . .

A(p); {Вызов процедуры А из В}

. . .

end;

Procedure A; {Основное описание процедуры А}

. . . {Раздел описаний процедуры А}

Begin

. . .

B(g); {Вызов процедуры В из А}

. . .

End;

17. Задача сортировки: алгоритмы и программы

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

Наиболее простыми алгоритмами сортировки считаются алгоритмы, известные в литературе под названиями - обменная (или пузырьковая) сортировка и сортировка выбором. Эти алгоритмы, в худшем случае, решают задачу сортировки за время пропорциональное N², где N - число сортируемых элементов. Такие алгоритмы называют алгоритмами с квадратичной сложностью. Эти алгоритмы используют, когда число сортируемых элементов относительно не велико (до 1000). Для сортировки данных больших объемов используют более сложные, с точки зрения реализации, алгоритмы. Сложность этих алгоритмов определяется по формулам: N*lnN или N*log₂N. Такие алгоритмы называют алгоритмами с логарифмической сложностью или быстрой сортировки. Эти алгоритмы используют чаще всего при сортировке данных в оперативной памяти, например в массивах или в динамических списках. Для сортировки данных во внешней памяти можно использовать алгоритм сортировки слиянием. Кроме перечисленных алгоритмов существует большое число других алгоритмов, с которыми можно ознакомиться, например, в [2,3].