0

Всем привет! Подскажите пожалуйста какая сложность у сортировки подсчетом? Имеется ввиду метод сортировки в котором используется вспомогательный массив, который заполняется нулями.

Сколько будет выполнено сравнений и перестановок при выполнении сортировки методом подсчёта у массива {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++;
    }
}

Заранее спасибо!

2
  • 1
    вот как раз свеженькое habr.com/ru/post/689738 23 сен 2022 в 9:49
  • @Эникейщик Большое спасибо! Как раз искал грамотно написанный код данной сортировки. Но у меня не получается посчитать количество сравнений и перестановок для массива {3, 1, 6, 13, 2, 0, 8}. Полученные мной значения не укладываются в сложность данной сортировки.
    – Pahomka
    23 сен 2022 в 10:15

1 ответ 1

2

Очень просто - эта сортировка не основана на сравнениях (Вики), так что их количество ноль, или O(n+к), если педантично учитывать изменение индексов в заголовках циклов. Эта сортировка не производит обменов, так что тоже ноль.

По вопросу в заголовке - сложность O(n+k), где n - количество элементов, k - диапазон значений.

2
  • @Pahomka не вставляйте код в комментарии, вставляйте в сам вопрос, его можно редактировать.
    – aepot
    23 сен 2022 в 12:05
  • 1
    @aepot поправил
    – Pahomka
    23 сен 2022 в 12:14

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.