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

Сортировка этим методом производится последовательно, шаг за шагом. На k-м. шаге считается, что часть массива, содержащая первые k — 1 элементов, уже упорядочена, то есть А [1] <= А [2] <=... <= А [k— 1]. Далее берется k -й элемент, и для него подбирается такое место в отсортированной части массива, что упорядоченность не нарушается. То есть требуется найти такое j (0 <= j < = k — 1), что A[ j ] <= A[k} < A [j + 1] (при j = 0 происходит только одно сравнение, если не использовать "барьерную" технику). Затем выполняется вставка элемента A [k] на место j, при этом происходит "сдвиг" массива (элементов с j -го по k — 1-й).
На каждом шаге отсортированная часть массива увеличивается. Всего потребуется выполнить N—1 шаг.
Рассмотрим этот процесс на примере. Пусть требуется отсортировать массив из 10 элементов по возрастанию.

1-й шаг. 13 б 8 11 3 1 5 9 15 7

Рассматриваем часть массива из одного элемента 13. Вставляем второй элемент массива 6 так, чтобы упорядоченность сохранилась. Так как 6 < 13, записываем 6 на первое место. Отсортированная часть массива содержит два элемента (6 и 13).

2-й шаг. 6 13 8 11 3, 1 5,9 15 7

Возьмем третий элемент массива 8 и подберем для него место в упорядоченной части массива. 8 > 6 и 8 < 13, следовательно, его место — второе.

Далее действуем аналогичным образом.

РЕАЛИЗАЦИЯ АЛГОРИТМА:

Procedure Sort;
Var k,j,x:Integer;
Begin
For k:=2 To N Do

Begin

x:=A[k]; j:=k-l;
While (j>0) And (x<A{j]) Do
Begin
A[j+l]:=A[j];Dec(j;);

End;
А[j+1]:=x;
End;
End;

ЭФФЕКТИВНОСТЬ АЛГОРИТМА:

Для массива, например, 1 2 3 4 5 6 7 8 потребуется N — 1 сравнение (напомним, что мы сортируем в порядке возрастания), а для массива 8 7 6 5 4 3 2 1 — N• (N — 1)/2, или C=O(N²).

ЗАДАНИЯ: I уровень:

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

III уровень:

1. 1. На момент вставки элемента с номером i элементы массива с номерами от 1 до i — 1 отсортированы. Выберем из них средний элемент (или один из двух средних) и сравним его с элементом А [i]. Если А [i] меньше этого элемента, то поиск места вставки следует продолжать в левой половине, иначе в правой половине отсортированного массива. Эта схема получила название сортировки бинарными вставками. Она предложена Дж. Мочли в 1946 году в одной из первых публикаций по методам компьютерной сортировка. Реализовать данный алгоритм.

2. 2. Д.Л. Шелл в 1959 году предложил следующую модификацию метода — "сортировку с убывающим шагом". Ее суть: дан массив из 8 элементов. Разделим его на 4 группы по 2 элемента, сортируем элементы в каждой группе. Затем группы увеличиваем в 2 раза, т.е. в каждой группе становится по 4 элемента, и выполняем для них сортировку. И, наконец, сортируем одну группу из 8 элементов. Реализовать данный алгоритм.