Witam.
Dziś na wykładzie prowadzący podał takie zadanko:
Macie nieograniczoną ilość pamięci, jakim sortowaniem posortowalibyście ciąg liczb?
0
1
Sortowanie przez zliczanie.
0
Jak nieograniczona ilość pamięci to sortowanie brute force.
1
Przez zliczanie (counting sort https://en.wikipedia.org/wiki/Counting_sort)
0
A czy sortowanie kubełkowe nie byłoby dobrym rozwiązaniem? Bym tak przydzielał liczby do kubełków aby w każdym była tylko jedna. Wtedy złożoność wynosiłaby O(n). Czy się mylę?
1
@AsemDlikeToBe w sensie zliczanie za pomocą hashmapy? Asymptotycznie byłoby O(n) przy założeniu że rozkład elementów byłby dobry (ale zauważ że to wcale nie takie proste!) ale wolniej od zliczania na zwykłej tablicy, przy założeniu że ilość liczb do sortowania jest znacznie większa od zakresu sortowanych liczb.
No i pamiętaj że to nie takie proste tak zrobić to hashowanie żeby nie było konfliktów a jednocześnie żeby nie zrobić tablicy o rozmiarze -max_int, max_int które sprowadzi sie do zwykłego zliczania :)