Пузырьковая сортировка вставками.
Это модификация обменного варианта сортировки. В этом методе входное и выходное множества находятся в одной последовательности, причем выходное - в начальной ее части. В исходном состоянии можно считать, что первый элемент последовательности уже принадлежит упорядоченному выходному множеству, остальная часть последовательности - неупорядоченное входное. Первый элемент входного множества примыкает к концу выходного множества. На каждом шаге сортировки происходит перераспределение последовательности: выходное множество увеличивается на один элемент, а входное - уменьшается. Это происходит за счет того, что первый элемент входного множества теперь считается последним элементом выходного. Затем выполняется просмотр выходного множества от конца к началу с перестановкой соседних элементов, которые не соответствуют критерию упорядоченности. Просмотр прекращается, когда прекращаются перестановки. Это приводит к тому, что последний элемент выходного множества "выплывает" на свое место в множестве. Поскольку при этом перестановка приводит к сдвигу нового в выходном множестве элемента на одну позицию влево, нет смысла всякий раз производить полный обмен между соседними элементами - достаточно сдвигать старый элемент вправо, а новый элемент записать в выходное множество, когда его место будет установлено. Именно так и построен программный пример пузырьковой сортировки вставками - 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 |
43 48:90 39_ 9 56 40 41 75 72 | |
43 48 90:39_ 9 56 40 41 75 72 | |
39 43 48 90:_9 56 40 41 75 72 | |
_9 39 43 48 90:56 40 41 75 72 | |
_9 39 43 48 56 90:40 41 75 72 | |
_9 39 40 43 48 56 90:41 75 72 | |
_9 39 40 41 43 48 56 90:75 72 | |
_9 39 40 41 43 48 56 75 90:72 | |
Результат | _9 39 40 41 43 48 56 72 75 90: |
Таблица 3.8
Хотя обменные алгоритмы стратегии включения и позволяют сократить число сравнений при наличии некоторой исходной упорядоченности входного множества, значительное число пересылок существенно снижает эффективность этих алгоритмов. Поэтому алгоритмы включения целесообразно применять к связным структурам данных, когда операция перестановки элементов структуры требует не пересылки данных в памяти, а выполняется способом коррекции указателей (см. главу 5).
Еще одна группа включающих алгоритмов сортировки использует структуру дерева. Мы рекомендуем читателю повторно вернуться к рассмотрению этих алгоритмов после ознакомления с главой 6.
Дата добавления: 2016-07-22; просмотров: 1325;