Всем привет! Подскажите пожалуйста какая сложность у сортировки подсчетом? Имеется ввиду метод сортировки в котором используется вспомогательный массив, который заполняется нулями.
Сколько будет выполнено сравнений и перестановок при выполнении сортировки методом подсчёта у массива {3, 1, 6, 13, 2, 0, 8} ?
Не подскажите, куда нужно сунуть счётчики srav и perest?
int max = A.Max();
Array.Copy(A, B, N + 1);
Array.Resize(ref B, max + 1);
for (int i = 0; i < max + 1; i++)
{
B[i] = 0;
}
for (int i = 0; i <= N; i++)
{
B[A[i]]++;
}
for (int i = 0, j = 0; i <= max; i++)
{
srav++;
while (B[i] > 0)
{
A[j] = i;
j++;
B[i]--;
perest++;
}
}
Заранее спасибо!