Сортировка вставками по шагам

Покажите отсортированный префикс после каждой вставки, число сдвигов и исходные номера равных элементов.

Ваш пример

От 1 до 24 целых чисел от−1000000 до 1000000. Разделители: пробел, запятая или точка с запятой; дроби не принимаются.

Разбор примера

Отсортировано: 1, 3, 3, 5, 7

Состояние после каждой завершённой вставки
ШагСостояние: число [исходный номер]Длина готового префиксаСдвигов на шаге
Начало7 [№1] · 3 [№2] · 5 [№3] · 3 [№4] · 1 [№5]10
Вставка №23 [№2] · 7 [№1] · 5 [№3] · 3 [№4] · 1 [№5]21
Вставка №33 [№2] · 5 [№3] · 7 [№1] · 3 [№4] · 1 [№5]31
Вставка №43 [№2] · 3 [№4] · 5 [№3] · 7 [№1] · 1 [№5]42
Вставка №51 [№5] · 3 [№2] · 3 [№4] · 5 [№3] · 7 [№1]54
  1. Перед каждой вставкой левый префикс уже отсортирован.
  2. Строго большие элементы сдвигаются вправо; равные остаются перед новым элементом.
  3. Сдвигов: 8. Строгих инверсий в исходном списке: 8.
Чисел
5
Сдвигов
8
Стабильность
Сохранена

Метод и условия расчёта

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

Вопросы по теме

Как увидеть стабильность?

У каждого числа сохраняется исходный номер. Среди равных чисел номера остаются в исходном порядке.

Подходит для огромных массивов?

Это учебная трасса до 24 чисел. Сортировка вставками в худшем случае требует квадратичной работы.

Поиск и сортировка: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.