А) Пузырьковая сортировка или сортировка простым обменом

Принцип метода:

Поочередно, начиная с 1-го элемента, сравниваем два соседних элемента

A[i]>A[i+1]

если данное условие истинно, то меняем местами эти два элемента

X:=A[i];

A[i]:=A[i+1];

A[i+1]:=X;

И далее берутся два следующие соседних элемента и так далее до N-к-го элемента.

После одного такого прохода на последней N-ой позиции массива будет стоять максимальный элемент (“всплыл” первый “пузырек”). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход выполняется до N-1-го элемента.

И так далее до N-1 проходов.

Алгоритм сортировки простым обменом:

Program Obmen;

Var K,I,J,Buf:Integer;

A : array[1..20] of Integer;

begin

For K:=1 to N-1 do {количество проходов}

{* ”Всплывание” очередного элемента на последнюю позицию*}

For I:=1 to N-K do

begin

If A[I] > A[I+1] then

begin

Buf:=A[I];

A[I]:= A[I+1];

A[I+1]:=Buf

end

end.

Б) Сортировка извлечением (выбором минимального элемента).

Общая концепция методов извлечения заключается в следующем: из исходного массива сначала извлекается минимальный элемент, затем из оставшихся элементов выбирается минимальный элемент и т. д., последний раз минимальный элемент выбирается из двух оставшихся элементов. Различные алгоритмы извлечения отличаются тем, какой элемент выбирается (min или max) и с каким элементом выбранный элемент меняется местами.

Ниже приведён алгоритм сортировки методом извлечения:

Пусть нужно упорядочить некоторый массив a[1], a[2],…, a[n] по неубыванию.

Program Vibor;

Var I,J,Buf:Integer;

A : array[1..20] of Integer;

begin

For I:=1 to N-1 do

For J:=I+1 to N do

If A[J] < A[I] then

begin

Buf:=A[I];

A[I]:= A[J];

A[J =Buf]

end

end.

В) Сортировка вставкой (включение).

Массив разделяется на две части: отсортированную и не отсортированную. Элементы из не отсортированной части массива поочередно выбираются и вставляются в отсортированную часть массива так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве не отсортированной части – все остальные элементы.

Для расстановки элементов необходимо выполнить следующие действия:

· сохранение очередного j-го не отсортированного элемента в дополнительной переменной d: d:=A[j];

· цикл осуществляет поиск места вставки j-го элемента и высвобождает это место для вставки, т. е. сдвигает все элементы массива, начиная от i-го элемента вправо^ A[i+1]:=A[i];, с шагом i:=i-1; , до тех пор пока будет истинным условие d<A[i];

ProgramVstavka;

Var I,J,D:integer;

A : array[1..20] of Integer;

Begin

ForJ:=2toNdo

Begin

{****Сохранение не отсортированного элемента****}

D:=A[J];

I:=J-1;

{****Цикл поиска места вставки и сдвигает элементы для освобождения места вставки ****}

while d<A[i] do

begin

A[i+1]:=A[i];

i:=i-1;

end;

{****Вставка сохраненного элемента в найденную позицию****}

A[i+1]:=d;

End;

End.

с) Метод попарного сравнения и метод попарного сравнения с часовым (методы: “Дробинки” и ”Дробинки с флагом”).

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

Ниже приведён алгоритм сортировки данными способами:

а) “Дробинки”.

ProgramDrobinka;

Var I,J,Q:integer;

F : array[1..20] of Integer;

begin

ForI:=1toN-1do

ForJ:=1toN-Ido

begin

IfF[J]>F[J+1]then

begin

Q:=F[J];