Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием. Например, если имеется массив целых а, то после сортировки по возрастанию должно выполняться условие:
а[1] <= а[2] <=…<= а[n]
где n – верхняя граница индекса массива.
Так как можно сравнивать переменные типов integer, real, char и string, то можно сортировать массивы этих типов.
Задача сортировки распространена в информационных системах и используется как предварительный этап задачи поиска, так как поиск в упорядоченном (отсортированном) массиве проводится намного быстрее, чем в неупорядоченном.
Существует много методов (алгоритмов) сортировки массивов, например:
1) Метод прямого выбора;
2) Метод прямого обмена;
3) Сортировка методом прямого выбора.
1) Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен:
1. просматривая массив от первого элемента, найти минимальный элемент и поместить его на место первого, а первый на место минимального.
|
|
2. просматривая массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй – на место минимального.
3. и так далее до предпоследнего элемента.
Пример алгоритма (рисунок И.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.