10.7. Сортировка элементов массива

Сортировкой называют процесс размещения элементов в некотором порядке (по возрастанию или по убыванию). Реализовать его проще в линейном массиве, поэтому предварительно любой другой массив необходимо трансформировать именно в линейный.

Наиболее простой метод сортировки получил название "метода пузырька". Допустим, сортировка выполняется по возрастанию в массиве из M элементов. Суть метода состоит в следующем. Сравниваются по величине первый и второй элементы массива. Если между ними правильный порядок - первый меньше второго, то они остаются на своих местах, а если неправильный, то они меняются местами. Затем сравнивается аналогичным образом второй и третий элементы, третий и четвертый и т.д. В результате однократного прохода по массиву описанным образом будет сделано (M-1) сравнений и в конце массива будет записан самый большой элемент.

Если была сделана хотя бы одна перестановка, то в индикатор перестановок F записывается единица (F=1) и процесс просмотра массива повторяется. Перед очередным проходом индикатор перестановок устанавливается в нулевое состояние (F=0). При повторном проходе по массиву будет сделано (M-2) сравнений, а найденный (второй по величине в массиве) элемент будет расположен предпоследним в массиве. При этом проход выполняется до M-2 элемента.

Если в результате первого или последующих проходов по массиву перестановок не было (F=0), то процесс сортировки заканчивается. Название "пузырька" метод получил потому, что при проходе сравниваются все пары элементов, и перестановки при выполнении условия выполняются со всеми парами. Движение наибольшего элемента осуществляется непрерывно в каждой паре до достижения самого верха для его значения. Это похоже на движение пузырька в жидкости. Он всплывают до своего предела.

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

Расположение элементов массива в процессе сортировки

Исходный массив	82, 4, 21, 7, 19, 16
Массив после первого прохода (F=1)	4, 21, 7, 19, 16, 82
Массив после второго прохода (F=1)	4, 7, 19, 16, 21, 82
Массив после третьего прохода (F=1)	4, 7, 16, 19, 21, 82
Массив после четвертого прохода (F=0)	4, 7, 16, 19, 21, 82

В предлагаемой программе используются следующие идентификаторы:

- D - сортируемый массив из 10 элементов;

- I – текущий номер сравнения;

- F - индикатор наличия перестановки (флажок): F=1, если перестановка была;

- NРROH – номер выполняемого прохода;

- М- количество элементов массива (длина массива);

- PROH – количество выполненных проходов, необходимое для сортировки;

- MAX – вспомогательная переменная для временного хранения элемента D[I] при перестановке.

Ячейка памяти MАХ обеспечивает временное хранение элемента D(I). Это вызвано следующим обстоятельством: если D[1]>D[2], то их необходимо поменять местами. Для этого D[1] пересылается в ячейку MAX, а элемент D[2] пересылается на место элемента D[1] в массиве D. После этого элемент D[1] из ячейки МAX записывается на место элемента D[2] в массиве D.

{ПРОГРАММА СОРТИРОВКИ МАССИВА ПО ВОЗРАСТАНИЮ}

PROGRAM SORT_VOZR;

VAR

D:ARRAY[1..10] OF INTEGER;

NPROH,M,I,F,MAX, PROH:INTEGER;

BEGIN

CLRSCR; {Очистка экрана}

WRITELN('ВВЕДИТЕМАССИВ D');

FOR I:=1 TO 10 DO READ(D[I]); {ВВОДМАССИВА D СКЛАВИАТУРЫ}

NPROH:=1; M:=10; F:=1; PROH:=0;

WHILE(NPROH<M)AND(F=1) DO {Выполнять до последнего прохода} {из всех возможных (M-1) или до} {отсутствия перестановок}

BEGIN

F:=0; {Сброс признака перестановки}

{БЛОК ВЫТАЛКИВАНИЯ В КОНЕЦ МАССИВА ОЧЕРЕДНОГО}

{ЭЛЕМЕНТА, МАКСИМАЛЬНОГО ИЗ ОСТАВШИХСЯ (M-NPROH) ЭЛЕМЕНТОВ}

FOR I:=1 TO M-NPROH DO

IF D[I]>D[I+1] THEN

BEGIN

MAX:=D[I]; {Перестановка через}

{вспомогательную переменную}

D[I]:=D[I+1];

D[I+1]:=MAX;

F:=1; {Установка признака перестановки}

END;

NPROH:=NPROH+1; PROH:=PROH+1;

WRITELN(‘F=’,F,’ NPROH=’,NPROH,’ PROH=’,PROH);

END;

WRITELN;

WRITELN('УПОРЯДОЧЕННЫЙ МАССИВ D:');

{ВЫВОД НА ЭКРАН МОНИТОРА ЭЛЕМЕНТОВ}

{УПОРЯДОЧЕННОГОМАССИВА D}

FOR I:=1 TO 10 DO WRITE(D[I], ' ');

WRITELN(‘PROH=’,PROH,’ NPROH=’,NPROH);

END.

В этом алгоритме из двух переменных PROH и NPROH можно оставить одну. По аналогии с рассмотренным можно разработать и программу сортировки по убыванию.