Вставка

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

: на этапе имя

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

.

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

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

временно размещается в , и просматриваются имена ; они сравниваются с и сдвигаются вправо, если обнаруживается, что они больше . Имеется фиктивное имя , значение которого служит для остановки просмотра слева. На рис. 14.1 работа этого алгоритма проиллюстрирована на примере таблицы из пяти имен.

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

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

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

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

---