Алгоритмы сортировки: обзор
Сортировка — одна из самых изученных задач в программировании. Существуют десятки алгоритмов, но важно знать ключевые. Разберём четыре: пузырьковую, быструю, слиянием и встроенный .sort() — и поймём, когда что использовать.
🤔 Зачем вообще нужна сортировка
Мы сортируем данные постоянно, даже не замечая этого. Контакты в телефоне отсортированы по алфавиту. Письма в почте — по дате. Товары в магазине — по цене. Результаты поиска — по релевантности.
В программировании сортировка критически важна по двум причинам:
Отсортированный массив позволяет использовать бинарный поиск — O(log n) вместо O(n). Тысячи элементов находятся за 10 шагов.
Отсортированный список легче читать, анализировать и отображать пользователю. Таблицы, отчёты, графики — везде нужна сортировка.
Многие задачи (поиск дубликатов, нахождение медианы, слияние данных) решаются значительно проще на отсортированных данных.
📌 Факт: алгоритмы сортировки — самая изученная тема в информатике. Над ними работали лучшие умы полвека. Именно поэтому встроенные функции сортировки в современных языках невероятно оптимизированы.
📚 Четыре алгоритма, которые нужно знать
Мы изучим четыре алгоритма. У каждого — своя идея, своя сложность и свои ситуации применения. В этом уроке — обзор и сравнение. Каждый следующий урок разберёт один алгоритм детально с кодом и визуализацией.
Самый простой алгоритм для понимания. Сравниваем соседние элементы и меняем их местами — большие «пузырьки» постепенно всплывают вправо. Несколько проходов — массив отсортирован.
Плюсы: очень просто реализовать и объяснить. Минусы: медленно — O(n²). На практике почти не используется.
Стратегия «разделяй и властвуй»: выбираем опорный элемент (pivot), делим массив на «меньше» и «больше», рекурсивно сортируем каждую часть. Очень быстро на практике.
Плюсы: один из самых быстрых алгоритмов на практике, сортирует «на месте» (мало памяти). Минусы: O(n²) в худшем случае (при неудачном pivot).
Тоже «разделяй и властвуй», но иначе: делим массив пополам рекурсивно до одиночных элементов, потом сливаем обратно в правильном порядке. Стабильный результат.
Плюсы: O(n log n) гарантированно, стабильная сортировка (одинаковые элементы сохраняют порядок). Минусы: требует дополнительной памяти O(n).
JavaScript использует гибридный алгоритм TimSort (слияние + сортировка вставками). Написан на C++, оптимизирован за десятилетия, использует специфику процессора. Быстрее любой вашей реализации.
Используйте в реальном коде! Почти всегда это правильный выбор. Исключения — учебные цели или очень специфические требования.
🛠️ Встроенный .sort(): правильное использование
У встроенного .sort() есть одна ловушка, которую должен знать каждый JavaScript-разработчик.
// ⚠️ ЛОВУШКА: по умолчанию .sort() сортирует как строки!
const nums = [10, 9, 2, 21, 3];
console.log(nums.sort());
// [10, 2, 21, 3, 9] — НЕПРАВИЛЬНО для чисел!
// "10" < "2" как строка (т.к. "1" < "2")
// ✅ ПРАВИЛЬНО: передайте функцию сравнения
const nums2 = [10, 9, 2, 21, 3];
console.log(nums2.sort((a, b) => a - b));
// [2, 3, 9, 10, 21] — правильная числовая сортировка
// По убыванию:
console.log(nums2.sort((a, b) => b - a));
// [21, 10, 9, 3, 2]
// Сортировка объектов по полю:
const users = [
{ name: "Иван", age: 25 },
{ name: "Мария", age: 19 },
{ name: "Алексей", age: 31 }
];
users.sort((a, b) => a.age - b.age);
// [Мария(19), Иван(25), Алексей(31)]
// Сортировка строк по алфавиту:
const names = ["Яков", "Анна", "Борис"];
names.sort((a, b) => a.localeCompare(b));
// ["Анна", "Борис", "Яков"]⚠️ Важно помнить: .sort() сортирует массив на месте (мутирует его) и возвращает ссылку на тот же массив. Если нужна копия — используйте [...arr].sort() или arr.slice().sort().
🎯 Когда что использовать
Самый частый вопрос: «Если встроенный sort такой хороший, зачем знать остальные?» Хороший вопрос. Давайте разберёмся.
✅ Когда использовать .sort()
- Практически всегда в реальном рабочем коде
- Когда важна производительность и вы не пишете учебный пример
- Когда нет специальных ограничений по памяти или стабильности
- Для сортировки любых объектов с кастомным компаратором
📚 Зачем знать остальные алгоритмы
- Технические интервью — вас спросят о сложности, попросят реализовать «руками»
- Понимание trade-off'ов — когда быстрая лучше слияния и наоборот
- Специфические задачи — параллельная сортировка, сортировка потоков данных, ограниченная память
- Мышление алгоритмиста — паттерны divide & conquer применяются везде, не только в сортировке
💡 Аналогия: водитель знает, как работает двигатель — не чтобы самому его собирать каждый раз, а чтобы правильно эксплуатировать машину, понимать, что происходит, и грамотно общаться с механиком. Так же и алгоритмы сортировки.
📊 Таблица сравнения алгоритмов
Сохраните эту таблицу — она пригодится и для учёбы, и для интервью.
| Алгоритм | Лучший | Средний | Худший | Память | Стабильность |
|---|---|---|---|---|---|
| 🫧 Пузырьковая | O(n) | O(n²) | O(n²) | O(1) | ✅ Да |
| ⚡ Быстрая | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ Нет |
| 🔀 Слиянием | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ Да |
| 🏆 Array.sort() | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ Да |
📖 Стабильная сортировка — это сортировка, которая сохраняет относительный порядок одинаковых элементов. Важно, когда сортируете объекты по одному полю, а в них есть другие поля — порядок «одинаковых» элементов предсказуем.
🗺️ Что дальше в разделе
В следующих уроках мы разберём каждый алгоритм в деталях — с кодом, пошаговой визуализацией и практическими заданиями.
Пузырьковая сортировка — пошаговая визуализация, две оптимизации, код
Быстрая сортировка — divide & conquer, pivot, рекурсия
Сортировка слиянием — рекурсивное разбиение и слияние
Линейный и бинарный поиск — от O(n) до O(log n)
✅ Итоги урока
- Сортировка нужна для ускорения поиска, удобства отображения и упрощения других алгоритмов
- Пузырьковая — O(n²), простейшая, учебная. На практике не используется
- Быстрая — O(n log n) в среднем, очень быстрая на практике, сортирует «на месте»
- Слиянием — O(n log n) гарантированно, стабильная, требует доп. памяти
- Встроенный
Array.sort()— использует TimSort, быстрее любой вашей реализации .sort()по умолчанию сортирует как строки — всегда передавайте функцию сравнения для чисел!- В реальном коде — всегда
.sort(). Остальные алгоритмы — для понимания и интервью
В следующем уроке — первый алгоритм в деталях: пузырьковая сортировка с пошаговой визуализацией на примере [5, 3, 8, 1, 4]. 🫧
Алгоритмы сортировки: обзор
7 вопросов