сортировка — работа за компьютером (11/21)

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

На практике вы реализуете устойчивую сортировку записей: сохраняете key, сдвигаете строго большие элементы и вставляете запись в готовый упорядоченный префикс.

Эксперимент

Сравните selection sort и insertion sort на упорядоченном, почти упорядоченном и обратном массивах. Проверяйте порядок, сохранение всех записей и устойчивость равных ключей.

Ключевой вывод

Сортировка вставками адаптивна: чем ближе данные к нужному порядку, тем меньше сдвигов.

Pascal

Сохраните key до цикла. Условие границы j >= 0 проверяйте раньше обращения к a[j].