EG
хм, теоретически я это знаю, но практически чет не видел сортировок без обмена
Size: a a a
2020 August 21
D
хм, теоретически я это знаю, но практически чет не видел сортировок без обмена
ну как бы trie
SP
смотри @Psilon представь функцию min/max. они линейны, так?
ΑZ
тогда почему всегда его не юзать? Даже если ключей столько же сколько элементов O(n+n) = O(n)
SP
вот тут то же самое - просто проходишься по массиву и суешь в аккумулятор какбудто ищешь min, но у тебя 100 аккумуляторов
ΑZ
вот тут то же самое - просто проходишься по массиву и суешь в аккумулятор какбудто ищешь min, но у тебя 100 аккумуляторов
хм, ну ваще логично
ΑZ
но это не инплейс
EG
тогда почему всегда его не юзать? Даже если ключей столько же сколько элементов O(n+n) = O(n)
Потому что
Если ты сортируешь хотя бы u64, то у тебя будет k = 18446744073709551616
k это рендж.Если ты сортируешь хотя бы u64, то у тебя будет k = 18446744073709551616
EG
Если ты сортируешь потенциально бесконечные типы, вроде строк, то это вообще неприменимо
SP
а наебалово в том что просто на один итем у тебя больше времени
ΑZ
Потому что
Если ты сортируешь хотя бы u64, то у тебя будет k = 18446744073709551616
k это рендж.Если ты сортируешь хотя бы u64, то у тебя будет k = 18446744073709551616
O(n+18446744073709551616) = O(n) 🧟♀️
EG
Это для counting sort
EG
O(n+18446744073709551616) = O(n) 🧟♀️
Да, но константа очень большая. В реальности тебе, обычно, важна не асимптотика, а скорость выполнения на твоих типичных данных.
SP
O(n+18446744073709551616) = O(n) 🧟♀️
да, именно
EG
Поэтому это хорошо работает для значений, у которых маленький рендж.
ΑZ
ладно, шучу
ΑZ
просто я кроме обменных сортировок в реальности никаких не видел
ΑZ
где-то на границе знаний есть понимание что они есть
ΑZ
но квик/мерж/инсершн в зависимости от требований
ΑZ
и усё