Информатика · объяснение и практика

Сортировка вставками: как элемент находит место в готовом префиксе

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Поиск и сортировка · Учебная карта

В маршруте Сортировки и сравнение строк · 10 тем

Главная мысль

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

Что уже известно перед очередным шагом

Пусть список содержит результаты измерений. Первый элемент сам по себе уже образует отсортированную часть длины один. Следующий шаг должен добавить к ней ровно один новый элемент. Правая часть списка пока не обязана быть упорядоченной: алгоритм не обещает завершить всю работу одной удачной вставкой.

Полезное утверждение, сохраняемое между шагами, называют инвариантом. Здесь перед обработкой позиции i элементы слева от неё уже отсортированы. Сдвиг больших значений освобождает место для очередного числа, не нарушая порядок остальных. После вставки отсортированный префикс становится на один элемент длиннее.

Прослеживаем сдвиги, а не угадываем результат

Возьмём числа 8, 3, 6, 3. Сначала тройка проходит перед восьмёркой: получается 3, 8, 6, 3. Затем шестёрка сдвигает только восьмёрку и занимает место между ними. На последнем шаге новая тройка пропускает вправо восьмёрку и шестёрку, но остаётся после прежней тройки.

Чтобы увидеть это различие, одинаковым числам присваивают исходные метки. Тройка А встретилась раньше тройки Б. При сравнении только по числовому значению итог должен сохранить А перед Б. Сдвиг при условии «больше или равно» разрушил бы эту договорённость, хотя сами числа в результате всё равно были бы отсортированы.

Пример

Исходно: 8, 3 А, 6, 3 Б. Итог: 3 А, 3 Б, 6, 8. Сдвигов по шагам: 1, 1, 2.

Всего четыре строгие инверсии: восьмёрка стоит перед тремя меньшими числами, а шестёрка — перед последней тройкой. Каждый сдвиг устраняет одну такую пару.

Почему почти готовый список обрабатывается легче

Если вход уже отсортирован, каждое новое число сразу остаётся на своём месте: больших предшественников нет. Если числа идут в обратном порядке, очередной элемент приходится проводить через всю готовую часть. Поэтому трудоёмкость зависит от исходного порядка, а худший случай растёт квадратично по длине.

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

От чтения к действию

А теперь — вы

В стабильной сортировке вставками новое число равно последнему элементу готового префикса. Что делать?

Частые вопросы

Готовый префикс включает ещё не обработанный элемент?

Нет. До шага он заканчивается перед текущей позицией, после успешной вставки увеличивается на один элемент.

Отсортированные числа доказывают стабильность?

Нет. Для проверки стабильности нужны метки или дополнительные данные у равных ключей.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться