Re: быстpая соpтиpовка

From

Andrew Ezhguroff ()

To

Oleg Khovayko

Date

2002-12-27T04:46:39Z

Area

RU.ALGORITHMS

From: "Andrew Ezhguroff" <eandr@com2com.ru>

Привет! "Oleg Khovayko" <olegh@hotpop.com>  сообщил(а):

 OK> 3. Не требует дополнительной памяти для данных
 OK> 4. Количество уровней рекурсии НИКОГДА не превысит количества бит
 OK> в твоем сортируемом слове - то есть уровней рекурсии будет не более 16,
 OK> тогда как для quicksort-a возможен такой набор данных,
 OK> что число уровней рекурсии станет равно длине сортируемого массива.
 OK> У тебя в микроконтроллере стек ограничен, поэтому данное свойство
 OK> алгоритма становится очень важным.

Но рекурсия все же нужна. И, следовательно, дополнительная память для
организации рекурсии нужна (так что в п.3 ты не прав).

Пирамидальная сортировка обеспечивает O(N*log(N)) для любых данных (правда с
большим коэф. пропорциональности - она работает медленнее лучшего случая
быстрой сортировки) и не требует рекурсии и дополнительных массивов.

С уважением, Андрей.


-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)