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

Элементы разделяются на две части – готовую последовательность а1,…,аi-1 и входную последовательность аi,…,an. На каждом шаге начиная с I:=2; и увеличивая I:=I+1 берут I-тый эл-т входной последовательности и передают в готовую посл-ть вставляя его на подходящее место.

Алгоритм.

For I:=2 to n do begin X:=a[I]; «вставить х на подходящее место в а1,…,аi» end;

При поиске подходящего места удобно передавать сравнение и пересылки, т. е. как бы просеивать х сравнивая его с очередным эл-том аj и либо вставляя х, либо пересылая аj направо и продвигаясь на лево. Такое просеивание может закончится при условиях 1) либо найден эл-т аj с ключом< чем ключ х

2) либо достигнут левый конец посл-ти.

Это типичный пример цикла с двумя условиями окончания поэтому можно применить известный метод барьера. Для этого установим барьер а0:=x

const n=20; type item= integer; index=0..n; var a:array [1..n] of item; I,j:index; x:item; 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;

Число сравнений ключей Сi при I-том просеивании составляет самое большое I-1, самое меньшее 1. Если предположить, что все сравнения равны вероятно i/2.

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

Не нашли, что искали? Воспользуйтесь поиском: