Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Сортировка вставками элементов относится к наиболее очевидным методам (алгоритм 5.1). Для компактности алгоритма вводится фиктивный элемент значение которого устанавливается равным Сортировка проходит цикл для для каждого элемент вставляется в свое правильное место среди При вставке элемент временно размещается в и просматриваются имена они сравниваются с и сдвигаются вправо, если обнаруживается, что они больше Имеется фиктивный элемент значение которого служит для остановки просмотра слева.
Алгоритм 5.1. Сортировка вставками
(см. скан)
Сложность алгоритма определяется числом проверок условия в цикле. Сравнение для конкретного выполняется раз, где число элементов, больших и стоящих слева от него, это число инверсий, у которых второй элемент Числа составляют таблицу инверсий а так как то в худшем случае сортировка элементов потребует) сравнений. Сложность сортировки вставками является квадратичной.