Сортировка вставками
Строит слева отсортированную часть, добавляя по одному значению. Каждое новое значение вынимается и движется влево, пока не встретит меньшее.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- да
- да
Лучший случай: как растёт время с размером списка n, когда входные данные самые удобные для алгоритма.
Средний случай: обычный рост времени с n. При n² вдвое больше значений сортируются вчетверо дольше; n log n растёт намного медленнее.
Худший случай: рост времени на самых неудобных данных. Важно, когда скорость не должна падать никогда.
Память: сколько памяти нужно сверх самого списка. 1 значит несколько переменных, n значит копию списка.
Стабильное: равные значения сохраняют исходный порядок. Это важно, когда записи сортируют по одному полю.
Без дополнительной памяти: сортирует внутри самого списка, без второго списка.
- сравнение
- перемещение
- в руке
- отсортированная часть
- на окончательном месте
Пар не по порядку: 154 (в начале: 154) не по порядку упорядочены Обе оси: значения от меньшего к большему
Нажмите «Воспроизвести»: линии покажут, как растут затраты
Нажмите «Воспроизвести» или проходите алгоритм по шагам.
Пробел: воспроизведение или пауза. Стрелки влево и вправо: шаг. Home и End: в начало или в конец.
Попробуйте: Выберите почти отсортированный список. Сдвигать почти нечего, поэтому шагов совсем мало.
Как это работает
Левая часть всегда отсортирована. Вынимаем следующее значение, сдвигаем каждое большее значение отсортированной части на одну позицию вправо и ставим вынутое значение в освободившееся место. Так многие раскладывают карты в руке.
Когда стоит применять
Хороший выбор для коротких списков и для почти отсортированных: на них она очень быстрая. Библиотеки сортировки на практике применяют её к небольшим частям списка внутри более быстрых методов.