title | weight |
---|---|
Сортировка вставками |
3 |
Пусть на
void insertion_sort(int *a, int n) {
for (int k = 1; k < n; k++)
for (int i = k; i > 0 && a[i - 1] < a[i]; i--)
// мы ещё не дошли до начала массива и предыдущий элемент меньше
swap(a[i], a[i - 1]);
}
Время работы в худшем случае тоже квадратичное — например, когда массив упорядочен по убыванию.
Однако, в отличие от двух предыдущих квадратичных сортировок, в некоторых хороших случаях время работы может быть меньше, потому что мы добавили условие ранней остановки во внутреннем цикле. Например, алгоритм сделает
Упражнение. Покажите, что алгоритм делает