Сравнения
Обмены
Проход

  • Вставляется
  • Сравниваются
  • Обменяны
  • Отсортированная часть

Подробнее о сортировке вставками

Сортировка вставками

Сортировка вставками работает так, как многие раскладывают игральные карты в руке. Она держит в начале списка отсортированную часть, берёт следующее значение и сдвигает его назад мимо всех больших значений, пока оно не встанет на место. Запустите сортировку с любой скоростью или пройдите её по одному сравнению и следите за счётчиками сравнений, обменов и проходов. Нажмите «Пуск», чтобы посмотреть сортировку, или «Шаг» и «Назад», чтобы идти по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место. Плитки считают сравнения, обмены и проходы. Выберите число столбиков, начальный порядок или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.

Как это работает

  1. Выберите число столбиков и начальный порядок: случайный, почти отсортированный, обратный или с небольшим числом разных значений. Или введите свои числа.
  2. Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место сортировки.
  3. Попробуйте почти отсортированный список и обратный и сравните, сколько сравнений нужно каждому.

Как работает сортировка вставками

Первое значение само по себе уже отсортированная часть. Возьмите второе значение и сравните его с предыдущим; если предыдущее больше, поменяйте их местами и продолжайте сравнивать и менять, пока предыдущее значение не окажется не больше или значение не дойдёт до начала. Теперь первые два значения стоят по порядку. Сделайте то же с третьим значением, с четвёртым и так далее до конца списка.

Быстрая на почти отсортированных списках

Каждый проход останавливается на первом значении, которое не больше, поэтому значение, которое уже стоит близко к своему месту, обходится всего в одно-два сравнения. Отсортированному списку нужно n − 1 сравнений и ни одного обмена; обратному, худшему случаю, — по n(n − 1)/2 тех и других. Число обменов всегда равно числу инверсий в начальном списке, то есть пар в неправильном порядке. Поэтому сортировку вставками часто применяют для коротких или почти отсортированных списков, а также внутри более быстрых сортировок, чтобы досортировать небольшие куски.

Часто задаваемые вопросы

Как работает сортировка вставками?

Она строит отсортированную часть в начале списка. Каждый проход берёт следующее значение и сдвигает его назад мимо всех больших значений перед ним, пока оно не встанет на место. После k-го прохода первые k + 1 значений стоят по порядку, хотя более позднее значение ещё может быть вставлено между ними.

Сколько сравнений и обменов делает сортировка вставками?

Число обменов всегда равно числу инверсий в начальном списке: ноль для отсортированного списка, n(n − 1)/2 для обратного. Сравнений столько же, сколько обменов, плюс не больше одного на проход, то есть от n − 1 до n(n − 1)/2.

Почему сортировка вставками быстрая на почти отсортированных списках?

Потому что проход останавливается, как только встречает значение, которое не больше. Когда каждое значение стоит близко к своему окончательному месту, каждый проход короткий, и вся сортировка занимает время, близкое к n.

Устойчива ли сортировка вставками?

Да. Значение проходит только мимо строго больших значений, поэтому равные значения никогда не обгоняют друг друга и сохраняют исходный порядок.

Отправляются ли мои числа куда-нибудь?

Нет. Сортировка выполняется в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор