Сортировка методом прямого включения

Сортировка методом прямого включения, так же как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов.

Сортировка методом прямого включения, как и все описанные выше, производится по шагам. На k - м шаге считается, что часть массива, содержащая первые k-1 элементов, уже упорядочена, то есть

а [1] ≤ а [2] ≤... ≤ a [k-1].

Далее необходимо взять k - й элемент и подобрать для него такое место в отсортированной части массива, чтобы после его вставки упорядоченность не нарушалась, то есть надо найти такое j (1 ≤ j ≤ k -1), что а [j] ≤ a[k] < a[j+1]. Затем вставить элемент а [k] на найденное место.

С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг.

Рассмотрим этот процесс на примере. Пусть требуется отсортировать массив из 10 элементов по возрастанию методом прямого включения

1 - й шаг

13 6 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, следовательно, его

нужно вставить на второе место.

3 - й шаг

6 8 13 11 3 1 5 9 15 7 Следующий элемент - 11. Он записывается в упорядоченную часть массива на третье место, так как 11 > 8, но 11 < 13.

4 - й шаг

6 8 11 13 3 1 5 9 15 7 Далее, действуя аналогичным образом,

определяем, что 3 необходимо записать на

первое место.

5 - шаг

3 6 8 11 13 1 5 9 15 7 По той же причине 1 записываем на первое

место.

6 - шаг

1 3 6 8 11 13 5 9 15 7 Так как 5 > 3, но 5 < 6 то место 5 в упоря-

доченной части - третье.

7 - шаг

1 3 5 6 8 11 13 9 15 7 Место числа 9 - шестое.

8 - шаг

1 3 5 6 8 9 11 13 15 7 Определяем место для предпоследнего

элемента 15. Оказывается, что этот эле-

мент массива уже находится на своем месте.

9 - шаг

1 3 5 6 8 9 11 13 15 7 Осталось подобрать подходящее место для

последнего элемента (7).

1 3 5 6 7 8 9 11 13 15 Массив отсортирован полностью.

Сейчас можно коротко описать фрагмент алгоритма сортировки методом прямого включения:

For k: = 2 To n Do

{ так как начинам сортировку с поиска подходящего места для a[2], i изменяется от 2 до n }

Begin

x: = a[k];

‘вставить x на подходящее место в a[1],..., a[k] ‘

End;

Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента x. Поступим следующим образом: будем просматривать элементы, расположенные левее x (то есть те, которые уже упорядочены), двигаясь к началу массива. Нужно просматривать элементы a[ j ], j изменяется от k-1 до 1. Такой просмотр должен закончиться при выполнении одного из следующих условий:

· найден элемент a[j] < x, что говорит о необходимости вставки x между a[j-1] и a[j].

· достигнут левый конец упорядоченной части массива, следовательно, нужно вставить x на первое место.

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

Программа сортировки методом прямого включения:

program n3; { Сортировка по убыванию }

const n=5;

type ar=array [1..n] of integer;

var i:integer;

a:ar;

procedure sorting3(var a:ar);

var i,j,x,k:integer;

begin

for k:=2 to n do

begin

x:=a[k]; j:=k-1;

while (j>0)and(x>=a[j]) do

begin

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

dec(j);

end;

a[j+1]:=x;

end;

end;

begin

writeln('Введите исходный массив:');

for i:=1 to n do read(a[i]);

sorting3(a);

writeln('Отсортированный массив:');

for i:=1 to n do write(a[i],' ');

writeln;

end.