Алгоритмы сортировки (пузырёк, вставки, выбор)

Зачем это в ЕГЭ.
Задание 26 проверяет умение анализировать и сравнивать алгоритмы сортировки. Даёт 1 первичный балл. Встречается в ~30% реальных вариантов, часто с требованием определить количество операций или отследить состояние массива после определённого шага.

Главная идея.
Сортировка — это упорядочивание элементов по возрастанию/убыванию. Ключевое отличие алгоритмов — в эффективности (количестве сравнений и перестановок) и принципе работы. Для ЕГЭ важно понимать «механику» трёх основных методов: пузырька, вставки и выбора.

Алгоритм (чеклист).
1. Определить тип сортировки по характерным операциям.
2. Для пузырька: сравнивать соседние элементы, меняя их местами при неверном порядке.
3. Для вставки: брать элемент и вставлять в правильную позицию в уже отсортированной части.
4. Для выбора: находить минимальный/максимальный элемент и ставить его на текущую позицию.
5. Проверить, что массив отсортирован после завершения всех проходов.

Опоры (кратко).
- Количество сравнений пузырька: $\frac{n(n-1)}{2}$ в худшем случае.
- Вставки: лучше для почти упорядоченных массивов ($O(n)$ в лучшем случае).
- Выбора: всегда $O(n^2)$, но минимум перестановок.

Пример 1 (количество перестановок).
Шаг 1. Дан массив [5, 3, 8, 6]. Применяем пузырьковую сортировку.
Шаг 2. Сравниваем 5 и 3: меняем местами → [3, 5, 8, 6].
Шаг 3. Сравниваем 5 и 8: порядок верный.
Шаг 4. Сравниваем 8 и 6: меняем → [3, 5, 6, 8].
Шаг 5. Итого: 2 перестановки.

Пример 2 (состояние массива после шага).
Шаг 1. Массив [7, 4, 2, 9]. Сортировка выбором по возрастанию.
Шаг 2. Первый проход: минимальный 2, меняем с 7 → [2, 4, 7, 9].
Шаг 3. Второй проход: 4 уже на месте.
Шаг 4. Результат после 2 проходов: [2, 4, 7, 9].

Типичные ошибки.
1. Путаница в алгоритмах. Пузырёк — соседние элементы, выбор — поиск минимума.
2. Неправильный подсчёт операций. Например, неучёт уже отсортированных элементов.
3. Ошибки в индексах. Особенно при ручной трассировке.
4. Игнорирование стабильности. Вставка сохраняет порядок равных элементов, выбор — нет.

Дальше.
Разбери комбинированные задачи, где требуется сравнить эффективность методов для одного массива.