Гимназия №1534

Сортировка подсчётом

Как мы выяснили, сортировка пузырьком умеет сортировать массив за $O(n^2)$. Сейчас мы научимся сортировать массивы специально вида гораздо быстрее.

Итак, предположим, что у нас имеется массив целых чисел из некоторого диапазона $[MINVALUE,\,MAXVALUE]$. Пусть также диапазон не слишком велик. Например, пусть $MAXVALUE - MINVALUE \le 10^7$. В этом случае мы можем подсчитать, сколько раз каждое значение из диапазона встречается в массиве. Затем мы можем по этой информации выписать исходный массив в отсортированном порядке.

Приведём код, который сортирует массив. Отметим, что такие параметры алгоритма, как MINVALUE и MAXVALUE, лучше выносить в секцию констант. В программировании принято имена констант записывать большими буквами.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

const 
  MINVALUE = 0;
  MAXVALUE = 1000 * 1000;
  MAXN     = 1000 * 1000;

var
  n, i, j, k: longint;
  a: array [1..MAXN] of longint;
  count: array [MINVALUE..MAXVALUE] of longint;

begin
  read(n);

  for i := 1 to n do 
    read(a[i]);

  // обнуляем массив count
  for j := MINVALUE to MAXVALUE do
    count[j] := 0;

  for i := 1 to n do 
    count[a[i]] := count[a[i]] + 1;

  i := 1; // позиция ячейки в массиве чисел, 
          // которая будет заполняться следующей
  for j := MINVALUE to MAXVALUE do
    for k := 1 to count[j] do begin
      a[i] := j;
      i := i + 1;
    end;

  for i := 1 to n do
    write(a[i], ' ');
end.

Оценим время работы этой программы. Обозначим размер диапазона за $m$, т. е. $m := MAXVALUE - MINVALUE + 1$. Цикл в строчках 18-19 выполняется за $O(m)$. Цикл в строчках 21-22 выполняется за $O(n)$. В строках 26-30 суммарно совершается $n + m$ операций. Итого время работы сортировки подсчётом составляет $O(n + m)$, где $n$ — размер массива, а $m$ — размер диапазона чисел. Серьёзное улучшение по сравнению с алгоритмом сортировки пузырьком!