Какие алгоритмы сортировки вы знаете и чем они отличаются?
- Какой алгоритм сортировки самый быстрый?
- Сравните сортировку пузырьком, вставками, слиянием и быструю
- Какая сортировка используется в стандартных библиотеках?
Простые — пузырьком, вставками, выбором — O(n²); эффективные — слиянием, быстрая, пирамидальная — O(n log n). Отличаются худшим случаем, памятью и устойчивостью.
- Вставки хороши на почти отсортированных и малых массивах — O(n) в лучшем случае
- Быстрая — обычно самая быстрая на практике, но O(n²) в худшем; слияние — устойчиво, но O(n) памяти
А ещё В стандартных библиотеках — гибриды: Timsort (Python, Java для объектов), introsort (C++)
Подробно
| Алгоритм | Лучший | Средний | Худший | Память | Устойчива |
|---|---|---|---|---|---|
| Пузырьком | O(n) | O(n²) | O(n²) | O(1) | да |
| Вставками | O(n) | O(n²) | O(n²) | O(1) | да |
| Выбором | O(n²) | O(n²) | O(n²) | O(1) | нет |
| Слиянием | O(n log n) | O(n log n) | O(n log n) | O(n) | да |
| Быстрая | 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(1) | нет |
Как они работают в двух словах:
- пузырьком — соседние пары меняются местами, большие «всплывают» в конец;
- вставками — каждый элемент вставляется на место в уже упорядоченную левую часть; на почти отсортированных данных почти ничего не двигает;
- выбором — ищем минимум оставшейся части и ставим вперёд;
- слиянием — делим пополам, сортируем половины, сливаем;
- быстрая — выбираем опорный, раскладываем меньшие влево, большие вправо, сортируем части;
- пирамидальная — строим кучу и по одному извлекаем максимум.
Что используется на практике: Timsort (Python, Java для объектов) — слияние плюс вставки для коротких отрезков, отлично работает на частично упорядоченных данных и устойчив; introsort (C++ std::sort) — быстрая сортировка, которая при слишком глубокой рекурсии переключается на пирамидальную, а мелкие части досортировывает вставками. Java для примитивов использует быструю сортировку с двумя опорными.
Ответ на «какая самая быстрая» — зависит от данных: размера, степени упорядоченности, нужна ли устойчивость и сколько есть памяти.
Что хотят услышать
- Деление на простые O(n²) и эффективные O(n log n).
- Лучший, средний и худший случаи, память, устойчивость.
- Когда простая сортировка уместна (вставки на почти отсортированных).
- Что используют стандартные библиотеки.
Частые ошибки
- «Быстрая сортировка всегда O(n log n)».
- Не знать, что такое устойчивость сортировки.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗Пузырьковая сортировка — O(n log n), быстрая — O(n²)
- ✗Сортировка вставками всегда медленнее быстрой, даже на почти упорядоченных данных
- ✗Пирамидальная сортировка устойчива и не требует памяти
- ✓Простые — O(n²), эффективные (слиянием, быстрая, пирамидальная) — O(n log n)
Что спросят дальше
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.