Сортировка подсчетом (counting sort)

Описание алгоритма сортировки подсчетом (counting sort) и анализ временной сложности

Хотите начать программировать?

ВЫ МОЖЕТЕ ПОДДЕРЖАТЬ ПРОЕКТ:
Яндекс кошелек:
410014557804280

Webmoney:
R348962076583
Z840320799500
E301944634338

Ваши пожертвования помогают мне уделять больше времени и сил для создания обучающих материалов.

[demensdeum_live]

Спасибо вам за видео, проблема почти у всех кто показывает как алгоритм работает в том что выборка идет из чисел которые идут друг за другом.
Более наглядно будет с вариантом:
1, 9, 1, 4, 6, 4, 4
Тогда массив для подсчета будет:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (мин число 0, макс 9)
с итоговыми счетчиками
0, 2, 0, 0, 3, 0, 1, 0, 0, 1
итого
1, 1, 4, 4, 4, 6, 9

[JJJoraKornev]

Ну а как происходит сама сортировка не указана.
Через 2 встроенных цикла?
Можно ли использовать ХешМап?

[evgeniykorniloff]

Здорово, вы этой связи могу порекомендовать quiksort с minvalue, maxvalue. Срединный элемент находится делением диапазона minvalue maxvalue на 2 и функция гарантирована от зависаний на любых массивах

[mchizhkova]

тут асимптотика не O(2n + k), а O(3n + k), мы же как-то нашли что вспомогательный массив - размера k, то есть искали или количество неповторяющихся элементов или min + max

[ЮрийБаринов-ся]

если делать так как вы показали мы не сможем нормально сортировать например строки.
если сделать из массива с колличеством элементов сделать массив с индексами то алгоритм можно превратить в устойчивую сортировку.

[MrGenFox]

Обычно сортируют не числа, а какие-то структуры у которых есть ключ в виде числа. Как в таком случае работать с Вашей сортировкой?

[YuriyBrazhnyk]

А список всех уникальных чисел в отсортированном виде вы как получили? это само по себе жестяковая задачка...

[litbeatzzz]

Все сортировки работают с числами... (любая сортировка сводится в итоге к сравнению чисел). Может вы хотели сказать цифр, а не чисел? Или натуральных чисел из небольшого диапазона (включая ноль) ?