0.1. Сортировка
Пусть имеется ряд чисел: 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 у нас самый большой, нам предстоит решить задачу сортировки для массива из 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]; {транзитного элемента c}
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] >=
>= a[2,1] >= a[2,2] >= …>= a[2,N] >=
>= a[3,1] >= a[3,2] >= …
Скачано с www.znanio.ru
Сортировка Пусть имеется ряд чисел: 8 2 5 4
А теперь представим, что это не трубка, а наш исходный массив, а вместо пузырьков поднимаются максимальные элементы
© ООО «Знанио»
С вами с 2009 года.
