Спасибо вам за видео, проблема почти у всех кто показывает как алгоритм работает в том что выборка идет из чисел которые идут друг за другом. Более наглядно будет с вариантом: 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
Здорово, вы этой связи могу порекомендовать quiksort с minvalue, maxvalue. Срединный элемент находится делением диапазона minvalue maxvalue на 2 и функция гарантирована от зависаний на любых массивах
тут асимптотика не O(2n + k) , а O(3n + k), мы же как-то нашли что вспомогательный массив - размера k, то есть искали или количество неповторяющихся элементов или min + max
@@danylosmahliuk8591 почему n + n + k = n + k? Разве не должно быть 2n + k ? Или это как-то по другому работает? И ещё смущает, что в итоге мы получаем не сам упорядоченный массив, а запись из которой его можно разложить. На это же то же потребуются операции?
@@PavelS-m5r Вместо вывода каждого значения можно помещать его в новый массив, который и получится отсортированным. Или даже перезаписывать старый массив, если он не нужен.
если делать так как вы показали мы не сможем нормально сортировать например строки. если сделать из массива с колличеством элементов сделать массив с индексами то алгоритм можно превратить в устойчивую сортировку.
Вы не описали критерий, по которому хотите сортировать, если он определяется уникальным числовым ключом то трогать сами структуры скорее всего нет смысла.
Можно пойти в лоб и создать массив размера n. Если соответствующих значений в исходном массиве нет, то после подсчёта всех чисел соответствующие ячейки будут пустыми. Например, массив {2 9 7 9}, создадим массив для подсчёта из 9 ячеек, после подсчёта получим {0 1 0 0 0 0 1 0 2}. Выводим отсортированный массив: не выводим ни одной единицы, выводим одну двойку, и т.д. Но для такого варианта желательны дополнительные танцы с бубном, если минимальное и/или максимальное значение большое, и необходимы танцы, если есть отрицательные значения...
Все сортировки работают с числами... (любая сортировка сводится в итоге к сравнению чисел). Может вы хотели сказать цифр, а не чисел? Или натуральных чисел из небольшого диапазона (включая ноль) ?
Не все, а конкретно эта, работает именно с числами, применять целесообразно когда диапазон чисел много меньше сортируемого массива, к примеру массив из миллиона чисел, каждое из которых от 0 до 1000
Есть так называемый класс comparsion sort сортировок, они работают на любом множестве элементов с заданным порядком, порядок задаётся предикатом обладающим строго определёнными свойствами, элементы множества не обязательно числа.