Вставка

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

: на этапе

имя

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

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

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

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

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

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

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

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

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

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

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

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

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

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