Сортировки включением

Сортировка прямым включением.Элементы условно разделяют на готовую a[1],...,a[i-1] и входную последовательности a[i],...,a[n]. Сначала i=2. На каждом шаге, увеличивая i на единицу, берут i-й элемент входной последовательности и передают в готовую последовательность, вставляя на подходящее место.

Итак, в начале рассматривается второй элемент (i=2) последовательности ключей. Он сравнивается с первым элементом (a[i-1]) и если он его меньше, то они меняются местами. В противном случае проход заканчивается, i увеличивается на 1 и процесс повторяется. Заметим, что упорядоченная последовательность a[i-1] называется готовой последовательностью и новый элемент вставляется в готовую последовательность на свое место.

На каждом проходе происходит перемещение i-того элемента в готовую последовательность, а некоторое число элементов сдвигается вправо. Данный процесс перемещения называется просачиванием элемента.

Здесь и далее, во всех процедурах сортировки ключи упорядочиваются по возрастанию. На входе процедур - количество элементов массива (n), на выходе - упорядоченный массив элементов(а).

Procedure Straight_Insertion(n:integer; Var a:t);

Var

i,j:word;

x:integer;

Begin

For i:=2 To n Do

begin

x:=a[i]; a[0]:=x; j:=i-1;

While x<a[j] Do

begin

a[j+1]:=a[j]; j:=j-1;

end;

a[j+1]:=x

end;

End;{Straight_Insertion}

Процедура упорядочивает элементы массива начиная с первого. Нулевой элемент используется процедурой как вспомогательный.

В основной программе массив необходимо объявить следующим образом:

TYPE

t=array[0..20] of integer;

VAR

A:t;

N,i:word;

Ввод массива:

FOR i:=1 to n do

Read(a[i]);

Вывод отсортированного массива:

FOR i:=1 to n do

Wrire(a[i],’ ‘);

Сортировка бинарными включениями.Алгоритм сортировки прямыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a[1],...,a[i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.

Procedure Binary_Insertion(n:word;Var a:t);

Var

i,j,k,r,m:word;

x:integer;

Begin

For i:=2 To n Do

begin

x:=a[i]; k:=1; r:=i-1;

While k<=r Do

begin

m:=(k+r) div 2;

If x<a[m] Then r:=m-1

Else k:=m+1

end;

For j:=i-1 DownTo l Do a[j+1]:=a[j];

a[k]:=x

end;

End; {Binary_Insertion}