Re: сортировка с линейной сложностью

From

Ilya Teterin ()

To

Dmitriy K.

Date

2002-07-31T19:34:30Z

Area

RU.ALGORITHMS

From: "Ilya Teterin" <alien@npp-integris.ru>

Хай, Дмитрий!
"Dmitriy K." <krylov@mail.primorye.ru>
<skipped>
Спасибо за ответ. Жаль, линейная сортировка нескольких миллионов 160-ти
разрядной информации по указанному алгоритму не получится - если выделять
старшие разряды, опять получится этот противный N*log(n) ;)
> P.S. А может, сразу отсортированную последовательность генерить?
Прикладное значение сего - быстрый поиск (быстрее log(n)) с использованием
хешей - хеши дают более-менее равномерное распределение.

....равномерное распределение дает интересное свойство - зная значение
элемента, мы можем примерно вычислить его положение после сортировки.
Например, при идеальном равномерном распределении 65536 16ти-разрядных чисел
положение каждого числа после сортировки будет равно его значению :) Ломаю
голову, пытаясь использовать это, написал алгоритм, но при малейшем
отклонении от равномерности опять всплывает этот противный логарифм :)

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)