Модели и структуры данных



         

Сортировки включением - часть 2


Затем выполняется просмотр выходного множества от конца к началу с перестановкой соседних элементов, которые не соответствуют критерию упорядоченности. Просмотр прекращается, когда прекращаются перестановки. Это приводит к тому, что последний элемент выходного множества "выплывает" на свое место в множестве. Поскольку при этом перестановка приводит к сдвигу нового в выходном множестве элемента на одну позицию влево, нет смысла всякий раз производить полный обмен между соседними элементами - достаточно сдвигать старый элемент вправо, а новый элемент записать в выходное множество, когда его место будет установлено. Именно так и построен программный пример пузырьковой сортировки вставками - 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:

Таблица 3.8

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


Содержание  Назад  Вперед