13.7. Сортировка

Пусть имеется ряд чисел: 8 2 5 4. Под сортировкой понимают их упорядочение по возрастанию (2 4 5 8) или убыванию (8 5 4 2). Сортировать можно и символы (по алфавиту или коду ASCII), и строки (как слова в словаре).

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

Задача. Задан массив из 100 произвольных положительных чисел. Отсортировать его по возрастанию.

Если мы не можем с ходу запрограммировать задачу, нужно подробно представить себе, в каком порядке мы решали бы ее вручную, без компьютера. Как бы мы сами сортировали 100 чисел? Мы бы запаслись пустым листом бумаги из 100 клеток. Затем нашли бы в исходном массиве максимальное число и записали его в самую правую клетку, а в исходном массиве на его месте записали бы число, меньшее самого маленького в массиве (в нашем случае подойдет 0). Затем нашли бы в изменившемся исходном массиве новое максимальное число и записали его на второе справа место. И так далее.

Вот программа для 10 чисел:

CONST N =10;

TYPE vector =array[1..N] of Word;

CONST massiv_ishodn :vector=(3,8,4,7,20,2,30,5,6,9); {Это исходный массив}

VAR massiv_rezult : vector; {Это наш пустой лист бумаги}

i :Word;

FUNCTION maximum (m:vector; N:Word; var Nomer_max: Word):Word;

{Это вспомогательная функция для поиска максимума в массиве}

VAR i,max:Word;

BEGIN

max :=m[1]; Nomer_max:=1;

{Это порядковый номер максимального элемента}

for i:=2 to N do if max<m[i] then begin max:=m[i]; Nomer_max:=i end;

maximum:=max

END;

PROCEDURE sortirovka (mass_ish:vector; N:Word; var mass_rez:vector);

{Основная процедура сортировки}

VAR i, Nom_max:Word;

BEGIN

for i:=1 to N do begin

mass_rez[N+1-i]:=maximum(mass_ish, N, Nom_max);

mass_ish[Nom_max]:=0

end {for};

END;

BEGIN

sortirovka (massiv_ishodn, N, massiv_rezult);

{Распечатываем отсортированный массив}

for i:=1 to N do Write (Massiv_rezult[i],' ');

END.

Функция maximum, кроме того, что сама имеет значение максимального элемента массива, выдает еще порядковый номер максимального элемента - Nomer_max. Это называется побочным эффектом функции.

Методов сортировки много. Приведенный метод - самый примитивный. Мало того что нам пришлось расходовать память на второй массив, для выполнения сортировки массива из 100 элементов понадобилось бы около 100 * 100 = 10000 операций сравнения элементов массива между собой.

Существуют методы гораздо более эффективные. Приведем один из них - метод пузырька. Представьте себе тонкую вертикальную трубку с водой. Запустим снизу пузырек воздуха. Он поднимется до самого верха. Затем пустим еще один. Он поднимется наверх и остановится сразу же под первым. Затем запустим третий, 100 и так далее все сто пузырьков.

Теперь представим, что это не трубка, а наш исходный массив, а вместо пузырьков поднимаются максимальные элементы.

Алгоритм такой: сравним первый элемент массива со, вторым, и если второй больше, то ничего не делаем, а если первый больше, то меняем местами первый и второй элементы. В этом вся соль метода. Затем повторяем это со вторым и третьим элементами. Если третий больше, то ничего не делаем, a если второй больше, то меняем местами второй и третий элементы. Затем повторяем все это с третьим и четвертым элементами и т. д. Таким образом, максимальный элемент, как пузырек, поднимется у нас до самого верха.

Теперь, когда мы знаем, что элемент номер 100 у нас самый большой, нам предстоит решить задачу сортировки для массива из 99 элементов. Запускаем второй пузырек и т. д.

Метод пузырька не требует второго массива, да и сравнений здесь в два раза меньше.

Вот программа:

CONST N =10;

TYPE vector =array[1..N] of Word;

CONST massiv :vector =(3,8,4,7,20,2,30,5,6,9);

VAR i :Word;

PROCEDURE puziryok (var mass:vector; Razmer:Word);

VAR i,m,c:Word;

BEGIN

for m:=Razmer downto 2 do begin {Всего пузырьков - 9}

for i:=1 to m-1 do begin

{i увеличивается - пузырек ползет вверх}

if mass[i]>mass[i+1] then begin {Стоит ли обмениваться значениями}

c:=mass[i];

{Три оператора для обмена значений двух элементов с помощью}

mass[i]:= mass[i+1];

{транзитного элемента с}

mass[i+1]:=c

end(if)

end{for};

end{for};

END;

BEGIN

puziryok (massiv,N);

for i:=1 to N do Write (massiv[i],''); {Распечатываем отсортированный массив}

END.

Задание 125

Отсортируйте по убыванию двумерный массив. Имеется в виду что:

a[1,1]>=a[1,2]>=...>=a[1,N]>=

>=а[2,1]>=а[2,2]>=...>=a[2,N]>=

>=а[3,1]>=а[3,2]>=...