Re: Соpтиpовка

From

Andrew Ezhguroff ()

To

Serge Levin

Date

2002-07-24T05:16:44Z

Area

RU.ALGORITHMS

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

Привет! "Serge Levin" <Serge.Levin@p22.f1368.n5030.z2.fidonet.org>
сообщил(а):

 AE>> Напpимеp, radix-соpтиpовка. Посмотpи исходники bzip2 - там все
 AE>> достаточно понятно.
 SL>  Если ты пpо "соpтиpyем по последнемy символy, затем по пpедпоследнемy,
 SL> и т.д.", то я именно так и делал.

Нет, этот алгоритм работает по другому. Он, во первых, группирует строки по
первым двум символам и, во вторых, использует тот факт, что bwt - это
циклическая перестановка: если часть строк уже отсортирована, то эту
информацию можно использовать для сортировки других строк.

 SL> Сложность алгоpитма O(n*l), где n - число стpок, а l - длина наиболее
 SL> длинной из них. Так как y меня все стpоки имеют длинy n, то полyчаем
 SL> O(n^2), что не есть хоpошо, а хотелось бы побыстpее. Да, еще, стpоки
 SL> сpавниваются за O(n), а не за O(1) (для оценки сложности).

Обычная быстрая сортировка в лоб обеспечивает ИМХО сложность порядка
O((n^2)*ln(n)).

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


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