Какие сортировки нужно знать?
На этой странице
Для собеседований важно понимать bubble/selection/insertion sort как учебные O(n^2) алгоритмы, merge sort как стабильный divide and conquer, quick sort как быстрый average-case алгоритм и особенности Array.prototype.sort() в JavaScript.
Вопрос
Какие алгоритмы сортировки нужно знать и чем они отличаются по сложности и стабильности?
Таблица
| Алгоритм | Average | Worst | Память | Что помнить |
|---|---|---|---|---|
| Bubble sort | O(n^2) | O(n^2) | O(1) | учебный |
| Selection sort | O(n^2) | O(n^2) | O(1) | ищет минимум |
| Insertion sort | O(n^2) | O(n^2) | O(1) | хорош на почти sorted |
| Merge sort | O(n log n) | O(n log n) | O(n) | stable, divide and conquer |
| Quick sort | O(n log n) | O(n^2) | O(log n) average | зависит от pivot |
Что значат столбцы таблицы
Stable (стабильная) сортировка не меняет порядок элементов с одинаковым ключом. Пример - сортируем пользователей по возрасту:
до: Аня 25, Борис 30, Вера 25
стабильно: Аня 25, Вера 25, Борис 30 (Аня осталась раньше Веры)
нестабильно: Вера 25, Аня 25, Борис 30 (тоже отсортировано, но порядок равных сломан)Это важно, когда сортируют в несколько проходов: сначала по имени, потом по возрасту - и ждут, что внутри одного возраста имена останутся по алфавиту. Array.prototype.sort в JavaScript стабилен начиная с ES2019.
In-place - сортировка меняет исходный массив и почти не использует дополнительную память (O(1) или O(log n) на рекурсию). Merge sort в обычной реализации не in-place: ему нужен временный массив O(n).
Память в таблице - дополнительная память помимо самого массива.
Что реально нужно уметь писать?
Минимальный набор:
- binary search;
- merge sort;
- quick sort;
- insertion sort;
- JS comparator для
sort.
Bubble sort обычно нужен только для объяснения идеи.
Зачем знать сортировки, если есть sort?
На практике в JS чаще используют:
nums.sort((a, b) => a - b)Но на интервью проверяют:
- понимание сложности;
- divide and conquer;
- mutation;
- comparator;
- стабильность;
- edge cases.
Что отвечать на собеседовании?
Нужно знать простые O(n^2) сортировки для понимания, merge sort как стабильный O(n log n) алгоритм с дополнительной памятью, quick sort как быстрый average-case алгоритм с worst case O(n^2), а также особенности JS sort: он мутирует массив и без comparator сортирует как строки.
Что важно помнить: частые ошибки
- Сортировать числа через
nums.sort()без comparator. - Говорить, что quick sort всегда
O(n log n). - Забывать память merge sort.
- Не знать, что JS
sortмутирует массив. - Не понимать stable sort.
Мини-шпаргалка
- Простые сортировки -
O(n^2). - Merge sort -
O(n log n), memoryO(n). - Quick sort - average
O(n log n), worstO(n^2). - JS
sortмутирует. - Numeric comparator:
(a, b) => a - b. toSortedвозвращает новый массив.