Спасибо вам за видео, проблема почти у всех кто показывает как алгоритм работает в том что выборка идет из чисел которые идут друг за другом. Более наглядно будет с вариантом: 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

спасибо, одно из лучших объяснений!

Спасибо! Отличные уроки!

@lambdaway

8 жыл бұрын

+Адлена Лавлейс благодарю!)

Спасибо, все доходчиво!

Спасибо за доходчивое объяснение!

@lambdaway

3 жыл бұрын

Благодарю🙂

Спасибо! Быстро и понятно.

Спасибо большое, полезное видео

Хорошо пояснил, спасибо!

спасибо!

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

Годно

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

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

@danylosmahliuk8591

4 жыл бұрын

2n или 3n - в итоге берём за n

@user-ib1kw2ip7c

4 жыл бұрын

@@danylosmahliuk8591 почему n + n + k = n + k? Разве не должно быть 2n + k ? Или это как-то по другому работает? И ещё смущает, что в итоге мы получаем не сам упорядоченный массив, а запись из которой его можно разложить. На это же то же потребуются операции?

@danilbutygin238

3 жыл бұрын

@@user-ib1kw2ip7c он про то что O(An+B) приблеженно равно O(n)

@nikelsad

3 жыл бұрын

@@user-ib1kw2ip7c Вместо вывода каждого значения можно помещать его в новый массив, который и получится отсортированным. Или даже перезаписывать старый массив, если он не нужен.

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

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

@lambdaway

3 жыл бұрын

Вы не описали критерий, по которому хотите сортировать, если он определяется уникальным числовым ключом то трогать сами структуры скорее всего нет смысла.

С отрицательными не работает?

@lambdaway

3 жыл бұрын

Да ничто не мешает отрицательные числа в массив поместить

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

@nikelsad

3 жыл бұрын

Можно пойти в лоб и создать массив размера n. Если соответствующих значений в исходном массиве нет, то после подсчёта всех чисел соответствующие ячейки будут пустыми. Например, массив {2 9 7 9}, создадим массив для подсчёта из 9 ячеек, после подсчёта получим {0 1 0 0 0 0 1 0 2}. Выводим отсортированный массив: не выводим ни одной единицы, выводим одну двойку, и т.д. Но для такого варианта желательны дополнительные танцы с бубном, если минимальное и/или максимальное значение большое, и необходимы танцы, если есть отрицательные значения...

@YuriyBrazhnyk

3 жыл бұрын

@@nikelsad та хоть как хотите сортируйте, эта операция не учтена в сложности алгоритма...

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

@lambdaway

3 жыл бұрын

Не все, а конкретно эта, работает именно с числами, применять целесообразно когда диапазон чисел много меньше сортируемого массива, к примеру массив из миллиона чисел, каждое из которых от 0 до 1000

@litbeatzzz

3 жыл бұрын

@@lambdaway А с чем по-вашему работают остальные сортировки ?

@lambdaway

3 жыл бұрын

Я имею виду, что сортировать можно не только числа

@lambdaway

3 жыл бұрын

Вы наверное имеете ввиду, что всегда можно пронумеровать множество и имея порядок и свести к сравнению чисел любую сортировку?

@lambdaway

3 жыл бұрын

Есть так называемый класс comparsion sort сортировок, они работают на любом множестве элементов с заданным порядком, порядок задаётся предикатом обладающим строго определёнными свойствами, элементы множества не обязательно числа.