Сортировка выбором
💻 Информатика · 9 класс
Как упорядочить массив, на каждом шаге выбирая минимальный элемент из оставшихся.
Что такое сортировка выбором
Сортировка выбором — это алгоритм упорядочивания массива, в котором на каждом шаге из неотсортированной части выбирается минимальный элемент и ставится на своё место в начале. Постепенно отсортированная часть растёт слева, а неотсортированная уменьшается справа.
Идея проста: сначала находим наименьший элемент всего массива и меняем его местами с первым. Затем находим наименьший из оставшихся и ставим вторым. И так до конца массива.
Алгоритм по шагам
для i от 1 до n-1:
мин := i
для j от i+1 до n:
если A[j] < A[мин]: мин := j
поменять A[i] и A[мин]Внешний цикл задаёт позицию, на которую ставим минимум. Внутренний цикл ищет номер минимального элемента среди оставшихся. После каждого шага один элемент встаёт на своё окончательное место.
Разбор на примере
Отсортируем массив 5, 3, 8, 1 по возрастанию.
| Шаг | Минимум из оставшихся | Состояние массива |
|---|---|---|
| Начало | — | 5, 3, 8, 1 |
| 1 | 1 | 1, 3, 8, 5 |
| 2 | 3 | 1, 3, 8, 5 |
| 3 | 5 | 1, 3, 5, 8 |
На первом шаге минимум 1 поменялся местами с 5. На втором минимум 3 уже стоял на месте. На третьем 5 поменялась с 8, и массив стал упорядоченным.
Особенности алгоритма
- Число сравнений не зависит от того, был ли массив уже частично упорядочен.
- Обменов делается мало — не больше одного на каждый шаг внешнего цикла.
- Алгоритм относится к квадратичным: для
nэлементов число сравнений околоn*n/2.
Частая ошибка: запоминать само значение минимума, а не его номер. Для обмена нужен именно индекс (позиция) минимального элемента, иначе непонятно, какие ячейки менять местами.
Сортировка по убыванию
Чтобы упорядочить массив по убыванию, достаточно на каждом шаге искать не минимум, а максимум из оставшейся части и ставить его в начало. Сам алгоритм при этом не меняется — заменяется только знак сравнения внутри внутреннего цикла. Это показывает, что небольшая правка условия позволяет получить противоположный порядок.
Когда подходит
Сортировка выбором проста и наглядна, поэтому её часто изучают первой. Она удобна, когда обмены дорогие, а сравнения дешёвые, ведь обменов здесь минимум. Для больших массивов используют более быстрые методы, но для учебных задач и небольших данных сортировки выбором достаточно. Понимание этого алгоритма помогает затем разобраться и в более сложных способах упорядочивания данных.
Кратко о главном
- На каждом шаге выбирается минимум из неотсортированной части и ставится на своё место.
- Отсортированная часть растёт слева, неотсортированная уменьшается справа.
- Для обмена нужен индекс минимума, а не его значение.
- Алгоритм квадратичный, число сравнений около
n*n/2.