Комбинаторные алгоритмы для программистов

         

Вставка


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

: на этапе
имя

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

.


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

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

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


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

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

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



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