Сортировка вставками: различия между версиями
Материал из Algocode wiki
Grphil (обсуждение | вклад) (Новая страница: «==Алгоритм== <b>Префиксом</b> длины $i$ будем называть первые $i$ элементов массива. Тогда пус...») |
Глеб (обсуждение | вклад) |
||
Строка 7: | Строка 7: | ||
Yet another [https://visualgo.net/nl/sorting красивая визуализация] (вкладка INS) | Yet another [https://visualgo.net/nl/sorting красивая визуализация] (вкладка INS) | ||
+ | ==Реализация== | ||
+ | |||
+ | <syntaxhighlight lang="C++" line='line'> | ||
+ | for (int i = 1; i < n; i++) { | ||
+ | for (int j = i; j > 0; j--) { | ||
+ | if (a[j - 1] < a[j]) { | ||
+ | break; | ||
+ | } | ||
+ | swap(a[j], a[j - 1]); | ||
+ | } | ||
+ | } | ||
+ | </syntaxhighlight> | ||
==Оценка времени работы== | ==Оценка времени работы== | ||
− | Так как каждое число перемещается влево не более $N$ раз, то время работы составляет $O(N^2)$. | + | Так как каждое число перемещается влево не более $N$ раз, а всего чисел - $N$, то время работы составляет $O(N^2)$. |
{{Автор|Полина Романченко|Romanchenko}} | {{Автор|Полина Романченко|Romanchenko}} | ||
[[Категория:Квадратичные сортировки]] | [[Категория:Квадратичные сортировки]] | ||
[[Категория:Конспект]] | [[Категория:Конспект]] |
Текущая версия на 08:51, 13 сентября 2019
Алгоритм
Префиксом длины $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