Сортировка распределением

Сортировка распределением интересна тем, что она сортирует массив, не сравнивая элементы друг с другом.

Рассмотрим сначала вырожденный случай сортировки распределением, а затем более общий.

При вырожденном распределении предполагается, что каждый элемент массива может принимать m (например, от 1 до m) фиксированных значений. Заведем массив Amount размерностью m, первоначально обнулив его. Затем для каждого i подсчитаем количество элементов массива A, равных i, и занесем это число в Amount[i]. После чего, в первые Amount[1] элементов массива A запишем 1, в следующие Amount[2] элементов массива A запишем 2 и т.д. до тех пор, пока не дойдем до конца массива A (заметим, что в то же время мы окажемся в конце массива Amount).

Теперь запишем алгоритм.

procedure DispersSort(n, m: integer;

var A: array[1..n] of integer);

{Процедура сортировки вырожденным распределением}

var

i, j, k: integer;

Amount: array[1..m] of integer;

begin

{Обнуляем массив Amount}

for i := 0 to m do Amount[i] := 0;

{Заполняем массив Amount}

for i := 1 to n do Amount[A[i]] := Amount[A[i]] + 1;

{Заполняем массив A}

k := 1;

for i := 0 to M do

for j := 1 to Amount[i] do begin

A[k] := i;

k := k + 1;

end;

end;

Временную сложность метода можно оценить как O(m+n) (m появляется в сумме, так как изначально надо обнулить массив Amount, а это требует m действий). Пространственная сложность в этом случае пропорциональна O(m), поскольку требуется дополнительная память размером порядка m.

Недостатком этого метода является то, что требуется дополнительная память размером порядка m, а это может оказаться недопустимым из-за большого значения m. Но, если m>>n, то есть способ уменьшить объем требуемой дополнительной памяти, который сейчас и рассмотрим, как общий случай сортировки распределением.

Пусть выделяется дополнительная память размером b+n, а элементы массива могут принимать значения от 0 до s, причем s>>b.

Каждый элемент этого массива можно представить в b-ичной системе счисления и разбить на k цифр этой системы счисления.

Заведем списки L₁, L₂… L_b общей суммарной длиной порядка n (это можно сделать, ограничившись дополнительной памятью O(b+n)).

Тогда алгоритм сортировки распределением можно представить следующим образом:

for i := k downto 1 do begin

for j := 1 to n do begin

if p = i-ой цифре A[j] в b-ной системе счисления then

занести A[j] в L[p] список;

end;

Очистить массив A;

for j := 1 to b do

Дописать элементы L[j] в массив A;

end;

Итак, как видно из приведенной выше программы, на каждом шаге метода производится сортировка элементов массива по значению i-ого разряда. При этом производится промежуточное распределение элементов массива по спискам в зависимости от значения соответствующего разряда этих элементов. Во время распределения очень важно сохранить при записи в списки порядок следования элементов, чтобы не нарушить порядок, достигнутый на предыдущих шагах.

Индукцией по i легко доказать, что после i шагов любые два числа, отличающиеся только в i последних разрядах, идут в правильном порядке.

Достигнув i=1, получаем полностью отсортированный массив.

Как нетрудно заметить, если положить s=b, то отпадает необходимость заводить списки и производить запись в них: в j-ый список будут попадать только числа, равные j. В этом случае достаточно хранить лишь размеры списков, то есть подсчитать количество элементов, равных j, для всех j от 1 до s. А потом просто заново заполнить массив A в соответствии с этими количествами, то есть получаем вырожденную сортировку.

Рассмотрим на примере задачу сортировки 12 целых чисел из интервала от 0 до 99, то есть n=12, b=10 (десятичная система счисления), s=99, k=2 (два разряда). При этом будем считать, что числа, содержащие только один разряд, дополняются слева нулем, то есть число «0» будет «00», число «1» будет «01» и т.д.

Рисунок 48. Сортировка распределением

Интересно, что временная сложность этого алгоритма пропорциональна O(k*n), а если учесть, что k фактически является константой, то получаем гарантированную (минимальную, среднюю и максимальную) линейную сложность. Но недостатком этого метода является необходимость выделять дополнительную память размером порядка b+n. Если бы не это ограничение, можно было бы считать этот метод самым эффективным при больших значениях n.