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

From

Dmitriy K. ()

To

Ilya Teterin

Date

2002-07-31T18:20:48Z

Area

RU.ALGORITHMS

From: "Dmitriy K." <krylov@mail.primorye.ru>

Привет, Ilya!
Wed, 31 Jul 2002 10:17:30 +0000 (UTC) Вы написали :

 IT> Хай, Олл!

 IT> Существует ли алгоритм сортировки с линейной вычислительной
 IT> сложностью, если известно, что сортируемые данные - случайная
 IT> величина с равномерным распределением?

Существует. Но человечеству пока не известна ;-)

Зависит от того, что за "данные" и что за "величина".

Если величина - из некоторого конечного множества - например, 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;

Как называется эта сортировка - я не помню. Кажется, "карманная".

Если же твоя "случайная величина" не помещается в границы байта, то тут надо
смотреть...

Например:
1) Если гарантировано все элементы разные - можно через битовые массивы
(правда, памяти пожрет...). Если встречается не больше k раз - через k
битовых массивов. Кстати, подойдет и для байтов, тогда вообще проще: в
Pascal уже есть подходящий битовый массив - производные от типа set.

2) Если не байт, а, например, слово (2 байта) - та же фигня, но на счетчики
больше памяти будет угрохано. На самом деле не так уж и важно, какое
представление. Просто для целых чисел получается проще - порядок задается
порядком счетчиков, тогда как для дробных приходится извращаться на шаге 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)