Алгоритмы trainee
Какие сортировки знаешь?
Ответ
Простые O(n²): пузырёк (bubble), выбор (selection), вставка (insertion). Эффективные O(n log n): merge sort (через слияние), quick sort (через разбиение), heap sort (через кучу). Специфичные: counting sort O(n+k). При этом quick sort в худшем случае деградирует до O(n²), а merge sort требует O(n) доп. памяти.
Разбор: Пузырёк, выбор и вставка — это O(n²); merge, quick и heap sort — O(n log n); counting sort — O(n+k). Главные ловушки: quick sort в худшем случае деградирует до O(n²) (гарантию O(n log n) даёт merge/heap sort), merge sort требует O(n) доп. памяти, а quick sort сортирует in-place — в дистракторах эти свойства намеренно перепутаны.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.