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