Визуализатор сортировок онлайн
Смотри, как работают алгоритмы сортировки — по шагам, с подсветкой сравнений и обменов. Пять алгоритмов: пузырьковая, выбором, вставками, быстрая и сортировка слиянием.
Чем алгоритмы отличаются
- Пузырьковая, выбором, вставками — простые, но медленные на больших данных: O(n²).
- Быстрая и слиянием — O(n·log n), именно их используют на олимпиадах.
Зачем это нужно
Понимание, как устроена сортировка, — фундамент алгоритмики: без него не разобраться в бинарном поиске, префиксных суммах и множестве олимпиадных приёмов.
Разбор на примере
Пузырьковая сортировка массива [5, 1, 4]. Первый проход: сравниваем 5 и 1 — меняем местами, получается [1, 5, 4]; сравниваем 5 и 4 — меняем, получается [1, 4, 5]. Второй проход: 1 и 4 стоят правильно, 4 и 5 тоже — обменов не было, значит массив отсортирован и можно остановиться. На трёх элементах это 3 сравнения, на массиве из n элементов в худшем случае — примерно n²/2. Для n = 1000 это полмиллиона операций, для n = 100 000 — пять миллиардов, и решение не уложится в лимит времени.
Что выбирать на олимпиаде
Свою сортировку на олимпиаде почти никогда не пишут: в Python есть встроенная list.sort() и sorted() — это сортировка слиянием с оптимизациями (Timsort), O(n·log n). Знать простые алгоритмы всё равно нужно: их разбирают в школе, спрашивают на устных турах и по ним считают число сравнений в задачах на анализ алгоритмов.
Где сортировка нужна в задачах
Сортировка редко бывает целью — чаще это первый шаг. Отсортировал и пошли два указателя, поиск пары с нужной суммой, жадный выбор по возрастанию веса, поиск медианы, склейка отрезков. Если задача звучит как «выбрать максимально много непересекающихся», почти наверняка начинается она с сортировки.