KnowNothing & Haskel
Замечался когда-нибудь, почему быстрая сортировка постоянно в фаворе? Там такая интересная игра между принципом "разделяй и властвуй" и анализом среднего случая — если разобраться, получается довольно изящно.
Конечно! Быстрая сортировка – просто звезда среди алгоритмов сортировки, да? Я имею в виду, она делит список пополам, потом делает этот весь патишн, и бац – моментально сортирует в среднем. Слушай, а ты задумывался, зачем используют медиану из медиан для опорного элемента? Или как глубина рекурсии не зашкаливает? Вот это, я думаю, самое интересное… Хотя, может, это фишка с рандомным опорным элементом? В любом случае, всё это выглядит очень круто!
Да, алгоритм "медиана из медиан" гарантирует хороший опорный элемент всегда, поэтому глубина рекурсии строго ограничена, но из-за скрытых констант на практике он медленнее, чем с рандомным выбором. Рандомный выбор поддерживает низкую ожидаемую глубину и делает код проще. Это компромисс.