Задача

1 /11


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

Теория Нажмите, чтобы прочитать/скрыть

Сортировка подсчетом ("черпачная")
Применение
Сортируемые числа имеют диапазон возможных целых положительных значений, который достаточно мал по сравнению с сортируемым множеством. Например, миллион значений, каждое из которых не больше 1000.
 
Алгоритм
1) Пусть есть массив А из N элементов, включающий числа в диапазоне от 0 до k-1 (то есть всего максимум k различных значений).
2) Создадим вспомогательный массив C[0..k-1], состоящий из нулей (назовем его массивом счетчиков: каждый элемент массива счетчиков хранит количество, которое встречается в исходном массиве А число равное индексу элемента массива C).
3) Последовательно прочитать элементы массива A и для каждого A[i] увеличить С[A[i]] на единицу. В итоге мы получим массив C, в котором каждый элемент C[i] равен количеству встречаемости значения i в исходном массиве A, индекс i равен значению элемента массива A.
4) Пройдя по массиву С и для каждого j от 0 до k-1 в новый массив (или перезапишем массив A) последовательно записать число j C[j] раз.
 
Пример
Пусть имеет массив А = {2, 5, 6, 9, 4, 1, 8, 2, 9, 8, 4, 1, 4, 1}.
Диапазон чисел - от 0 до 9, то есть всего 10 различных значений.
1. Создаем массив С из 10 нулевых элементов.
2. Проходим по массиву А и увеличиваем на 1 элемент С[A[i]].
3. Полученный массив С = {0, 3, 2, 0, 3, 1, 1, 0, 2, 2}.

Данный метод можно применять и при наличии отрицательных значений, в этом случае для подсчета количества элементов равных самому минимальному (Amin) будем использовать элемент С[0], подсчет i-го элемента массива A будет производиться следующим образом C[A[i] - Amin].

 
Пример реализации алгоритма 

Пусть все n чисел массива А натуральные и лежат в промежутке от 1 до 100. 

1) Создадим массив размера 100, в котором будем хранить на k-ом месте, сколько раз число k встретилось в этом массиве.
2) Пройдемся по всем числам исходного массива и увеличим соответствующее значение массива на 1.
3) После того, как мы посчитали, сколько раз каждое число встретилось, можно просто пройтись по этому массиву и вывести 1 столько раз, сколько встретилась 1, вывести 2 столько раз, сколько встретилась 2, и так далее.

  
С++ Python Pascal
const int Nmax = 1000;
int c[100] = {0}, n;
int a[Nmax];
...
for (int i = 0; i < n; i++)
    c[a[i]]++;

int k = 0;
for (int i = 0; i < 100; i++)
    while (c[i] != 0)
    {
        a[k] = i;
        k++;
        c[i]--;
    };
c = [0]*100
for i in range (len(a)):
    c[a[i]] += 1

k = 0
a=[0]*len(a)
for i in range (100):
    while c[i] != 0:
        a[k] = i
        k += 1
        c[i] -= 1

var 
    c: array [0..99] of integer;
    k, n, i: integer;
...
for i:= 0 to n-1 do
  c[i] := 0;
  
for i:= 0 to n-1 do
  c[a[i]] := c[a[i]] + 1;

k := 0;
for i:= 0 to 99 do
  while c[i] <> 0 do
    begin
      a[k] := i;
      k := k + 1;
      c[i] := c[i] - 1;
    end;


Произвольный целочисленный диапазон

Что делать, если диапазон значений (min и max) заранее не известен? Что делать, если минимальное значение больше нуля или в сортируемых данных присутствуют отрицательные числа?
Первый вопрос можно решить линейным поиском min и max, что не повлияет на асимптотику алгоритма.
Второй вопрос несколько сложнее. Если min больше нуля, то следует при работе с массивом C из A[i] вычитать min, а при обратной записи прибавлять. При наличии отрицательных чисел нужно при работе с массивом C к A[i] прибавлять |min|, а при обратной записи вычитать.

Задача

Реализуйте алгоритм сортировки подсчетом для произвольных чисел, по модулю не превосходящих 10000.
 
Входные данные
На вход программе сначала подается значение n <= 100000 – количество элементов массива. В следующей строке расположены сами элементы – целые числа, по модулю не превосходящие 10000.
 
Выходные данные
Выведите на экран отсортированный по неубыванию массив.
 
Примеры
Входные данные Выходные данные
1
5
1 3 4 2 5
1 2 3 4 5




time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w64426
Free Pascal1
Python264
Комментарий учителя