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

1. Цей метод звичайно використовують гравці в карти. Елементи (карти) умовно розділяються на впорядковану послідовність a₁,...,a_i-1 і вхідну послідовність a_i,...,a_n, яку потрібно впорядкувати. На кожному кроці, починаючи з другого, беруть поточний елемент невпорядкованої частини і передають у впорядковану  послідовність, уставляючи його на підходяще місце.  Вставка здійснюється “посуванням” елементів впорядкованої послідовності на певну кількість кроків вправо. Посування закінчується при виконання однієї з двох умов:

· знайдено елемент a_j із ключем меншим, чим ключ x (елемента, який впорядковується);

· досягнутий лівий кінець готової послідовності.

Оскільки наперед кількість таких “посувань” невідома, для практичної реалізації алгоритму доцільно застосувати цикл з передумовою. Застосування методу розглянемо на прикладі впорядкування масиву з 10 елементів. Елементи, що переміщувались вправо, виділимо кольором.

Вихідний масив:

44  55  12  42  94  18  06  67  32  13

Перший крок: переставляється елемент х=12

44  55  55  42  94  18  06  67  32  13

44  44  55  42  94  18  06  67  32  13

12  44  55  42  94  18  06  67  32  13

Другий  крок: переставляється елемент х=42

12  44  55  55  94  18  06  67  32  13

12  44  44  55  94  18  06  67  32  13

12  42  44  55  94  18  06  67  32  13

Третій  крок: переставляється елемент х=18

12  42  44  55  94  94  06  67  32  13

12  42  44  55  55  94  06  67  32  13

12  42  44  44  55  94  06  67  32  13

12  42  42  44  55  94  06  67  32  13

12  18  42  44  55  94  06  67  32  13

….

Процедуроа реалізації алгоритму має вигляд:

procedure straightinsertion (var a: massiv);

var

i,j: integer;

x: integer;

n1,n:integer;

begin

{границі масиву}

n1:= low(a);

n:= high(a);

{впорядкування}

for i:= n1+1 to n do

begin

x:=a[i];

j:=i-1;

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

  begin

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

  j:=j-1;

  end;

  a[j+1]:=x;

end;

end;