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.742 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


49
komentarze: 18 | wyświetlenia: 65802
37
komentarze: 9 | wyświetlenia: 29298
50
komentarze: 27 | wyświetlenia: 64475
40
komentarze: 19 | wyświetlenia: 33311
32
komentarze: 12 | wyświetlenia: 27229
12
komentarze: 3 | wyświetlenia: 30405
11
komentarze: 2 | wyświetlenia: 33541
11
komentarze: 1 | wyświetlenia: 87047
10
komentarze: 2 | wyświetlenia: 6369
19
komentarze: 10 | wyświetlenia: 21606
18
komentarze: 11 | wyświetlenia: 9479
21
komentarze: 9 | wyświetlenia: 12701
17
komentarze: 10 | wyświetlenia: 11024
 
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