Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 2 сек. Память: 16 Мб Сложность: 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, ' ');
  }
}

Данный алгоритм не является универсальным и применим исключительно к массивам с ограниченным диапазоном возможных значений.


[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483