Сортировка вставками по шагам
Покажите отсортированный префикс после каждой вставки, число сдвигов и исходные номера равных элементов.
Ваш пример
Разбор примера
Отсортировано: 1, 3, 3, 5, 7
| Шаг | Состояние: число [исходный номер] | Длина готового префикса | Сдвигов на шаге |
|---|---|---|---|
| Начало | 7 [№1] · 3 [№2] · 5 [№3] · 3 [№4] · 1 [№5] | 1 | 0 |
| Вставка №2 | 3 [№2] · 7 [№1] · 5 [№3] · 3 [№4] · 1 [№5] | 2 | 1 |
| Вставка №3 | 3 [№2] · 5 [№3] · 7 [№1] · 3 [№4] · 1 [№5] | 3 | 1 |
| Вставка №4 | 3 [№2] · 3 [№4] · 5 [№3] · 7 [№1] · 1 [№5] | 4 | 2 |
| Вставка №5 | 1 [№5] · 3 [№2] · 3 [№4] · 5 [№3] · 7 [№1] | 5 | 4 |
- Перед каждой вставкой левый префикс уже отсортирован.
- Строго большие элементы сдвигаются вправо; равные остаются перед новым элементом.
- Сдвигов: 8. Строгих инверсий в исходном списке: 8.
- Чисел
- 5
- Сдвигов
- 8
- Стабильность
- Сохранена
Метод и условия расчёта
Вынимаем очередной элемент. Сдвигаем только строго большие значения, затем вставляем элемент в освободившееся место. Равные не меняют взаимный порядок.
Вопросы по теме
Как увидеть стабильность?
У каждого числа сохраняется исходный номер. Среди равных чисел номера остаются в исходном порядке.
Подходит для огромных массивов?
Это учебная трасса до 24 чисел. Сортировка вставками в худшем случае требует квадратичной работы.
Поиск и сортировка: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.