Сортировка подсчетом
(Время: 2 сек. Память: 128 Мб Сложность: 29%)
В этой задаче нужно отсортировать целочисленный массив, но сложность ее в том, что массив может содержать очень большое количество элементов (до миллиона). Решить данную задачу возможно с использованием стандартного алгоритма быстрой сортировки, но несмотря на это существует более эффективное решение, основанное на использовании так называемой сортировки подсчетом (CountSort).
Дело в том, что диапазон возможных значений элементов массива ограничен и поэтому вовсе не обязательно хранить весь массив в памяти, достаточно считывая его поэлементно вычислять для каждого возможного элемента x количество таких элементов в массиве. Для этого определяется некоторый массив d[x], в котором каждый элемент - это счетчик количества элементов исходного массива a[i], т.е в итоге в d[x] мы предполагаем получить количество элементов массива a[i], которые равны x. Достичь этого можно следующим образом: при чтении очередного элемента a[i] увеличивать значение d[a[i]] на единицу. По завершении этого процесса достаточно вывести d[x] раз в порядке увеличения x (по всему возможному диапазону) значение x. Данный алгоритм имеет порядок сложности O(N).
Решение данной задачи на алгоритмическом языке:
int d[-100..100]={0...0};
read(n);
for i=1..n{
read(x);
d[x]=d[x]+1;
}
for x=-100..100{
for i=1..d[x]{
write(x, ' ');
}
}
Данный алгоритм не является универсальным и применим исключительно к массивам с ограниченным диапазоном возможных значений.
| 
