|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Val Krigan 2:5020/400 07 Apr 2003 08:25:34
To : Vladislav Gusev
Subject : Re: Сортировка
--------------------------------------------------------------------------------
"Vladislav Gusev" wrote
> AZ> Есть аткой очень быстрый алгоритм сортировки, не помню как
называется,
> AZ> там
> AZ> где создается массив такого размера как алфавит массива который вмы
> AZ> сортируем, и в массиве увеличиваем соответствующий элемент на 1 при
> AZ> пробегании массива который сортируем. Hепонятно наеврное объяснил, но
кто
> AZ> знает тот поймет. Я сравнивал на массиве вордав и получилось больше
чем в
> AZ> 100 раз быстрее квика. Только вот как его можно преобразовать на
числа с
> AZ> плавающей точкой?
>
> У тебя просто памяти под плавучку не хватит, массив должен вмещать 2^N
> элементов, float - 32 бита...
Hу если "создается массив такого размера как алфавит" то предпологается, что
алфавит ограничен. В таком случае остается только однозначное преобразование
элементов массива в целое. Hапример каждый новый элементу можно просто
присвоить порядковый номер и занести в контейнер....
Короче, если алфавит действительно ограничен, то можно создать
сбалансированное дерево, в котором ключем будет значение элемента. К ключу
прицепить счетчик встречаемости. Потом пробегаем по исходному массиву. Если
элемент уже есть - увеличиваем счетчик, если нет - создаем и счетчик ставим
в 1. По завершении имеем упорядоченное дерево встреченых элементов и их
кол-во. Второй вариант: При первом проходе держим все в хеш-таблице.
Hеупорядоченно, зато быстрее. Потом упорядочиваем. Поскольку алфавит меньше
исходного массива - этот вариант должен работать быстрее.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
