Сортировка массива

Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием. Например, если имеется массив целых а, то после сортировки по возрастанию должно выполняться условие:

а[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.