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

Сортировка подсчётом — алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.

Описание алгоритма

Идея сортировки указана в её названии — нужно подсчитывать число элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив A из миллиона натуральных чисел, меньших 100. Тогда можно создать вспомогательный массив B из 99 (1..99) элементов, «пробежать» весь исходный массив и вычислять частоту встречаемости каждого элемента — то есть если A[i]=a, то B[a] следует увеличить на единицу. Затем «пробежать» счетчиком i массив B, записывая в массив A число i B[i] раз.

Временная и ёмкостная сложности алгоритма

Пусть n — длина исходного массива, k — максимальное число в массиве.

Тогда временная сложность алгоритма равна O(n+k), а ёмкостная — O(n+k).

Реализация на C
void CountingSort (int *a, int n, int min, int max)
{
int i, j, c;
int *b;
assert(n > 0);
assert(min <= max);
b = (int *)calloc(max - min + 1, sizeof(int));
assert(b != NULL);
for (i = 0; i <= n - 1; ++i) ++b[a[i] - min];
for (j = min; j <= max; ++j)
{
c = b[j - min];
while (c > 0)
{
*a = j; ++a; --c;
}
}
free(b);
}
Реализация на Pascal

function CountingSort(_array: OF INTEGER): TIntegerArray;
var i, n, j, temp_variable: integer;
Sorted_array: TIntegerArray;
begin
Counter:=0;

SetLength(Sorted_array, Length(numeric_array));
n:= Length(numeric_array)-1;

for i:=0 to n do
begin
temp_variable:=0;
for j:=0 to n do
if _array[i]>_array[j] then inc(temp_variable);
Sorted_array[temp_variable]:=_array[i];
end;
Result:=Sorted_array;
end;

Литература

Ананий В. Левитин Глава 7. Пространственно-временной компромисс: Сортировка подсчетом // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 307-310. ISBN 0-201-74395-7
Википедия


Алгоритмы сортировок и их реализации
	Главная