|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy K. 2:5020/400 31 Jul 2002 18:20:48
To : Ilya Teterin
Subject : Re: сортировка с линейной сложностью
--------------------------------------------------------------------------------
Привет, Ilya!
Wed, 31 Jul 2002 10:17:30 +0000 (UTC) Вы написали :
IT> Хай, Олл!
IT> Существует ли алгоритм сортировки с линейной вычислительной
IT> сложностью, если известно, что сортируемые данные - случайная
IT> величина с равномерным распределением?
Существует. Hо человечеству пока не известна ;-)
Зависит от того, что за "данные" и что за "величина".
Если величина - из некоторого конечного множества - например, 0-255, то
сортировку последовательности с линейной скоростью a0, a1, ..., ak можно
сделать так:
1) посчитать, сколько раз встречается 0, сколько - 1 и т.д. Это можно
сделать за один проход последовательности, заведя 256 счетчиков.
2) построить отсортированную последовательность: сначала идут '0' - столько
раз, сколько встречались в исходной последовательности, затем '1' и т.д.
Линейность всё равно сохраниться, т.к. количество проходов равно k.
Вот так:
const k = 10;
var
a: array[1..k] of byte;
procedure sort;
var
counters: array[byte] of byte;
i, j, l: byte;
begin
FillChar(counters, SizeOf(counters), 0);
for i := 1 to k do Inc(counters[a[k]]); // Шаг 1
l = 1; // Шаг 2
for i := 0 to 255 do
for j := 1 to counters[a[i]] do
begin
a[l] := i;
Inc(l);
end;
end;
Как называется эта сортировка - я не помню. Кажется, "карманная".
Если же твоя "случайная величина" не помещается в границы байта, то тут надо
смотреть...
Hапример:
1) Если гарантировано все элементы разные - можно через битовые массивы
(правда, памяти пожрет...). Если встречается не больше k раз - через k
битовых массивов. Кстати, подойдет и для байтов, тогда вообще проще: в
Pascal уже есть подходящий битовый массив - производные от типа set.
2) Если не байт, а, например, слово (2 байта) - та же фигня, но на счетчики
больше памяти будет угрохано. Hа самом деле не так уж и важно, какое
представление. Просто для целых чисел получается проще - порядок задается
порядком счетчиков, тогда как для дробных приходится извращаться на шаге 2
да и память, память...
3) Сдается мне, что если эта "случайная величина" представляется, ну, для
простоты типом integer (32-х битным), то сначала нуна отсортировать по
младшим байтам (сохраняя информацию об оставшихся), потом - по более старшим
и т.д... Тогда для счетчиков нужно будет меньше памяти. Думать надо.
P.S. А может, сразу отсортированную последовательность генерить?
P.P.S. В инете проскакивала как-то информация о O(log(log(log(n))))
сортировке... Типа, для больших n ;) . Могу поискать на винте.
Удачи!
__________________________________________________________________________
--{ Dmitriy Krylov aka "Abulafia" }-------------------------------------
--{ mailto: krylov@mail.primorye.ru }-------------------------------------
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: сортировка с линейной сложностью 
