Алгоритмы основных методов сортировок

(Для всех случаев как пример рассмотрена сортировка чисел по возрастанию).

Алгоритм сортировки выбором.

Это метод сортировки на месте (в одном массиве). В массиве ищется минимальный элемент и переставляется на место первого элемента (а первый элемент – на место найденного минимального). Потом этот процесс повторяется, но массив рассматривается со второго элемента (первый уже на месте). Найденный минимальный элемент меняется местами со вторым. Это повторяется до (n–1)-го элемента (n-ый элемент автоматически окажется на месте). Примечание: при поиске минимального элемента нужно находить и запоминать его место – для перестановки элементов.

Пример алгоритма на языке Паскаль для массива А длиной N чисел:

for i:=1 to N-1 do

Begin

{ поиск места, где находится минимальный элемент}

imin:=i;

for j:=imin+1 to N do

if A[j]<A[imin] then

imin:=j;

{ перестановка i-го и минимального элементов}

r:=A[i];

A[i]:=A[imin];

A[imin]:=r;

end;

Алгоритм сортировки обменом.

Это также метод сортировки на месте (в одном массиве); некоторые алгоритмы этого метода носят название метода пузырька. Сравниваются два соседних элемента (первый и второй), если они в правильном порядке – ничего не делается, если порядок нарушен – они меняются местами. Потом этот процесс повторяется для второго и третьего элементов, и так до конца (n–1 и n-ый элементы). В результате самый большой элемент оказывается в самом конце (на n-ом месте). Затем весь этот процесс повторяется, но уже до n–1-го элемента (так как n-ый уже на месте); затем – до n–2-го и так всего n–1 раз. Тем самым n–1 элементов снизу окажутся упорядоченными, а следовательно и первый элемент тоже.

Пример:

for i:=1 to N-1 do

for j:=1 to N-i do

if A[j]>A[j+1] then {если два соседних элемента идут по убыванию}

begin { перестановка j-го и следующего элементов}

r:=A[j];

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

A[j+1]:=r;

end;

Алгоритм сортировки вставками.

Этот метод относится к сортировкам в двух массивах. Имеется два массива. Один заполнен неупорядоченными числами, второй – пустой. Из первого берется первое число и переписывается на первое место во второй массив. Берется второе число и сравнивается с переписанным во второй массив. Если уже записанное число больше второго, оно переписывается на одну позицию ниже (на второе место), а последнее взятое число – на место первого. Затем из исходного массива берется третье число и сравнивается со вторым из выходного массива. Если оно должно вставляться выше второго, второе переписывается на позицию ниже. Далее сравнение проводится с первым числом и, если вставляемое число больше или равно первому, оно записывается на место, освободившееся от второго числа, иначе первое переписывается на позицию ниже, а вставляемое – на его место. Процесс повторяется, пока не будут вставлены на нужные места во второй массив все числа из первого.

Пример:

for i:=1 to N do { каждый элемент массива А вставляем в массив В