Тёмный

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

Evgeniy M
Подписаться 3,1 тыс.
Просмотров 27 тыс.
50% 1

Опубликовано:

 

30 окт 2024

Поделиться:

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист
Посмотреть позже
Комментарии : 33   
@demensdeum_live
@demensdeum_live 2 года назад
Спасибо вам за видео, проблема почти у всех кто показывает как алгоритм работает в том что выборка идет из чисел которые идут друг за другом. Более наглядно будет с вариантом: 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
@1996806
@1996806 8 лет назад
Спасибо! Отличные уроки!
@lambdaway
@lambdaway 8 лет назад
+Адлена Лавлейс благодарю!)
@fake_kira
@fake_kira Год назад
Спасибо большое, полезное видео
@dzianisdashkevich1848
@dzianisdashkevich1848 4 года назад
спасибо, одно из лучших объяснений!
@vangog63
@vangog63 2 года назад
Хорошо пояснил, спасибо!
@viktoryiakalamiyets3569
@viktoryiakalamiyets3569 4 года назад
Спасибо, все доходчиво!
@Igor_Grey
@Igor_Grey 4 года назад
Спасибо за доходчивое объяснение!
@lambdaway
@lambdaway 4 года назад
Благодарю🙂
@АндрейБойчук-м6ш
Спасибо! Быстро и понятно.
@JJJoraKornev
@JJJoraKornev 7 лет назад
Ну а как происходит сама сортировка не указана. Через 2 встроенных цикла? Можно ли использовать ХешМап?
@evgeniykorniloff9974
@evgeniykorniloff9974 2 года назад
Здорово, вы этой связи могу порекомендовать quiksort с minvalue, maxvalue. Срединный элемент находится делением диапазона minvalue maxvalue на 2 и функция гарантирована от зависаний на любых массивах
@mchizhkova
@mchizhkova 5 лет назад
тут асимптотика не O(2n + k) , а O(3n + k), мы же как-то нашли что вспомогательный массив - размера k, то есть искали или количество неповторяющихся элементов или min + max
@danylosmahliuk8591
@danylosmahliuk8591 4 года назад
2n или 3n - в итоге берём за n
@PavelS-m5r
@PavelS-m5r 4 года назад
@@danylosmahliuk8591 почему n + n + k = n + k? Разве не должно быть 2n + k ? Или это как-то по другому работает? И ещё смущает, что в итоге мы получаем не сам упорядоченный массив, а запись из которой его можно разложить. На это же то же потребуются операции?
@danilbutygin238
@danilbutygin238 4 года назад
@@PavelS-m5r он про то что O(An+B) приблеженно равно O(n)
@nikelsad
@nikelsad 3 года назад
@@PavelS-m5r Вместо вывода каждого значения можно помещать его в новый массив, который и получится отсортированным. Или даже перезаписывать старый массив, если он не нужен.
@A0l0e0k0s1
@A0l0e0k0s1 4 года назад
Годно
@ЮрийБаринов-с2я
@ЮрийБаринов-с2я 3 года назад
если делать так как вы показали мы не сможем нормально сортировать например строки. если сделать из массива с колличеством элементов сделать массив с индексами то алгоритм можно превратить в устойчивую сортировку.
@MrGenFox
@MrGenFox 3 года назад
Обычно сортируют не числа, а какие-то структуры у которых есть ключ в виде числа. Как в таком случае работать с Вашей сортировкой?
@lambdaway
@lambdaway 3 года назад
Вы не описали критерий, по которому хотите сортировать, если он определяется уникальным числовым ключом то трогать сами структуры скорее всего нет смысла.
@bogbond
@bogbond 6 лет назад
спасибо!
@YuriyBrazhnyk
@YuriyBrazhnyk 3 года назад
А список всех уникальных чисел в отсортированном виде вы как получили? это само по себе жестяковая задачка...
@nikelsad
@nikelsad 3 года назад
Можно пойти в лоб и создать массив размера n. Если соответствующих значений в исходном массиве нет, то после подсчёта всех чисел соответствующие ячейки будут пустыми. Например, массив {2 9 7 9}, создадим массив для подсчёта из 9 ячеек, после подсчёта получим {0 1 0 0 0 0 1 0 2}. Выводим отсортированный массив: не выводим ни одной единицы, выводим одну двойку, и т.д. Но для такого варианта желательны дополнительные танцы с бубном, если минимальное и/или максимальное значение большое, и необходимы танцы, если есть отрицательные значения...
@YuriyBrazhnyk
@YuriyBrazhnyk 3 года назад
@@nikelsad та хоть как хотите сортируйте, эта операция не учтена в сложности алгоритма...
@sakensaken1590
@sakensaken1590 4 года назад
С отрицательными не работает?
@lambdaway
@lambdaway 4 года назад
Да ничто не мешает отрицательные числа в массив поместить
@litbeatzzz
@litbeatzzz 4 года назад
Все сортировки работают с числами... (любая сортировка сводится в итоге к сравнению чисел). Может вы хотели сказать цифр, а не чисел? Или натуральных чисел из небольшого диапазона (включая ноль) ?
@lambdaway
@lambdaway 4 года назад
Не все, а конкретно эта, работает именно с числами, применять целесообразно когда диапазон чисел много меньше сортируемого массива, к примеру массив из миллиона чисел, каждое из которых от 0 до 1000
@litbeatzzz
@litbeatzzz 4 года назад
@@lambdaway А с чем по-вашему работают остальные сортировки ?
@lambdaway
@lambdaway 4 года назад
Я имею виду, что сортировать можно не только числа
@lambdaway
@lambdaway 4 года назад
Вы наверное имеете ввиду, что всегда можно пронумеровать множество и имея порядок и свести к сравнению чисел любую сортировку?
@lambdaway
@lambdaway 4 года назад
Есть так называемый класс comparsion sort сортировок, они работают на любом множестве элементов с заданным порядком, порядок задаётся предикатом обладающим строго определёнными свойствами, элементы множества не обязательно числа.
Далее
Сортировка подсчётом
6:41
Просмотров 3,7 тыс.
Learn Counting Sort Algorithm in LESS THAN 6 MINUTES!
5:59