Сортировка элементов одномерных массивов

Сортировка элементов одномерных массивов

Сортировка представляет собой процесс упорядочения элементов в массиве по возрастанию или убыванию, так чтобы

X[1] ≤ X[2] ≤ … ≤ X[n] или X[1] ≥ X[2] ≥ … ≥ X[n].

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

· Сортировка выбором;

· Сортировка обменом (пузырьковая);

· Сортировка вставкой.

Общее описание начальных условий всех трех представленных алгоритмов: дан одномерный целочисленный массив а[1..n].

Сортировка выбором

На каждом шаге выбирают минимальный элемент из имеющихся, и помещают его на первое место в своем блоке (оставшейся части массива)

for i := 1 to n - 1 do

begin

min := a[i];

im := i;

for j:=i+1 to n do

if a[j]<min then

begin

min:=a[j];

im:=j;

end;

a[im]:=a[i];

a[i]:= min;

end;

Сортировка обменом

На каждом шаге сравнивают между собой соседние элементы массива и помещают максимальный в паре на последнее место

for i := 1 to n-1 do

for j := 1 to n-i do

if a[j]>a[j+1] then {если текущий больше следующего, то}

begin

t:=a[j]; {меняем}

a[j]:=a[j+1]; { их }

a[j+1]:=t; {местами}

end;

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

Сортировка заключается в том, что сначала упорядочиваются первые два элемента, затем делается вставка третьего элемента в и процесс повторяется

for i := 2 to n do

begin

t:=a[i]; { сохраним 2 элемент}

j:=i-1; {предшествующий}

12 3 Следующая ⇒