[amirus] Re: Sortissimo
- From: Mind Engine <mindengine@xxxxxxx>
- To: AmiS <amirus@xxxxxxxxxxxxx>
- Date: Wed, 13 Nov 2002 18:19:31 +0300
Hi, AmiS!
12 ноября 2002 г., 19:55:44, ты сочинил:
>> AmiS, если в тебе еще теплится life-force, еще один подсказон, я тут
>> подошел к теме сортировки (на эту тему в одном из номеров будет мощная
>> статья, ибо я нашел описалово всех основных голгоритмов) и надыбал фишку,
>> что для нашего случая (частично приведенного в порядок массива) идеально
>> подходит алгоритм mergesort! А quicksort будет ловить тормоза на такой
>> ситуации... Ты того, мотай на ус или что там у тебя! ;^)
AmiS> Было время когда я на сортировке собаку съел... :)
И как, не вспучило?
AmiS> Вообще ты не совсем прав. если
AmiS> углублятся в теорию то у merge-sort как и у quick-sort среднее время
работы на равномерном
AmiS> случайном распределении будет NlogN. если говорить про частично
упорядочные данные, то
AmiS> Qsort проигрывает только из-за того что стандартная процедура выбора
граничного
AmiS> (разделяющего если хочешь) значения расчитывает на хаотичность данных.
Ну и я про то!
AmiS> Для данный такого
AmiS> рода как ты говоришь можно применить в qsort другой алгоритм выбора
например
AmiS> псевдослучайный... в данном случае ты приблизишься (а то и выиграешь) по
сравнению с merge
AmiS> sort.
Ну не факт, надо пробовать...
AmiS>
AmiS> А вообще существуют алгоритмы сортировки за Линейное время...
Я особо не копал...
AmiS> которые для такх данных
AmiS> как у тебя тоже подходят... так что комай дальше или мотяй на ус или что
там у тебя. ;)
На косу тока могу! :D
AmiS> А что касается ерудикта, я вообще не буду делать там сортировку... ;)
Подумай почему. И
AmiS> опять же мотай на ус.
А для пользовательского словаря? С другими то ясен пень!
--
With Love to You...
Mind Engine/team PowerAmiga
Other related posts:
