Учебно-методическое пособие. Алматы, 2017 ббк

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

Выше мы рассмотрели основные виды сортировок, они отличаются по скорости выполнения, более того, скорость сортировки зависит и от степени упорядоченности исходного массива. Однако, для них характерно общая особенность, время сортировки быстро возрастает с количеством элементов (время работы любого из универсальных “эффективных”,(то есть выполняющих порядка Nlog₂N действий).

Интерестно, сущестует ли метод сортировки такой, в котором количество действий равно количеству самих элементов. Оказывается, такой метод существует. Пусть, требуется отсортировать 1000000 чисел, вводимых, например, из стандартного потока ввода (это типичная задача для районных или городских олимпиад по информатике). Так вот, если эти числа являются целыми и известен диапазон значений в котром они лежат то, в этом случае алгоритм сортировки фактически заключается в подсчете количества каждого из числа и записи результата согласно полученным результатам подсчета. Реализовать этот алгоритм можно так:
Procedure Karman;

Const

N2=Nmax; {верхнее возможное значение числа}

Var

d:array[N1..N2] of longint; {массив для подсчета}

n,i,j:longint;

begin

read(n);{n - количество цифр}

begin

inc(d[a]);

end;

for j := N2 to N1 do {печатаем результат}

writeln(j);

end;
Эту «сортировку» называют еще «карманной сортировкой». Ее можно применять в случае, если тип переменных подлежащих сортировки является перечисляемым и есть ограничение на их значения.
Задание

1. Написать программу которая определяет какой символ чаще всего встречается в тексте