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

Алгоритм

Префиксом длины $i$ будем называть первые $i$ элементов массива.

Тогда пусть на $i$-ом шаге у нас уже будет отсортирован префикс до $i$-го элемента. Чтобы этот префикс увеличить, нужно взять элемент, идущий после него, и менять с левым соседом, пока этот элемент наконец не окажется больше своего левого соседа. Если в конце он больше левого соседа, но меньше правого - это значит, что мы правильно вставили этот элемент в отсортированную часть массива.

Yet another красивая визуализация (вкладка INS)

Реализация

1 for (int i = 1; i < n; i++) {
2     for (int j = i; j > 0; j--) {
3         if (a[j - 1] < a[j]) {
4             break;
5         }
6         swap(a[j], a[j - 1]);
7     }
8 }

Оценка времени работы

Так как каждое число перемещается влево не более $N$ раз, а всего чисел - $N$, то время работы составляет $O(N^2)$.

---

Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko