Пузырьковая сортировка вставками.

Это модификация обменного варианта сортировки. В этом методе входное и выходное множества находятся в одной последовательности, причем выходное - в начальной ее части. В исходном состоянии можно считать, что первый элемент последовательности уже принадлежит упорядоченному выходному множеству, остальная часть последовательности - неупорядоченное входное. Первый элемент входного множества примыкает к концу выходного множества. На каждом шаге сортировки происходит перераспределение последовательности: выходное множество увеличивается на один элемент, а входное - уменьшается. Это происходит за счет того, что первый элемент входного множества теперь считается последним элементом выходного. Затем выполняется просмотр выходного множества от конца к началу с перестановкой соседних элементов, которые не соответствуют критерию упорядоченности. Просмотр прекращается, когда прекращаются перестановки. Это приводит к тому, что последний элемент выходного множества "выплывает" на свое место в множестве. Поскольку при этом перестановка приводит к сдвигу нового в выходном множестве элемента на одну позицию влево, нет смысла всякий раз производить полный обмен между соседними элементами - достаточно сдвигать старый элемент вправо, а новый элемент записать в выходное множество, когда его место будет установлено. Именно так и построен программный пример пузырьковой сортировки вставками - 3.12.

{===== Программный пример 3.12 =====} Procedure Sort (var a : Seq); Var i, j, k, t : integer; begin for i:=2 to N do begin { перебор входного массива } {*** вх.множество - [i..N], вых.множество - [1..i] } t:=a[i]; { запоминается значение нового эл-та } j:=i-1; {поиск места для эл-та в вых. множестве со сдвигом} { цикл закончится при достижении начала или, когда будет встречен эл-т, меньший нового } while (j >= 1) and (a[j] > t) do begin a[j+1]:=a[j]; { все эл-ты, большие нового сдвигаются } j:=j-1; { цикл от конца к началу выходного множества } end; a[j+1]:=t; { новый эл-т ставится на свое место } end; end;

Результаты трассировки программного примера 3.11 представлены в таблице 3.8.

Шаг	Содержимое массива a
Исходный	48:43 90 39_ 9 56 40 41 75 72
1	43 48:90 39_ 9 56 40 41 75 72
2	43 48 90:39_ 9 56 40 41 75 72
3	39 43 48 90:_9 56 40 41 75 72
4	_9 39 43 48 90:56 40 41 75 72
5	_9 39 43 48 56 90:40 41 75 72
6	_9 39 40 43 48 56 90:41 75 72
7	_9 39 40 41 43 48 56 90:75 72
8	_9 39 40 41 43 48 56 75 90:72
Результат	_9 39 40 41 43 48 56 72 75 90: