|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Iassenev 2:5020/400 10 Apr 2003 13:30:57
To : Alexandr Zykhov
Subject : Re: Сортировка
--------------------------------------------------------------------------------
> Есть аткой очень быстрый алгоритм сортировки, не помню как называется, там
где
> создается массив такого размера как алфавит массива который вмы сортируем,
и в
> массиве увеличиваем соответствующий элемент на 1 при пробегании массива
который
> сортируем. Hепонятно наеврное объяснил, но кто знает тот поймет. Я
сравнивал на
> массиве вордав и получилось больше чем в 100 раз быстрее квика. Только вот
как
> его можно преобразовать на числа с плавающей точкой?
Эта сортировка называется "сортировка подсчётом". Она действительно
алгоритмически быстрее (O(N)), чем остальные (O(NLogN)), т.к.использует
информацию о внутреннем представлении данных. Однако, сравнение "в 100 раз
быстрее быстрой сортировки" - это некорректно. Кроме того, Вы могли
неэффективно реализовать быструю сортировку, попробуйте её STL-вский
вариант.
Для того, чтобы отсортировать массив float-ов, Вам необходимо использовать
либо поразрядную сортировку, либо два раза сортировку подсчётом.
Скажем, если Вы хотите отсортировать массив 32-х битовых беззнаковых целых,
Вы можете выделить массив из 256-и элементов, и, начиная от младших байтов к
старшим 4 раза отсортировать массив сортировкой подсчётом. Аналогично можно
сделать и для float-ов, проблема только в том, что там они знаковые. Я
где-то в интернете наткнулся на исходники программ?, которая делает именно
то, что Вам нужно.
Поищите по этой фразе "Fast Float Sort" или "Fast Float Sort Radix ".
Желаю удачи,
Дмитрий Ясенев.
--- ifmail v.2.15dev4
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
