Сортировка методом прямого включения, так же как и сортировка методом
простого выбора, обычно применяется для массивов, не содержащих
повторяющихся элементов.
Сортировка методом прямого включения, как и
все описанные выше, производится по шагам. На k - м шаге считается, что
часть массива, содержащая первые k-1 элементов, уже упорядочена, то
есть
а [1] ≤ а [2] ≤ ... ≤ a [k-1].
Далее необходимо взять k - й
элемент и подобрать для него такое место в отсортированной части
массива, чтобы после его вставки упорядоченность не нарушалась, то есть
надо найти такое j ( 1 ≤ j ≤ k -1 ), что а [j] ≤ a[k] < a[j+1]. Затем
вставить элемент а [k] на найденное место.
С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг.
Сейчас можно коротко описать фрагмент алгоритма сортировки методом прямого включения:
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.