Найти медиану медиасов quicksort

Question

Я работаю над быстрым сортировкой по медианному алгоритму медианов. Обычно я использую сортировку сортировки, чтобы получить медиану подмассивов из 5 элементов. Однако, если есть тысячи подмассивов, это означает, что мне нужно найти медиану из тысяч медиан. Я думаю, что не могу использовать сортировку, чтобы найти эту медиану, потому что она не оптимальна.

Вопрос:

Может кто-нибудь предложить мне лучший способ найти, что медиана? Спасибо заранее.

Answer 1

Алгоритм медианы медианов не работает, находя медиану каждого блока размера 5, а затем запуская алгоритм сортировки на них, чтобы найти медианную. Вместо этого вы обычно сортируете каждый блок, принимаете медианную из каждого, а затем рекурсивно вызываете алгоритм медианы медианов на этих медианах, чтобы получить хороший стержень. Очень редко встречается алгоритм медианы медианов, используемый в quicksort, поскольку постоянный коэффициент во время выполнения O (n) алгоритма медианы медианов настолько велик, что он имеет тенденцию заметно ухудшать производительность.

Есть несколько возможных улучшений, которые вы можете попробовать по этому оригинальному подходу. Самый простой способ получить хороший стержень - это просто выбрать случайный элемент - это приводит к Θ (n log n) времени исполнения с очень высокой вероятностью. Если вам неудобно использовать случайность, вы можете попробовать использовать introselect algorithm, что является модификацией алгоритма медианы медианов, который пытается снизить постоянный коэффициент, угадывая элемент, который может быть хорошим стержнем и отрезать рекурсию рано, если его найти. Вы также можете попробовать написать introsort, который использует quicksort и переключается на другой алгоритм (обычно heapsort), если окажется, что алгоритм дегенерирует.

Надеюсь, это поможет!