- Вставляется
- Сравниваются
- Обменяны
- Отсортированная часть
Сортировка вставками
Сортировка вставками работает так, как многие раскладывают игральные карты в руке. Она держит в начале списка отсортированную часть, берёт следующее значение и сдвигает его назад мимо всех больших значений, пока оно не встанет на место. Запустите сортировку с любой скоростью или пройдите её по одному сравнению и следите за счётчиками сравнений, обменов и проходов. Нажмите «Пуск», чтобы посмотреть сортировку, или «Шаг» и «Назад», чтобы идти по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место. Плитки считают сравнения, обмены и проходы. Выберите число столбиков, начальный порядок или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.
Как это работает
- Выберите число столбиков и начальный порядок: случайный, почти отсортированный, обратный или с небольшим числом разных значений. Или введите свои числа.
- Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место сортировки.
- Попробуйте почти отсортированный список и обратный и сравните, сколько сравнений нужно каждому.
Как работает сортировка вставками
Первое значение само по себе уже отсортированная часть. Возьмите второе значение и сравните его с предыдущим; если предыдущее больше, поменяйте их местами и продолжайте сравнивать и менять, пока предыдущее значение не окажется не больше или значение не дойдёт до начала. Теперь первые два значения стоят по порядку. Сделайте то же с третьим значением, с четвёртым и так далее до конца списка.
Быстрая на почти отсортированных списках
Каждый проход останавливается на первом значении, которое не больше, поэтому значение, которое уже стоит близко к своему месту, обходится всего в одно-два сравнения. Отсортированному списку нужно n − 1 сравнений и ни одного обмена; обратному, худшему случаю, — по n(n − 1)/2 тех и других. Число обменов всегда равно числу инверсий в начальном списке, то есть пар в неправильном порядке. Поэтому сортировку вставками часто применяют для коротких или почти отсортированных списков, а также внутри более быстрых сортировок, чтобы досортировать небольшие куски.
Часто задаваемые вопросы
Как работает сортировка вставками?
Она строит отсортированную часть в начале списка. Каждый проход берёт следующее значение и сдвигает его назад мимо всех больших значений перед ним, пока оно не встанет на место. После k-го прохода первые k + 1 значений стоят по порядку, хотя более позднее значение ещё может быть вставлено между ними.
Сколько сравнений и обменов делает сортировка вставками?
Число обменов всегда равно числу инверсий в начальном списке: ноль для отсортированного списка, n(n − 1)/2 для обратного. Сравнений столько же, сколько обменов, плюс не больше одного на проход, то есть от n − 1 до n(n − 1)/2.
Почему сортировка вставками быстрая на почти отсортированных списках?
Потому что проход останавливается, как только встречает значение, которое не больше. Когда каждое значение стоит близко к своему окончательному месту, каждый проход короткий, и вся сортировка занимает время, близкое к n.
Устойчива ли сортировка вставками?
Да. Значение проходит только мимо строго больших значений, поэтому равные значения никогда не обгоняют друг друга и сохраняют исходный порядок.
Отправляются ли мои числа куда-нибудь?
Нет. Сортировка выполняется в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор