Методы сортировки

Ясно, что любой массив 1-упорядочен, так как его подмассивы длиной 1 можно считать упорядоченными. Если массив k-упорядочен и n<=k, то он упорядочен.

Теперь запишем общую  схему алгоритма:

k:=1;

while k < n do

begin

  ... преобразовать k-упорядоченный  массив

     в 2k-упорядоченный;

  k := 2 * k;

end;

Рассмотрим процедуру  преобразования k-упорядоченного массива  в 2k-упорядоченный. Сгруппируем все  подмассивы длины k в пары подмассивов. Теперь пару упорядоченных подмассивов  сольем в один упорядоченный подмассив. Проделав это со всеми парами, мы получим 2k-упорядоченный массив:

t:=0;

while t + k < n do

begin

  p := t;

  q := t+k;

  ...r := min(t+2*k, n); {в паскале нет  функции min }

  ...сливаем два подмассива A[p..q-1] и A[q..r]

  t := r;

end;

Слияние требует вспомогательного массива для записи результатов  слияния - обозначим его B. Через p0 и q0 обозначим номера последних элементов  участков, подвергшихся слиянию, s0 - последний  записанный в массив B элемент. На каждом шаге слияния производится одно из двух действий:

B[s0+1]:=A[p0+1];

Inc(p0);

Inc(s0);

или

B[s0+1]:=A[q0+1];

Inc(q0);

Inc(s0);

Первое действие (взятие элемента из первого отрезка) может  производиться при двух условиях:

(1) первый отрезок не  кончился (p0 < q);

(2) второй отрезок кончился (q0 = r) или не кончился, но элемент  в нем не меньше [(q0 < r) и (A[p0+1] <= A[q0+1])].

Аналогично для второго  действия. Итак, получаем

p0 := p; q0 := q; s0 := p;

while (p0<>q)or(q0<>r) do

begin

  if (p0<q)and((q0=r)or((q0 < r) and

   (A[p0+1]<=A[q0+1]))) then

  begin

    B[s0+1] := A[p0+1]; Inc(p0); Inc(s0);

  end else

  begin

    B[s0+1] := A[q0+1]; Inc(q0); Inc(s0);

  end;

end;

(Если оба отрезка не  кончены и первые невыбранные  элементы в них равны, то  допустимы оба действия; в программе  выбрано первое.)

Осталось собрать программу  в одно целое:

k := 1;

while k < N do

begin

  t := 0;

  while t+k < N do

  begin

    p := t; q := t+k;

    if t+2*k>N then r := N else r := t+2*k;

    p0 := p; q0 := q; s0 := p;

    while (p0<>q) or (q0<>r) do

    begin

      if (p0<q) and ((q0=r)or((q0<r)and

       (A[p0+1]<=A[q0+1]))) then

      begin

        B[s0+1] := A[p0+1];

        Inc(p0);

      end else

      begin

        B[s0+1] := A[q0+1];

        Inc(q0);

      end;

      Inc(s0);

    end;

    t := r;

  end;

  k := k shl 1;

  A := B;

end;

Сразу же бросается в глаза  недостаток метода – он требует  дополнительную память размером порядка N (для хранения вспомогательного массива). Но как и для древесной сортировки, его временная сложность всегда пропорциональна N*log(N) (так как преобразование k-упорядоченного массива в 2k-упорядоченный требует порядка N действий и внешний цикл по k совершает порядка log(N) итераций).

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

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

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

2.2.7.1. Вырожденное  распределение

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

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

for i := 1 to N do

  Inc(Amount[A[i]]);

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

p := 1;

for i := 0 to M do

  for j := 1 to Amount[i] do

  begin

    A[p] := i;

    Inc(p);

  end;

Несмотря на то, что здесь  два внешних цикла на этом участке  алгоритма выполняется порядка N действий. Это следует из того, что  . Поэтому временную сложность метода можно оценить как T(M+N) (M появляется в сумме, так как изначально надо обнулить массив Amount, а это требует M действий). Пространственная сложность в этом случае равна O(M), поскольку требуется дополнительная память размером порядка M.

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

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

Пусть мы можем завести  дополнительную память размером M+N, а  элементы массива могут принимать  значения от 0 до S, причем S>>M.

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

Заведем M списков общей  суммарной длиной порядка N (это можно  сделать, ограничившись дополнительной памятью O(M+N)).

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

for i := K downto 1 do

begin

  for j := 1 to N do

  begin

    L:=<i-ой цифре A[j] в  M-ной системе счисления>;

    ... занести A[j] в L-ный  список;

  end;

  ... очистить массив A

  for j := 1 to M do

  ... дописать элементы j-ого списка  в массив A

end;

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

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

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

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

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

2.3. Сравнительный анализ

Для проведения экспериментального сравнительного анализа различных  методов сортировки была разработана  программа, которая в автоматическом режиме подсчитывала время, требуемое  для каждого метода сортировки. Для  чистоты эксперимента сортировка всеми  методами проводилась на одинаковых наборах входных данных, затем  формировался новый набор данных, и они опять подвергались сортировке различными методами. Таким образом  было выполнено 60 циклов сортировки, подсчитано среднее время, которое потребовалось  каждому методу, чтобы отсортировать  входной массив. Для более полного  анализа методов в каждом цикле  сортировки сортировка проводилась  для размерностей 500, 1000, 3000, 5000, 8000, 10000, 30000, 60000. Это дало возможность проследить динамику роста требуемого для сортировки времени. Также проверялось, как  ведут себя методы на различных входных данных: упорядоченных в прямом порядке, упорядоченных в обратном порядке и случайных.

Ниже приведены таблицы, которые выдала составленная программа.

а) Для массива, заполненного случайными элементами:

	500	1000	3000	5000	8000	10000	30000	60000
Подсчетом	0.08	0.31	2.76	7.67	19.67
Включением	0.03	0.06	0.60	1.66	4.22	6.58	59.62
Шелла	0.02	0.05	0.43	1.12	2.72	4.24	35.62
Слиянием	0.03	0.02	0.06	0.09	0.11	0.13	0.38	0.77
Извлечением	0.01	0.10	0.92	2.54	6.51	10.17
Древесная	0.02	0.02	0.11	0.20	0.33	0.42	1.39	3.02
Пузырьковая	0.07	0.27	2.43	6.75	17.28
Быстрая	0.00	0.00	0.01	0.03	0.03	0.04	0.13	0.27
Двоичным  распределением	0.00	0.00	0.02	0.03	0.05	0.06	0.20	0.38
Вырожденным распределением	0.00	0.00	0.00	0.00	0.01	0.01	0.01	0.02

б) Для исходно упорядоченного массива:

	500	1000	3000	5000	8000	10000	30000	60000
Подсчетом	0.08	0.32	2.65	7.26	18.46
Включением	0.00	0.00	0.00	0.00	0.01	0.01	0.01	0.03
Шелла	0.00	0.00	0.01	0.02	0.02	0.05	0.15	0.29
Слиянием	0.02	0.02	0.04	0.08	0.09	0.12	0.31	0.63
Извлечением	0.02	0.11	0.92	2.54	6.53	10.20
Древесная	0.01	0.03	0.11	0.19	0.34	0.43	1.45	3.11
Пузырьковая	0.00	0.00	0.00	0.00	0.00	0.01	0.01	0.02
Быстрая	0.00	0.00	0.01	0.02	0.03	0.04	0.11	0.22
Двоичным  распределением	0.00	0.01	0.02	0.03	0.04	0.05	0.18	0.36
Вырожденным распределением	0.00	0.00	0.00	0.00	0.00	0.01	0.01	0.02

в) Для массива исходно  упорядоченного в обратном порядке:

	500	1000	3000	5000	8000	10000	30000	60000
Подсчетом	0.09	0.32	2.64	7.26	18.47
Включением	0.02	0.13	1.16	3.26	8.37	13.08
Шелла	0.01	0.00	0.03	0.16	0.21	0.27	2.09	8.02
Слиянием	0.02	0.03	0.06	0.06	0.10	0.11	0.32	0.64
Извлечением	0.02	0.11	0.91	2.54	6.51	10.19
Древесная	0.00	0.02	0.10	0.18	0.30	0.39	1.32	2.85
Пузырьковая	0.06	0.29	2.95	8.35	21.60
Быстрая	0.00	0.00	0.01	0.01	0.03	0.04	0.11	0.24
Двоичным  распределением	0.01	0.01	0.03	0.03	0.05	0.07	0.19	0.37
Вырожденным распределением	0.00	0.00	0.00	0.00	0.00	0.00	0.01	0.03

Примечание. Пусты ячейки, для которых испытание не проводилось. Время засекалось с точностью  до одной пятидесятой секунды, поэтому  нули в таблице означают, что было затрачено меньше времени, чем одна пятидесятая доля секунды. Испытание  проводилось на AMD-K5-PR133/32Mb EDO/850Mb под  управлением MS-DOS 7.0, входящую в состав WINDOWS 95. Массивы размещались в  динамической памяти.