ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Dmitriy Goldobin                     2:5020/400     14 Jul 2003  13:59:47
 To : Dmitriy Iassenev
 Subject : Re: QuickSort
 -------------------------------------------------------------------------------- 
 

 Hi!
 
 > худший случай для быстрой сортировки - 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. В самом лучшем случае глубина
 рекурсии logN, значит обрабатывается NlogN ячеек, меньше просто не может
 получиться, даже если массив уже был заранее отсортирован.
 
 Как считать матожидание тут - совершенно непонятно. Выбираем из N значений
 одно случайным образом, каково будет количество значений меньше и больше
 выбранного?
 
 > > худшем случае не N, а logN если первыми начинать обрабатывать всегда
 
 более
 
 > > короткие ветки, а по более длинной не спускаться, а обрабатывать на том
 
 же
 
 > > уровне.
 
 > Представьте худший вариант - Вы всегда выбираете элемент, который является
 > минимальным (считаем, что сортируем в порядке возрастания) - тогда
 > использование стека 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;
     }
 }
 
 > > Hаверное что-то специфическое с большими ограничениями на память. Да и
 > > вообще в частных случаях, когда тебе о данных известно нечто, чего не
 > > учитывает универсальный алгоритм, можно сделать быстрее.
 >
 > :-)) попробуйте, я выиграл у STL только на строках и данных с малым
 > диапазоном
 > значений, она написана _очень_ грамотно, с учётом практически всех советов
 > по сортировке.
 
 да это ж не я вопрос задавал. :) А выиграть? Когда мне о данных заранее
 известно нечто, то много способов. Допустим я знаю что распределение данных
 близко к равномерному в диапазоне от 1 до 100000. Тогда я буду высчитывать
 для qsort среднее значение прямо из границ обрабатываемого участка. Или
 допустим данные дискретны и диапазон небольшой - сортировка подсчетом,
 гарантированные N*2 :) Или допустим в каких-то случаях радиксом сортировать.
 А универсальный алгоритм на то и универсальный, что в среднем дает хороший
 результат, но в частных случаях его можно обогнать, иногда значительно.
 
 Bye.
 --- ifmail v.2.15dev5
  * Origin: Demos online service (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