Алгоритмы сортировки массивов
💻 Информатика · 11 класс
Зачем сортировать данные
Сортировка — это упорядочивание элементов массива по возрастанию или убыванию. Отсортированные данные легче искать, сравнивать и обрабатывать: например, в упорядоченном списке быстро работает двоичный поиск. В одиннадцатом классе разбирают несколько алгоритмов сортировки и сравнивают их по числу выполняемых действий.
Простые сортировки
- Сортировка пузырьком многократно проходит по массиву и меняет местами соседние элементы, если они стоят в неверном порядке. Большие значения постепенно всплывают к концу, как пузырьки.
- Сортировка выбором на каждом шаге находит минимальный элемент из ещё не упорядоченных и ставит его на очередное место.
- Сортировка вставками берёт очередной элемент и вставляет его в уже отсортированную часть на правильную позицию.
Разбор пузырька
Массив: 5 1 4 2
Проход 1: 1 4 2 5 (значение 5 всплыло в конец)
Проход 2: 1 2 4 5
Проход 3: 1 2 4 5 (перестановок нет, можно остановиться)
Итог: 1 2 4 5После прохода, в котором не было ни одной перестановки, массив уже упорядочен, и работу можно прекратить досрочно.
Быстрая сортировка
Быстрая сортировка выбирает опорный элемент и делит массив на две части: значения меньше опорного и значения больше опорного. Затем тот же приём рекурсивно применяют к каждой части. На практике этот метод работает значительно быстрее простых сортировок на больших массивах, поэтому именно он чаще всего применяется в реальных программах.
Устойчивость и выбор метода
Сортировку называют устойчивой, если она не меняет взаимный порядок элементов с одинаковыми значениями. Это важно, когда данные сортируют по нескольким признакам подряд, например список учеников сначала по классу, а потом по фамилии. Выбор алгоритма зависит от размера данных и требований к скорости.
- Для коротких массивов годятся простые сортировки — их легко запрограммировать без ошибок.
- Для больших массивов выбирают быструю сортировку или сортировку слиянием.
- Если данные почти упорядочены, сортировка вставками работает очень быстро.
Сравнение по скорости
Скорость оценивают числом сравнений при n элементах в массиве.
| Алгоритм | Среднее число действий | Скорость |
|---|---|---|
| Пузырёк | около n*n | медленный |
| Выбор | около n*n | медленный |
| Вставки | около n*n | средний |
| Быстрая | около n*log(n) | быстрый |
Частые ошибки. Выходят за границы массива, сравнивая последний элемент с несуществующим следующим. Забывают, что после прохода без перестановок массив уже отсортирован и цикл можно прервать. Путают сортировку по возрастанию и по убыванию, меняя знак сравнения.
Кратко о главном
- Сортировка упорядочивает элементы по возрастанию или убыванию.
- Простые методы — пузырёк, выбор, вставки — работают за число действий порядка
n*n. - Быстрая сортировка делит массив опорным элементом и работает быстрее.
- Алгоритмы сравнивают по числу действий при росте размера данных.