ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Dmitriy Iassenev                     2:5020/400     14 Jul 2003  15:50:02
 To : Dmitriy Goldobin
 Subject : Re: QuickSort
 -------------------------------------------------------------------------------- 
 

 > > худший случай для быстрой сортировки - N^2, однако матожидание близко к
 
 N
 
 >
 > По-моему все-таки N^2/2. Hа первом шаге мы обработали все N ячеек и
 
 получили
 
 > два куска. Hа втором шаге мы обрабатываем эти 2 куска, суммарно опять же N
 > ячеек. То есть N * на глубину рекурсии. Hо с учетом того, что кусок длиной
 
 1
 
 > обрабатывать не нужно, то в худшем случае имеем глубину рекурсии N, но
 > количество обрабатываемых ячеек каждый раз уменьшится на 1, поэтому имеем
 > N+(N-1)+(N-2)+...+2. То есть около N^2/2.
 
 я имел в виду O(N^2)
 
 > В самом лучшем случае глубина
 > рекурсии logN, значит обрабатывается NlogN ячеек, меньше просто не может
 > получиться, даже если массив уже был заранее отсортирован.
 
 :-)) если массив был уже отсортирован, то это худший случай для
 нерандомизированной быстрой сортировки. Обычно для маленьких блоков
 применяют уже не быструю сортировку, а сортировку Шелла или обменную. Если
 использовать рандомизированную быструю сортировку, применяя на последней
 стадии обменную сортировку, то матожидание будет
 n*k + n*log(n/k), где k - количество элементов, начиная с которого работает
 обменная сортировка. Ассимптотически это по-прежнему O(N*log(N)), но с очень
 маленькой константой (потому я и сказал, что близко к N).
 
 > > Представьте худший вариант - Вы всегда выбираете элемент, который
 
 является
 
 > > минимальным (считаем, что сортируем в порядке возрастания) - тогда
 > > использование стека N.
 >
 > Так более длинный кусок обрабатывается без рекурсии.
 >
 > sort( bounds )
 > {
 > while( len(bounds) > 1 ) {
 >   (bounds1,bounds2) = sortstage(bounds);
 >   if( len(bounds1) > len(bounds2) ) {
 >     sort( bounds2 );
 >     bounds = bounds1;
 >     }
 >   else {
 >     sort( bounds1 );
 >     bounds = bounds2;
 >     }
 > }
 
 :-)) я тоже использую этот трюк, но рассуждения вёл безотносительно него
 (скажем, мы разбиваем не ровно на 2 части, а на k).
 
 > да это ж не я вопрос задавал. :) А выиграть? Когда мне о данных заранее
 > известно нечто, то много способов. Допустим я знаю что распределение
 
 данных
 
 > близко к равномерному в диапазоне от 1 до 100000. Тогда я буду высчитывать
 > для qsort среднее значение прямо из границ обрабатываемого участка.
 
 в STL берётся медиана 3-х
 
 > Или
 > допустим данные дискретны и диапазон небольшой - сортировка подсчетом,
 > гарантированные N*2 :)
 
 в связи с нынешней архитектурой ПК иногда пузырьковая сортировка может
 выполнится быстрее быстрой, т.к. она использует память более
 последовательно, в случае с сортировкой подсчётом Вы можете больше проиграть
 на обращениях к памяти, таким образом константа при N будет большой.
 
 > Или допустим в каких-то случаях радиксом сортировать.
 > А универсальный алгоритм на то и универсальный, что в среднем дает хороший
 > результат, но в частных случаях его можно обогнать, иногда значительно.
 
 :-)) Вы всё-таки попробуйте, радиксом не так просто обогнать быструю
 сортировку, я сам пробовал это на сортировке строк, показатели отличаются не
 более чем на 20% (в среднем всего 10% выигрыша).
 
 С уважением,
 Дмитрий Ясенев.
 --- ifmail v.2.15dev5
  * Origin: Unknown (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: QuickSort   Dmitriy Goldobin   14 Jul 2003 11:11:36   Re: QuickSort   Dmitriy Iassenev   14 Jul 2003 12:49:13   Re: QuickSort   Dmitriy Goldobin   14 Jul 2003 13:01:15   Re: QuickSort   Dmitriy Iassenev   14 Jul 2003 13:34:27   Re: QuickSort   Dmitriy Goldobin   14 Jul 2003 13:59:47   Re: QuickSort   Dmitriy Iassenev   14 Jul 2003 15:50:02