Сортировка подсчетом ("черпачная")
Применение
Сортируемые числа имеют диапазон возможных целых положительных значений, который достаточно мал по сравнению с сортируемым множеством. Например, миллион значений, каждое из которых не больше 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|, а при обратной записи вычитать.