Сортировка вставками — это один из самых интуитивно понятных алгоритмов сортировки. Он напоминает способ, которым мы раскладываем карты в руке, упорядочивая их по возрастанию или убыванию. Этот алгоритм особенно удобен для небольших массивов и обучающих примеров.
Что такое сортировка вставками?
Сортировка вставками — это алгоритм, который проходит по массиву, берет каждый элемент и вставляет его в соответствующую позицию в уже отсортированной части массива.
Как работает алгоритм?
- Начинаем с того, что считаем первый элемент массива уже отсортированным.
- Берем следующий элемент и сравниваем его с элементами отсортированной части массива.
- Сдвигаем элементы, которые больше текущего, вправо.
- Вставляем текущий элемент на его правильное место.
- Повторяем процесс для всех элементов массива.
Пример работы
Рассмотрим массив [9, 5, 1, 4, 3]:
- Первый шаг:Элемент 9 уже отсортирован. Переходим к 5.
Сравниваем 5 и 9. Сдвигаем 9 вправо и вставляем 5.
Результат: [5, 9, 1, 4, 3]. - Второй шаг:Переходим к 1.
Сравниваем 1 с 9 и 5, сдвигаем оба вправо.
Вставляем 1 на первое место.
Результат: [1, 5, 9, 4, 3]. - Третий шаг:Переходим к 4.
Сравниваем 4 с 9 и 5, сдвигаем их вправо.
Вставляем 4 между 1 и 5.
Результат: [1, 4, 5, 9, 3]. - Четвертый шаг:Переходим к 3.
Сравниваем 3 с 9, 5 и 4, сдвигаем их вправо.
Вставляем 3 между 1 и 4.
Результат: [1, 3, 4, 5, 9].
Реализация на Go
Эффективность алгоритма
Временная сложность:
- Лучший случай (массив уже отсортирован): O(n)O(n)O(n).
- Худший случай (массив отсортирован в обратном порядке): O(n2)O(n^2)O(n2).
Память:
- Алгоритм работает "на месте", поэтому использует O(1)O(1)O(1) дополнительной памяти.
Преимущества и недостатки
Плюсы:
- Простота реализации.
- Эффективен для небольших массивов.
- Хорошо работает для частично отсортированных данных.
Минусы:
- Не подходит для больших массивов из-за квадратичной временной сложности.
Заключение
Сортировка вставками — это удобный алгоритм для небольших задач или изучения основ алгоритмов. Несмотря на ограниченную производительность, его концепция активно используется в других, более сложных алгоритмах, таких как сортировка Shell.
Также у меня есть Telegram-канал, где я пишу намного чаще. Буду рад.