Быстрая сортировка. Опорное число.

[Securus]

Здравствуйте! При реализации q-sorta в литературе я видел только предложения по выбору опорного элемента. Но почему бы не выбрать опорное число, скажем, как среднее арифметическое всех элементов? Это увеличит время выполнения в 2 раза, но зато и увеличит "половинность" деления. Или увеличение времени в 2 раза считается более критичным, чем возможность неудачных делений?

[venco]

Securus в сообщении #454308 писал(а):

Здравствуйте! При реализации q-sorta в литературе я видел только предложения по выбору опорного элемента. Но почему бы не выбрать опорное число, скажем, как среднее арифметическое всех элементов? Это увеличит время выполнения в 2 раза, но зато и увеличит "половинность" деления. Или увеличение времени в 2 раза считается более критичным, чем возможность неудачных делений?

Во первых, не всегда на сортируемых элементах определены операции сложения и деления.
Во вторых, даже использование среднего арифметического не улучшит теоретическую сложность $O(n^2)$ в худшем случае, например, если элементы - степени двойки.
Ну и в третьих, есть уже эффективные модификации быстрой сортировки, лишённые недостатков тривиальной реализации. Например в стандартной библиотеке С++ используется вариант introsort - он быстр и в случайном, и худшем случае.

А если быструю сортировку замедлить в два раза, то наверно лучше уже использовать heapsort - с гарантированной сложностью $O(n\ln n)$. Этот алгоритм проигрывает быстрой сортировке только константным множителем. Кстати introsort в сложных случаях как раз переключается на heapsort.

[Securus]

Спасибо за ответ. Действительно, интересная идея- подключать более стабильный алгоритм на слишком глубоких уровнях рекурсии. Кстати, я не подчеркнул, что скорость упадёт в 2 раза в наилучшем случае (при использовании среднего арифметического), а вот если такой выбор использовать для не сильно скачущих последовательностей, которые чаще всего встречаются на практике, то мне кажется, что будет выигрыш по времени. Я это проверю в ближайшее время экспериментально.