8) Метод сортировки массива вставками

8) Метод сортировки массива вставками

Идея: берём 1-ый элемент неупорядоченной части, ищем ему место в упорядоченной и вставляем. Изначально первые 2 элемента упорядочиваются отдельно.

sort

Not sort

Место для элемента ищется профессиональным правым бин-поиском.

Место для элемента – R, сама вставка – циклический сдвиг вправо от R до j

if a[1]> a[2]

then begin

t: =a[1];

a[1]: =a[2];

a[2]: =t;

end;

for j: =3 to N do begin

L: =0; R: =j;

while (R-L> 1) do begin

m: =(L+R) div 2;

if a[m] > a [j]

then R: =m

else L: =m

end;

e: =a[j];

for i: =j downto R+1 do

a[i]: = a[i-1];

a[R]: =t

end;