|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 27 Dec 2002 05:46:39
To : Oleg Khovayko
Subject : Re: быстpая соpтиpовка
--------------------------------------------------------------------------------
Привет! "Oleg Khovayko" <olegh@hotpop.com> сообщил(а):
OK> 3. Hе требует дополнительной памяти для данных
OK> 4. Количество уровней рекурсии HИКОГДА не превысит количества бит
OK> в твоем сортируемом слове - то есть уровней рекурсии будет не более 16,
OK> тогда как для quicksort-a возможен такой набор данных,
OK> что число уровней рекурсии станет равно длине сортируемого массива.
OK> У тебя в микроконтроллере стек ограничен, поэтому данное свойство
OK> алгоритма становится очень важным.
Hо рекурсия все же нужна. И, следовательно, дополнительная память для
организации рекурсии нужна (так что в п.3 ты не прав).
Пирамидальная сортировка обеспечивает O(N*log(N)) для любых данных (правда с
большим коэф. пропорциональности - она работает медленнее лучшего случая
быстрой сортировки) и не требует рекурсии и дополнительных массивов.
С уважением, Андрей.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
