Сортировка массива
💻 Информатика · 9 класс
Что такое сортировка
Сортировка массива — это перестановка его элементов так, чтобы они шли в определённом порядке: по возрастанию или по убыванию. Упорядоченные данные легче просматривать, в них быстрее искать нужный элемент, их удобнее сравнивать. Сортировка — одна из самых распространённых операций в программировании.
Сортировка обменом (пузырьковая)
Идея очень простая: соседние элементы сравнивают и, если они стоят в неправильном порядке, меняют местами. За один проход по массиву самый большой элемент «всплывает» в конец, словно пузырёк воздуха в воде. Проходы повторяют до тех пор, пока массив не станет полностью упорядоченным.
для i от 1 до n-1:
для j от 1 до n-i:
если a[j] > a[j+1] то обмен(a[j], a[j+1])
Внешний цикл задаёт число проходов, внутренний — сравнивает соседние пары. С каждым проходом «всплывший» элемент уже стоит на месте, поэтому область сравнения сокращается.
Разбор на примере
Отсортируем массив из трёх чисел по возрастанию методом обмена:
| Действие | Массив |
|---|---|
| начало | 5 2 4 |
| сравнили первые два, обмен | 2 5 4 |
| сравнили вторые два, обмен | 2 4 5 |
| второй проход, обменов нет | 2 4 5 |
После того как за целый проход не произошло ни одного обмена, можно быть уверенным, что массив отсортирован. На этом основана полезная оптимизация: если ввести признак, который сбрасывается при каждом обмене, то цикл можно прервать досрочно, как только за проход не случилось ни одной перестановки. Для почти упорядоченных данных это заметно ускоряет работу.
Устойчивость и направление сортировки
Чтобы отсортировать массив по убыванию, а не по возрастанию, достаточно поменять знак сравнения на противоположный — сам алгоритм остаётся тем же. Это удобно: один и тот же метод решает обе задачи. Важно также понимать, что результат сортировки не зависит от выбранного метода: и пузырьковая сортировка, и сортировка выбором приводят массив к одному и тому же упорядоченному виду, различаясь лишь числом сравнений и обменов, то есть скоростью работы на больших объёмах данных.
Сортировка выбором
В этом методе на каждом шаге ищут наименьший элемент среди ещё не отсортированных и ставят его на очередное место в начале. Затем переходят к следующей позиции. Принцип отличается от пузырьковой сортировки, но результат тот же — упорядоченный массив. Сортировка выбором делает меньше обменов, но столько же сравнений.
Частые ошибки. Выходят за границу массива при сравнении соседнего элемента; путают знак сравнения и сортируют не в ту сторону; выполняют обмен без вспомогательной переменной и теряют значение; делают лишние или, наоборот, недостаточные проходы по массиву.
Кратко о главном
- Сортировка упорядочивает элементы по возрастанию или убыванию.
- Пузырьковая сортировка меняет местами соседние элементы.
- Сортировка выбором ставит на место наименьший элемент.
- Обмен значений требует вспомогательной переменной.
- Если за проход обменов не было, массив уже отсортирован.