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



             

Вставка


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

j = 2,3,\ldots,n
: на этапе
j
имя
x_j

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

x_1,x_2,\ldots,x_{j - 1}
.

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

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

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

x_j
временно размещается в
X
, и просматриваются имена
x_{j - 1},x_{j - 2},\ldots,x_i
; они сравниваются с
X
и сдвигаются вправо, если обнаруживается, что они больше
X
. Имеется фиктивное имя
x_0
, значение которого
- \infty
служит для остановки просмотра слева. На рис. 14.1 работа этого алгоритма проиллюстрирована на примере таблицы из пяти имен.

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

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

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

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




Содержание  Назад  Вперед