Сортировка вставками.
На каждом шаге
алгоритма мы выбираем один из элементов входных данных и вставляем его на
нужную позицию в уже отсортированном списке, до тех пор, пока набор входных
данных не будет исчерпан. Метод выбора очередного элемента из исходного массива
произволен; может использоваться практически любой алгоритм выбора. Обычно (и с
целью получения устойчивого алгоритма сортировки), элементы вставляются по
порядку их появления во входном массиве.
Сказанное можно
записать следующим образом в псевдокоде:
Начало цикла для j от 2 до N
переместить M[j] на позицию i <= j такую, что
M[j] < M[k] для i<= k < j и
либо M[j] >= M[i-1], либо i=1
конец цикла
переместить M[j] на позицию i <= j такую, что
M[j] < M[k] для i<= k < j и
либо M[j] >= M[i-1], либо i=1
конец цикла
Время выполнения алгоритма зависит от входных данных: чем большее
множество нужно отсортировать, тем большее время выполняется сортировка. Также
на время выполнения влияет исходная упорядоченность массива. Так, лучшим
случаем является отсортированный массив, а худшим — массив, отсортированный в
порядке, обратном нужному. Временная сложность алгоритма при худшем варианте
входных данных — θ(n²).
Анализ
сложности – Королев-Миков страницы 122!!!
