Тема №13. Сортировка массивов
Тема №13. Сортировка массивов
Тема имеет исключительно важное значение
Первой серьезной задачей программирования, с которой сталкивается начинающий программист – это задача сортировки массива. Под сортировкой понимается упорядочивание элементов массива по возрастанию (или по убыванию) без создания копии массива (т.е. «на месте»).
Самый простой алгоритм – это линейная сортировка. Рассмотрим рис. 13.1.
Проведем последовательно сравнение первого элемента со всеми последующими, при если при очередном сравнении (например сразу 4 и 2) выяснится, что элементы стоят в «неправильном» порядке – переставим их местами, затем продолжим сравнение
(рис. 13.2). По окончании одного прохода, можно сказать, что в первом элементе массива находится минимальный элемент (Рис. 13.4).
Рис 13.1
Рис 13.2
Рис 13.3
Рис 13.4
Далее применим указанную процедуру к неотсортированному «остатку» массива (рис. 13.5) до тех пор, пока не переставим два последних элемента (рис. 13.6-13.7).
Рис 13.5
Рис 13.6
Рис 13.7
Рис 13.8
Алгоритм линейной сортировки очень прост, но не экономичен, среднее число просмотров и перестановок пропорционально квадрату числа элементов (точнее -N2 /2 ).
- 37 -
Приведем программу сортировки. Обратите внимание, что мы использовали массив в качестве параметра процедуры. Для этого необходимо создать тип Massiv (стр. 34). Часто для экономии памяти массив передают через var-параметр (стр. 32), даже если не предполагается его модифицировать в подпрограмме. Т.е. заголовок процедуры print мог бы выглядеть следующим образом:
procedure print (var m : Massiv); .
Program LinerSort;
Const N = 10; // Число элементов массива
Type Massiv = array [1..N] of integer; // Определение типа Massiv
procedure swap(var x,y: integer); // Перестановка элементов местами
var z : integer;
begin
z:=x; x:=y; y:=z;
end;
procedure print(m : Massiv); // Вывод массива
var i : integer;
begin
for i:=1 to N do write(m[i]:5);
writeln; // Новая строка
end;
// Переменные главной программы
var a : Massiv; i,j : integer;
begin
// Заполнение массива случайными числами в диапазоне от 0 до 99
for i:=1 to N do a[i]:=random(100);
print(a); // Вывод массива
for i:=1 to N-1 do // Внешний цикл до N-1 (обратите внимание!)
for j:=i+1 to N do // Внутренний цикл от i+1 (обратите внимание!) if (a[i]>a[j]) then swap(a[i],a[j]); // Перестановка элементов
print(a); // Вывод отсортированного массива
end.
Задание 13
1. Внимательно прочитать текст. Оформите сортировку массива в виде отдельной процедуры (здесь уже применение var-параметра будет обязательным). (2 балла)
2. Добавьте в процедуру сортировки операторы, которые позволил ли бы узнать сколько раз происходят перестановки в процессе сортировки. Выясните этот вопрос для N=10, 100, 1000.
(3балла) - 38 -