Главная > Дискретная математика. Алгоритмы и программы
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

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

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

5.1. Сортировка вставками

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

Алгоритм 5.1. Сортировка вставками

(см. скан)

Сложность алгоритма определяется числом проверок условия в цикле. Сравнение для конкретного выполняется раз, где число элементов, больших и стоящих слева от него, это число инверсий, у которых второй элемент Числа составляют таблицу инверсий а так как то в худшем случае сортировка элементов потребует) сравнений. Сложность сортировки вставками является квадратичной.

1
Оглавление
email@scask.ru