2. Сортировка массива
Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием. Например, если имеется массив целых а, то после сортировки по возрастанию должно выполняться условие:
а[1] <= а[2] <=…<= а[n]
где n – верхняя граница индекса массива.
Так как можно сравнивать переменные типов integer, real, char и string, то можно сортировать массивы этих типов.
Задача сортировки распространена в информационных системах и используется как предварительный этап задачи поиска, так как поиск в упорядоченном (отсортированном) массиве проводится намного быстрее, чем в неупорядоченном.
Существует много методов (алгоритмов) сортировки массивов, например:
Метод прямого выбора;
Метод прямого обмена;
Сортировка методом прямого выбора.
Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен:
просматривая массив от первого элемента, найти минимальный элемент и поместить его на место первого, а первый на место минимального.
просматривая массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй – на место минимального.
и так далее до предпоследнего элемента.
Пример алгоритма (рисунок И.1) и программы, сортирующей элементы массива по возрастанию.
Рисунок И.1 – Блок-схема программы сортирования элементов массива по возрастанию
program Primer;
const n=5; {описание константы}
var
a:array[1..n] of integer; {объявление одномерного массива}
i,j,min,buf,k:integer;
begin
writeln(‘введите элементы массива’);
for i:=1 to n do
readln(a[i]); {заполнение одномерного массива}
for i:=1 to n-1 do {сортировка}
begin
min:=i;
for j:=i+1 to n do
begin
if a[j]<a[min] then min:=j;
buf:=a[i];
a[i]:=a[min];
a[min]:=buf;
end;
end;
for k:=1 to n do write(a[k],’ ‘); {выво дмассива на экран}
readln;
end.
Сортировка методом прямого обмена (линейной сортировки).
В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим, и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением – к концу массива (тонут), поэтому этот метод иногда называют методом «пузырька». Это процесс повторяется на единицу меньше раз, чем элементов в массиве.
Примералгоритма (рисунок) и программы сортировки массива целых чисел по возрастанию методом «пузырька».
program Primer;
const n=5; {описание константы}
var
a:array[1..n] of integer; {объявление массива}
i,buf,k:integer;
begin
writeln(‘введите значения элементов массива’);
for i:=1 to n do readln(a[i]); {заполнение одномерного массива}
for i:=1 to n-1 do {сортировка}
begin
for k:=1 to n-1 do
begin
if a[k]>a[k+1] then
begin
buf:=a[k];
a[k]:=a[k+1];
a[k+1]:=buf;
end;
end;
end;
for k:=1 to n do write(a[k],’ ‘);
readln;
end.
Рисунок И.2 – Блок-схема программы сортирования элементов массива по возрастанию методом “пузырька”