Jestem już po sortowaniu bąbelkowym, przez wstawianie, wybieranie, scalanie i zliczanie, i chcę się wziąć teraz za sortowanie kubełkowe, ale tak jak widać po temacie mam problem ze zrozumieniem tego sposobu.
Na Wikipedii byłem.
Piszą tam m.in. że to sortowanie jest najczęściej stosowane, gdy liczby w zadanym przedziale są rozłożone jednostajnie.
Nie bardzo rozumiem stwierdzenia: przedział rozłożony jednostajnie.
Trochę przypomina mi ten sposób sortowanie przez scalanie, ale musi być różnica.
0
3
przedział rozłożony jednostajnie
To nie przedział jest rozłożony jednostajnie, tylko liczby są rozłożone jednostajnie w zadanym przedziale. Czyli jak masz 10 liczb w przedziale[1,100]to chcesz przykładowo jedną liczbę między 1 a 10, jedną między 10 a 20 itd. zamiast wszystkich liczb o wartości między 70 a 75.
Jak masz przez scalanie to liczba z lewego podprzedziału może być większa niż liczba z prawego podprzedziału, natomiast w kubełkowym wszystkie w lewym kubełku są mniejsze niż te w prawym kubełku. Dodatkowo możesz mieć więcej kubełków niż 2 (dla 2 to jest prawie jak quick-sort).
Masz tu wizualizację algorytmu: https://www.cs.usfca.edu/~galles/visualization/BucketSort.html
0
A jak to jest zrobione że według wizuaizacji z https://www.cs.usfca.edu/~galles/visualization/BucketSort.html pod jednym indeksem znajduje się kilka wartości? Tak jakby pod dany indeks dolnej tablicy był podpięty vector