Алгоритмы сортировки

Выбор sorting зависит от размера input, stability, memory, key range и почти отсортированности данных. Bubble и selection sort в основном учебные; insertion sort хорош для tiny или nearly sorted data; merge sort stable, но требует extra memory; quicksort fast on average; heap sort контролирует memory; counting sort требует bounded key range.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Интервьюеры могут не просить кодить каждый sort, но ожидают сравнение complexity, stability и объяснение, почему language built-in sort часто лучше в product code.

Типовые ошибки: Quicksort worst case может быть O(n squared). Counting sort не comparison sort и может тратить memory. Stable ordering важен, когда equal keys несут secondary data.

Чеклист:

• Упомяните time и space.
• Назовите stability.
• Проверьте key range.
• Предпочитайте built-in sort, если реализация не является задачей.