Login lub e-mail Hasło   

Sortowanie kubełkowe

Wprowadzenie Sortowanie kubełkowe ( bucket sort ) to algorytm wynaleziony w 1956 r. przez E.J. Issaca i R.C. Singletona , działający w czasie liniowym (O(n)). Liczby przeznaczon...
Wyświetlenia: 8.546 Zamieszczono 29/10/2006

Wprowadzenie

Sortowanie kubełkowe (bucket sort) to algorytm wynaleziony w 1956 r. przez E.J. Issaca i R.C. Singletona, działający w czasie liniowym (O(n)). Liczby przeznaczone do tego sortowania powinny być liczbami z przedziału [0;1) i powinny być dosyć równo rozłożone w tymże przedziale. Cały algorytm opiera się na podziale przedziału [0;1) na pewną ilość równych podprzedziałów, tzw. kubełków. Następnie każda z liczb przeznaczona do sortowania jest "wrzucana" do odpowiedniego kubełka. Aby otrzymać posortowane liczby najpierw sortuje się liczby w każdym z kubełków, a następnie łączy się je wszystkie po kolei.

 

Przykład

W przykładzie poniżej przedstawiłem sortowanie kubełkowe dla 10 kubełków. Kubełki są ponumerowane od 0 do 9. Każda liczba trafia do kubełka takiego, jaką ma pierwszą cyfrę po przecinku. Oto liczby przeznaczone do posortowania:

0,78 0,15 0,26 0,02 0,64 0,76 0,63 0,59 0,25 0,74 0,15 0,18 0,82 0,79 0,39

Teraz każdą z liczb należy wrzucić do odpowiedniego kubełka. Jak to jest napisane powyżej zależy to od pierwszej liczby po przecinku danej liczby. Poniżej przedstawiam liczby wraz z numer kubełka do którego trafią:

Liczba 0,78 0,15 0,26 0,02 0,64 0,76 0,63 0,59 0,25 0,74 0,15 0,18 0,82 0,79 0,39
Numer kubełka: 7 1 2 0 6 7 6 5 2 7 1 1 8 7 3

Oto kubełki wraz z liczbami, które zostały po kolei do nich wrzucone:

Kubełek Liczby
0 0,02
1 0,15; 0,15; 0,18
2 0,26; 0,25
3 0,39
4  
5 0,59
6 0,64; 0,63;
7 0,78; 0,76; 0,74; 0,79
8 0,82
9  

Liczby zostały już przydzielone do odpowiednich kubełków. Teraz należy je posortować w każdym z nich. Po sortowaniu otrzymujemy:

Kubełek Liczby
0 0,02
1 0,15; 0,15; 0,18
2 0,25; 0,26
3 0,39
4  
5 0,59
6 0,63; 0,64;
7 0,74; 0,76; 0,78; 0,79
8 0,82
9  

Teraz wystarczy po kolei połączyć zawartość wszystkich kubełków i liczby będą już posortowane. W naszym przypadku wygląda to następująco:

0,02 0,15 0,15 0,18 0,25 0,26 0,39 0,59 0,63 0,64 0,74 0,76 0,78 0,79 0,82

I w ten sposób doszliśmy do końca algorytmu sortowania kubełkowego.

Na koniec parę uwag. Do reprezentacji kubełków najlepiej jest użyć struktur danych zwanych listami. Jako algorytmu do sortowania kubełków można użyć sortowania przez wstawianie. Mimo, że ma on złożoność O(n2) to ogólnie sortowanie kubełkowe ma złożoność O(n). Wynika to z tego, że dane wejściowe są równomiernie rozłożone w przedziale [0;1).

W przypadku, gdy mamy do posortowania liczby spoza przedziału [0;1) to należy każdą z nich podzielić przez sumę największej liczby w danych ciągu i liczby 1. W ten sposób wszystkie liczby będą w zadanym przedziale. Należy dodać w tym przypadku dodać 1 do największej liczby, bo gdy będziemy dzielić właśnie ją to otrzymamy liczbę 1, a ta liczba do przedziału podanego wyżej nie należy.

Podobne artykuły


8
komentarze: 79 | wyświetlenia: 1153
111
komentarze: 32 | wyświetlenia: 60728
54
komentarze: 56 | wyświetlenia: 32590
54
komentarze: 68 | wyświetlenia: 31293
50
komentarze: 27 | wyświetlenia: 63526
49
komentarze: 18 | wyświetlenia: 64978
39
komentarze: 50 | wyświetlenia: 23278
39
komentarze: 30 | wyświetlenia: 28846
37
komentarze: 9 | wyświetlenia: 28520
36
komentarze: 37 | wyświetlenia: 23499
34
komentarze: 21 | wyświetlenia: 26317
32
komentarze: 12 | wyświetlenia: 26675
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska