Программа состоит из отдельных разделов или блоков, которые долж­ны располагаться в следующем порядке: [ заголовок программы; ]

^{Лабораторная работа 14.
Упорядочивание (сортировка) массива}


В большинстве случаев, массивы применяются для хранения большого количества однотипной информации, создания и организации баз и банков данных и т.д. Во многих случаях номер (индекс) элемента в массиве не играет большой роли. Важно именно его значение, т.е. сама информация. Базы и банки данных, в свою очередь, необходимы не только для того, чтобы "складывать" в них информацию, но и для того, чтобы в любой мо­мент была возможность удобного и быстрого доступа к ней. В обычном "неотсортированном" массиве информацию найти можно, но только уже из­вестным Вам способом последовательного перебора-просмотра всех его элементов, до тех пор, пока нужный элемент не будет обнаружен. Этот самый простой метод обладает только одним, но очень существенным недос­татком - на поиск одного элемента уходит много времени. Все остальные методы поиска информации намного эффективнее, быстрее, но применяются только в упорядоченных, отсортированных массивах. Поэтому часто возни­кает задача об упорядочивании массива.


Рассмотрим простой случай такой задачи: дан числовой массив xl, х2, ... хn, элементы которого попарно различны; требуется переставить элементы массива так, чтобы после перестановки они были упорядочены в порядке возрастания: xl < х2 < ... < хn.


Существует несколько алгоритмов решения этой задачи. Мы рассмот­рим два наиболее популярных.


Алгоритм сортировки выбором


Очевидно, что первое место в массиве должен занять минимальный элемент массива, второе - наименьший из всех остальных, третий - наи­меньший из оставшихся и т.д.
Для этого необходимо выполнить следующую последовательность дейс­твий:
Определить минимальный элемент массива;
Поменять его местами с первым элементом;
Определить минимальный элемент среди оставшихся;
Поменять его местами со вторым элементом и т.д.;
Эта последовательность действий должна выполняться до тех пор, пока не будет определён последний минимальный элемент.


Всю операцию по упорядочиванию массива можно разбить на более простые задачи.


Первая - поиск минимального элемента. Предлагаемый фрагмент прог­раммы напомнит Вам, как это делается.


min:=m[l]; {допустим, что 1-й элемент - минимален}
t:=l; {и его номер =1}
FOR i:=l ТО 30 DO if m[i]buf:=m[t]; {замена}
m[t]:=m[i];
m[i]:=buf;
END;


Описанный метод сортировки массивов можно применять как для сор­тировки массивов по возрастанию, так и для сортировки массивов по убы­ванию. Для этого просто необходимо определять не минимальный элемент массива, а максимальный. В тексте программы это выражается заменой в некоторых местах знака "<" на знак ">".


Алгоритм пузырьковой сортировки


Алгоритм так называемой "пузырьковой" сортировки более оригинален и в большинстве случаев более эффективен. При использовании этого ал­горитма весь массив просматривается несколько раз подряд. При каждом таком просмотре сравниваются последовательно только соседние элементы массива: сначала первый со вторым, потом второй с третьим, и в конце предпоследний с последним. Если при сравнении окажется, что предыдущий элемент больше следующего, они меняются местами описанным выше спосо­бом. Так в результате одного последовательного просмотра элементы, значение которых больше, "всплывают" образно говоря на поверхность, т.е. ближе к концу массива. Если провести такой последовательный прос­мотр массива несколько раз, то "тяжёлые" элементы окончательно "всплы­вут" и массив окажется отсортированным. Остаётся нерешённым ещё один вопрос. Сколько раз необходимо выполнять такой просмотр? Ведь может оказаться, что и одного просмотра будет достаточно. Столько, сколько нужно для полной сортировки, т.е. пока при просмотре элементы не будут меняться местами. Для этого удобно организовать логическую переменную ind, и присваивать ей значение ложь в случае, если замена происходила хотя бы один раз. Если значением этой переменной останется истина, то просмотры необходимо прекратить.


Предлагаемый Вам ниже фрагмент программы реализован на основе ме­тода пузырьковой сортировки. Он выполняет полную сортировку массива состоящего из 40 элементов.


REPEAT
ind:=true; {предположим, что массив уже отсортирован}
FOR i:=l ТО 39 DO {цикл для организации просмотра}
if m[i]>m[i+l] then {сравнение двух соседних элементов}
begin
buf:=m[i]; {меняем соседние элементы местами}
m[i]:=m[i+l];
m[i+l]:=buf;
ind:=false; {как оказалось, массив неотсортирован}
end;
UNTIL ind; {выполняем просмотры пока ind=false}
Контрольные вопросы.


1 Опишите идею сортировки массива методом выбора и последовательность действий для его реализации на языке Turbo Pascal.
2 Опишите идею сортировки массива "пузырьковым" методом и последова­тельность действий для его реализации на языке Turbo Pascal.