2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Быстрая сортировка. Опорное число.
Сообщение05.06.2011, 13:53 


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

 Профиль  
                  
 
 Re: Быстрая сортировка. Опорное число.
Сообщение05.06.2011, 16:50 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Быстрая сортировка. Опорное число.
Сообщение06.06.2011, 01:15 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group