Сортировка подсчётом
Сортировка подсчётом — алгоритм сортировки массива,
при котором подсчитывается число одинаковых элементов. Алгоритм выгодно
применять, когда в массиве много элементов, но все они достаточно малы.
Описание алгоритма
Идея сортировки указана в её названии — нужно подсчитывать число
элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив
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; |
Литература
|
