Вставка

Вставка - простейшая сортировка вставками проходит через этапы

$Вставка$

: на этапе

$Вставка$

имя

$Вставка$

вставляется на свое правильное место среди

$Вставка$

Рис. 14.1. Простая сортировка вставками, используемая на таблице из n = 5 имен. Пунктирные вертикальные линии разделяют уже отсортированную часть таблицы и еще не отсортированную

При вставке имя

$Вставка$

временно размещается в

$Вставка$

, и просматриваются имена

$Вставка$

; они сравниваются с

$Вставка$

и сдвигаются вправо, если обнаруживается, что они больше

$Вставка$

. Имеется фиктивное имя

$Вставка$

, значение которого

$Вставка$

служит для остановки просмотра слева. На рис. 14.1 работа этого алгоритма проиллюстрирована на примере таблицы из пяти имен.

Алгоритм 14.1. Простая сортировка вставками

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

$Вставка$

перестановок равновероятны) и лучшем.

Содержание раздела

Главная сайта