Внимание! Практически весь материал этой лекции был в видеолекции.
Если вы всё хорошо усвоили, просто пробегитесь глазами и переходите дальше.
Основная идея этого алгоритма — разделение нашего массива на две части, отсортированную и неотсортированную. На каждом шаге алгоритма число переходит от неотсортированной к отсортированной части.
![Алгоритмы сортировки. Сортировка вставками - 1](https://cdn.javarush.com/images/article/bea1ee30-626c-4ba6-a90b-41d43ae0411b/original.png)
Давайте на примере ниже разберем, как работает сортировка вставкой. До того, как мы начали, все элементы считаются неотсортированными.
![Алгоритмы сортировки. Сортировка вставками - 2](https://cdn.javarush.com/images/article/e97719bc-8c14-45d0-b81e-9a80db6d8c08/original.png)
Шаг 1. Возьмем первое неотсортированное значение (3) и вставим его в отсортированный подмассив. На этом шаге весь отсортированный подмассив, его начало и конец и будут этой самой тройкой.
![Алгоритмы сортировки. Сортировка вставками - 3](https://cdn.javarush.com/images/article/2498925e-08a5-4199-894e-9a42718b5c8d/original.png)
Шаг 2. Поскольку 3 < 5, мы вставим 5 в отсортированный подмассив справа от 3.
![Алгоритмы сортировки. Сортировка вставками - 4](https://cdn.javarush.com/images/article/f365d4eb-5dbf-4c63-b3a0-f5e3cabde46a/original.png)
Шаг 3. Теперь работаем над вставкой числа 2 в наш отсортированный массив. Сравниваем 2 со значениями справа налево, чтобы найти правильную позицию. Поскольку 2 < 5 и 2 < 3 и мы дошли до начала отсортированного подмассива. Следовательно, мы должны вставить 2 слева от 3. Для этого подвигаем 3 и 5 вправо, чтобы появилось место для двойки и вставляем её в начало массива.
![Алгоритмы сортировки. Сортировка вставками - 5](https://cdn.javarush.com/images/article/80b70552-74bd-417c-a39a-22fee35f9a41/original.png)
Шаг 4. Нам повезло: 6 > 5, поэтому мы можем вставить это число сразу за числом 5.
![Алгоритмы сортировки. Сортировка вставками - 6](https://cdn.javarush.com/images/article/fbfb1608-b7df-4d2b-af2a-cadbfd8f8544/original.png)
Шаг 5. 4 < 6 и 4 < 5, но 4 > 3. Следовательно, мы знаем, что 4 нужно вставить справа от 3.
Снова мы вынуждены подвинуть 5 и 6 вправо, чтобы создать лакуну для 4.
![Алгоритмы сортировки. Сортировка вставками - 7](https://cdn.javarush.com/images/article/5abe1836-531f-4600-9309-b1488fb84837/original.png)
Готово!
Обобщенный алгоритм:
Берем каждый неотсортированный элемент n и сравниваем его со значениями в отсортированном подмассиве справа налево, пока не определим подходящую позицию для n (то есть, в тот момент, когда находим первое число, которое меньше, чем n). Затем сдвигаем все отсортированные элементы, которые находятся справа от этого числа вправо, чтобы образовалось место для нашего n, и вставляем его туда, тем самым расширяя отсортированную часть массива.
Для каждого неотсортированного элемента n нужно:
- Определить место в отсортированной части массива, куда нужно вставить
n
- Сдвинуть отсортированные элементы вправо, чтобы сделать лакуну для
n
- Вставить n в образовавшуюся лакуну в отсортированной части массива.
А вот и код! Рекомендуем написать свою версию программы сортировки.
![Алгоритмы сортировки. Сортировка вставками - 8](https://cdn.javarush.com/images/article/99183afb-3b07-4a64-93f2-163f3c19fbde/original.png)
Асимптотическая сложность алгоритма
В самом плохом случае мы сделаем одно сравнение со вторым элементом, два сравнения с третьим и так далее. Таким образом, наша скорость равна O(n2)
.
В лучшем случае мы будем работать с уже отсортированным массивом. Отсортированная часть, которую мы строим слева направо без вставок и передвижений элементов займет время Ω(n)
.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ