Сортировка вставками: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «==Алгоритм== <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