2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Быстрая сортировка. Опорное число.
Сообщение05.06.2011, 16:50 
Securus в сообщении #454308 писал(а):
Здравствуйте! При реализации q-sorta в литературе я видел только предложения по выбору опорного элемента. Но почему бы не выбрать опорное число, скажем, как среднее арифметическое всех элементов? Это увеличит время выполнения в 2 раза, но зато и увеличит "половинность" деления. Или увеличение времени в 2 раза считается более критичным, чем возможность неудачных делений?
Во первых, не всегда на сортируемых элементах определены операции сложения и деления.
Во вторых, даже использование среднего арифметического не улучшит теоретическую сложность $O(n^2)$ в худшем случае, например, если элементы - степени двойки.
Ну и в третьих, есть уже эффективные модификации быстрой сортировки, лишённые недостатков тривиальной реализации. Например в стандартной библиотеке С++ используется вариант introsort - он быстр и в случайном, и худшем случае.

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

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

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group