Алгоритмы с нуля
Сортировка и поиск: тест с выбором
Суть Синтез по всему юниту в формате выбора: когда сортировка окупается, stable-сортировки, merge sort против quicksort, инвариант binary search и бинарный поиск по ответу.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеШесть вопросов через весь юнит. Каждый — это решение, которое вы принимаете, когда берётесь за сортировку или поиск в реальном коде: не определение для пересказа, а компромисс, который надо взвесить.
Цель
Убедитесь, что вы связываете стержень юнита: сортировка — это препроцессинг, за который платят один раз; сортировки за O(n log n) меняют stable-свойство на память и худший случай; а binary search обобщается с массивов на любое монотонное пространство ответов.
Викторина
Completed
Вам пришёл неотсортированный массив из 1 000 000 элементов, и нужно ответить ровно на один запрос: есть ли в нём значение X? Какой подход дешевле всего и при этом корректен?
Heads-up Для одного запроса O(n log n) сортировки плюс O(log n) поиска строго хуже одного прохода за O(n). Сортировка — это препроцессинг: она окупается, только когда амортизируется по многим последующим запросам.
Heads-up Построение множества — это тоже O(n), тот же порядок, что и проход, плюс лишняя память и никакой выгоды для одного поиска. Смысл в том, что любой препроцессинг впустую для единственного запроса.
Heads-up Binary search требует отсортированного массива. На неотсортированном входе он отбрасывает не ту половину и возвращает неверные ответы — отсортированность это его предусловие.
Викторина
Completed
Вы сортируете список заказов по сумме, где несколько заказов имеют одинаковую сумму, и нужно, чтобы при равенстве сохранялся исходный порядок поступления. Какая сортировка безопасна?
Heads-up Скорость не имеет отношения к stable-свойству. Quicksort с partition по схеме Lomuto может переставлять равные ключи, перекидывая их через границу pivot; он не stable.
Heads-up Selection sort тоже не stable: перенос минимума на место может перепрыгнуть один равный элемент через другой, ломая порядок поступления. Stable-варианты — insertion sort и merge sort.
Heads-up Stable-свойство не зависит от сложности. Merge sort (O(n log n)) — stable; quicksort и heapsort (тоже O(n log n)) — нет. Выбирать надо алгоритм, а не только асимптотику.
Викторина
Completed
Merge sort и quicksort оба O(n log n) в среднем. Для сортировки огромного массива на месте при жёстком ограничении по памяти и без требования stable — почему quicksort часто выбирают в продакшене?
Heads-up Всё наоборот: merge sort всегда O(n log n), а quicksort деградирует до O(n²) на плохих pivot. Quicksort выигрывает по памяти и константам, а не по худшему случаю.
Heads-up Stable — это как раз merge sort. Причина предпочесть quicksort — это O(n) буфер merge sort, а не какая-либо проблема со stable-свойством.
Heads-up Quicksort тоже рекурсивен; на сбалансированных partition он тратит O(log n) стека. Преимущество — partition на месте против O(n) вспомогательного массива merge sort.
Викторина
Completed
Quicksort, который всегда берёт последний элемент как pivot, нормально работает на случайных данных, но тратит минуты на уже отсортированных. Почему и как это стандартно чинят?
Heads-up Сравнения стоят столько же; проблема в форме partition. Фиксированный последний pivot на отсортированных данных всегда экстремален и даёт максимально несбалансированную рекурсию O(n²).
Heads-up Он сортирует корректно — просто медленно. Результат верный; вырождается рекурсия, превращая O(n log n) в O(n²).
Heads-up Никакого молчаливого перезапуска нет; глубокая рекурсия может переполнить стек, но суть в работе O(n²) из-за несбалансированных partition. Рандомизированный pivot возвращает ожидаемое O(n log n).
Викторина
Completed
Binary search использует while (lo < hi) с hi = arr.length - 1 и возвращает -1 после цикла. На большинстве входов он работает, но промахивается, когда цель стоит в позиции, где lo равно hi. В чём дефект?
Heads-up При включающем диапазоне hi = arr.length - 1 корректно; arr.length дало бы выход за границы. Дефект — строгое < в условии цикла, оставляющее ячейку lo == hi непроверенной.
Heads-up Округление mid здесь ни при чём; цикл просто завершается до проверки индекса lo == hi. Поменяйте условие на lo <= hi.
Heads-up Может, при корректном инварианте. Промах — чисто ошибка на единицу в границе цикла, а не ограничение binary search.
Викторина
Completed
Нужно найти минимальную грузоподъёмность корабля, чтобы доставить все посылки за D дней, и нет отсортированного массива грузоподъёмностей, по которому можно индексироваться. Когда binary search всё равно применим?
Heads-up Binary search требует отсортированного/монотонного пространства поиска, а не буквального массива. Монотонный предикат feasible() позволяет так же делить диапазон ответов пополам.
Heads-up Порядок весов не важен; проверка осуществимости работает с ними как есть. Монотонна должна быть feasible(capacity) при росте capacity.
Heads-up Это как раз немонотонный случай, где binary search ломается: переход, который разворачивается обратно, рушит логику отбрасывания половины. Нужен единственный переход false→true.
Итог
Сквозная мысль юнита — одна привычка: решить, стоит ли покупать порядок. Сортируйте, только если переиспользуете порядок; берите stable-сортировку (merge, insertion), когда равные элементы должны сохранять место; меняйте O(n) буфер merge sort на in-place O(log n) стек quicksort, когда памяти мало, и помните, что плохие pivot грозят O(n²), если не рандомизировать. Когда порядок есть, binary search находит ответы за O(log n) — но только при корректном включающем инварианте, и обобщается на любой монотонный предикат, а не только на массивы.