Материал: Мансуров. Основы программирования в среде Lazarus. 2010
Глава 3 Более сложные элементы языка
____________________________________________________________________
B(i);
. . . . .
end;
procedure B(param: integer);
begin
. . . . .
A(i);
. . . . .
end;
Теперь не поможет и перестановка местами процедур, так как они "зацик-
лены" друг на друга. Только использование опережающего объявления проце-
дуры В позволяет разрешить эту проблему.
procedure B(param: integer); forward; procedure A (param: integer;)
begin
. . . . .
B(i);
. . . . .
end;
procedure B(param: integer); begin
. . . . .
A(i);
. . . . .
end;
271
Глава 4 Типовые алгоритмы обработки
информации
К типовым алгоритмам я отношу алгоритмы сортировки, поиска и алго-
ритмы работы с динамическими структурами. Можно, конечно, рассмотреть и множество других алгоритмов, отнеся их к типовым. Но мы в данной главе рас-
смотрим именно эти алгоритмы.
4.1. Алгоритмы сортировки
Сортировка - процесс упорядочения элементов какого-либо объекта по возрастанию или убыванию значений выбранного признака. По окончании сор-
тировки элементы располагаются либо по возрастанию, либо по убыванию. Ес-
ли среди элементов имеются одинаковые, то говорят сортировка по неубыва-
нию или по невозрастанию. На сортировку информации тратится 25-50% ма-
шинного времени при работе со сложными программными комплексами (раз-
личные информационно-поисковые системы на базе СУБД, компиляторы и другие программные средства).
Сортировать можно данные, для которых определены операции сравнения.
Чаще всего сортировке подлежат числа. Однако сортировать можно не только числа как таковые. Мы с вами уже знаем, что символы представляются в памя-
ти в виде некоторых кодов. Таким образом, вполне можно сортировать симво-
лы, например, фамилии можно отсортировать по алфавиту. Сортировать можно не только объекты, содержащие одиночные элементы, но и объекты достаточно сложной структуры, например записи, содержащие несколько элементов. Фай-
лы, как правило, содержат записи сложной структуры. Таким
272
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
образом и в основном, сортировке подлежат файлы. В программе предыдущего раздела структура записи файла состояла из нескольких полей, таких как "Фа-
милия", "Группа", "Предмет", "Оценка". Вполне можно осуществить сортиров-
ку этого файла, например по группе, а внутри группы отсортировать фамилии студентов по алфавиту. Поле, по которому осуществляется сортировка называ-
ется ключом. В нашем случае ключ это сначала поле "Группа", затем поле "Фа-
милия" внутри отсортированной части файла, соответствующей той или иной группе.
Эффективность методов сортировки оценивается по числу сравнений эле-
ментов между собой и числу перестановок элементов для упорядочения масси-
ва или файла. Существуют огромное количество алгоритмов сортировки. Если сортируемый файл полностью помещается в оперативной памяти, то сортиров-
ка называется внутренней. Сортировка файлов на диске называется внешней сортировкой. Кроме того, все алгоритмы сортировки можно условно разделить на "простые", но "медленные" и "сложные", но "быстрые". Взятие в кавычки здесь не случайно. В некоторых случаях "сложные", но "быстрые" алгоритмы оказываются медленнее "простых". Чаще всего так происходит для небольших файлов. Для подавляющего числа случаев "простые" алгоритмы вполне подхо-
дят по скорости работы и нет смысла "извращаться", пытаясь реализовать сложные и хитроумные алгоритмы. Необходимо помнить, что чем проще алго-
ритм (и это относится не только к алгоритмам сортировки), тем надежнее будет работать ваша программа. И только для очень больших файлов, когда именно на сортировке ваша программа "застревает", стоит поискать более сложные и быстрые алгоритмы.
Рассмотрим несколько алгоритмов сортировки. В примерах мы будем рас-
сматривать сортировку массивов целых чисел.
273
4.1 Алгоритмы сортировки
____________________________________________________________________
4.1.1 Обменная сортировка (метод "пузырька")
Свое название алгоритм получил благодаря тому, что в процессе сортиров-
ки меньшие (большие) числа как бы всплывают вверх как пузырьки воздуха в воде. Если идет сортировка по возрастанию, "всплывают" меньшие числа, если
по убыванию, то большие. Рассмотрим пример.
Пусть имеется массив, состоящий из четырех чисел: 4, 3, 2, 1. Необходимо
расположить элементы массива по возрастанию. Сравниваются, начиная с кон-
ца массива пары соседних чисел. Если они расположены в неправильном по-
рядке – меняем их местами. В результате первого прохода наименьший элемент
(число 1) оказывается "наверху", на месте нулевого элемента, т.е. самый "лег-
кий" элемент "всплыл на поверхность", рис. 4.1.
4 |
4 |
4 |
1 |
3 |
3 |
1 |
4 |
2 |
1 |
3 |
3 |
1 |
2 |
2 |
2 |
Рис. 4.1 Состояние массива во время первого прохода.
Как видно из рисунка, на первом шаге текущего прохода меняются мес-
тами числа "1" и "2". На втором шаге меняются "1" и "3" и на четвертом шаге
меняются местами "1" и "4".
Далее осуществляется второй проход, в котором просматриваются элемен-
ты массива, кроме первого, который уже "встал" на свое место. Состояние мас-
сива во время второго прохода, рис. 4.2: |
|
||||
|
|
|
|
||
|
1 |
|
1 |
|
1 |
4 |
4 |
2 |
|||
3 |
2 |
4 |
|||
2 |
3 |
3 |
|||
Рис. 4.2 Состояние массива во время второго прохода.
274
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
На рисунке элемент, который уже не участвует в просмотре, выделен.
На следующем (последнем для данного массива) проходе поменяются мес-
тами числа "4" и "3". В итоге получаем отсортированный массив:
1 |
|
1 |
2 |
|
2 |
4 |
3 |
|
3 |
4 |
|
Рис. 4.3 После третьего прохода получаем отсортированный массив.
Таким образом, проходы делаются по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сор-
тировка заканчивается, так как последовательность упорядочена по возраста-
нию. Блок-схема алгоритма сортировки методом "пузырька" приведена на ри-
сунке 4.4.
Составим программу с использованием динамических массивов. При раз-
боре программы не забудьте, что индексация элементов в таких массивах начи-
нается с 0!
program bubble_sort; uses
CRT, FileUtil; var
i, n: integer;
vector: array of integer;
{ ============= Сортировка методом "пузырька" ======== } procedure bubble(var vector: array of integer); var
temp: integer;
i, j, count: integer;
275