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

Begin

Сортировка выбором (линейная сортировка)

Begin

Repeat

Begin

Begin

b:=a[i];

a[i]:=a[i-1];

a[i-1]:=b;

end;

Фрагмент программы, реализующий «пузырьковую» сортировку.

К – текущая длина массива, b - переменная для обмена элементов.

for k:=n downto 2 do

for i:=1 to k-1 do {k-1, чтобы не было выхода за границы массива}

if a[i]>a[i+1] then

b:=a[i];

a[i]:=a[i-1];

a[i-1]:=b;

end;

Одно из усовершенствований прямого алгоритма сортировки – это использование в качестве внешнего цикла оператора Repeat-until. Условием его завершения будет отсутствие обмена соседних элементов при просмотре массива. Для фиксации этого используем логическую переменную-флажок F, которая перед началом просмотра получает значение true и изменяет свое значение на false при обмене.

Фрагмент программы, реализующий усовершенствованную «пузырьковую» сортировку.

K:=n;

F:=true; {флажок, фиксирующий, был ли обмен элементов за проход}

for i:=1 to k-1 do

if a[i]>a[i+1] then

b:=a[i];

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

a[i+1]:=b;

f:=false; {обмен был}

end;

k:=k-1;

until f;

Этот вариант позволяет выполнять всего один лишний проход в случае, если массив уже отсортирован тогда, когда прямая сортировка будет выполнять N-1 проходов вне зависимости от состояния массива.

Принцип метода.Рассмотрим для случая сортировки по возрастанию массива длиной N. В массиве находится наибольший элемент и обменивается местами с последним. Затем из оставшихся N-1 элементов (номера от 1 до N-1) снова находится наименьший и обменивается с предпоследним и т.д. Проходов для поиска минимального элемента требуется N-1. Данный алгоритм также является n-квадратичным: внешний цикл выполняется n-1 раз, внутренний n/2 раз. Выполняется ½(n²-n) сравнений – столько же, сколько и в методе перестановок. По сравнению с ним сортировка выбором имеет лучшие показатели, т.к. количество перестановок значительно меньше.

Фрагмент программы, реализующий «линейную» сортировку.

К – текущая длина массива, b - переменная для обмена элементов.

for k:=n downto 2 do

imax:=1;

for i:=1 to k do

if a[i]>a[imax] thenimax:=I;

b:=a[k];

a[k]:=a[imax];

a[imax]:=b;

end;

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

Алгоритм состоит из N-1 проходов, каждый из которых включает 4 действия:

1. Взятие очередного i-го элемента из неотсортированной части и сохранение его в дополнительной переменной b.
2. Поиск позиции j в отсортированной части массива, в которую нужно вставить взятый элемент, чтобы не нарушить упорядоченность.
3. Сдвиг элементов массива от позиции I-1 до позиции j-1 вправо, чтобы освободить найденную позицию вставки.
4. Вставка взятого элемента в позицию j.

В отличие от «пузырьковой» сортировки и сортировки выбором количество сравнений зависит от исходной отсортированности массива. Если массив отсортирован, то сравнений N-1, в худшем – ½(n²-n). Число перестановок в лучшем случае 2(n-1), в среднем ¼(n²-n), в худшем ½(n²-n).

Дата добавления: 2014-03-11; просмотров: 351; Нарушение авторских прав

Мы поможем в написании ваших работ!