#Основные алгоритмы сортировки
#Пузырьковая сортировка (Bubble Sort)
- Принцип: многократно проходит по массиву, меняя местами соседние элементы если они в неверном порядке
- Сложность: O(n²) в среднем и худшем случае
- Особенности: неэффективна на практике, используется только для обучения
- В Python: не используется,
sorted() использует Timsort
#Сортировка слиянием (Merge Sort)
- Принцип: делит массив пополам до единичных элементов, затем сливает отсортированные части
- Сложность: O(n log n) во всех случаях
- Особенности: стабильная (сохраняет порядок равных элементов), требует O(n) дополнительной памяти
- В Python:
sorted() и list.sort() используют Timsort (гибрид merge sort + insertion sort)
#Быстрая сортировка (Quicksort)
- Принцип: выбирает опорный элемент (pivot) и разделяет массив на две части
- Сложность: O(n log n) в среднем, O(n²) в худшем случае
- Особенности: на практике часто быстрее merge sort из-за cache locality
- Улучшения: случайный pivot (randomized quicksort), median-of-three, 3-way partition для дубликатов
#Выбор алгоритма сортировки
При выборе алгоритма сортировки учитывайте:
-
- Малые массивы (< 50 элементов): insertion sort может быть эффективнее
- Большие массивы: merge sort или quicksort
-
Требования к стабильности
- Нужна стабильность (сохранение порядка равных элементов): merge sort
- Стабильность не важна: quicksort
-
- Ограничена память: in-place алгоритмы (quicksort, heap sort)
- Дополнительная память доступна: merge sort
-
- Уже частично отсортированные: insertion sort или Timsort
- Много дубликатов: 3-way quicksort
- Худший случай критичен: merge sort (гарантированная O(n log n))
#Практические рекомендации
- В большинстве случаев используйте встроенные функции сортировки (
sorted(), list.sort())
- Для специфических задач реализуйте подходящий алгоритм
- Учитывайте особенности языка программирования (например, в Python Timsort оптимизирован для реальных данных)
- Тестируйте производительность на ваших данных, а не полагайтесь только на теоретическую сложность