Sortowanie kubełkowe – algorytm i implementacje w C++, Javie i Python

Nadszedł kolejny piątek, a wraz z nim kolejna część „Piątku z sortowaniem”. Czy jesteście gotowi na poznanie nowego algorytmu? Dziś pod lupę weźmiemy sortowanie kubełkowe (bucket sort). Bierzmy się do roboty.

Działanie

Algorytm sortowania kubełkowego jest znacznie przystępniejszy, od omawianego w poprzednim tekście sortowania binarnego. Jest on szczególnie przyjazny, w przypadku sortowania liczb całkowitych. Jak zwykle, wytłumaczmy na początku, w jaki sposób funkcjonuje ten algorytm.

Jego działanie, dzielimy na kilka prostych kroków. W pierwszym z nich, określamy dwa indeksy ymin i ymax, które mówią nam o najmniejszej i największej wartości, występującej w zbiorze. Wartości te przydadzą nam się głównie w implementacji tego algorytmu. Następnie przygotowujemy „kubełki” zliczające ilość wystąpień danych wartości w zborze. Ilość „kubełków”, możemy obliczyć ze wzoru ymin – ymax +1.

W kolejnym z kroków zliczamy liczbę wystąpień poszczególnych elementów, zwiększając wartość „kubełka” o indeksie, który odpowiada indeksowi rozpatrywanego elementu. Np. gdy natkniemy się na element o wartości 5, zwiększamy wartość „kubełeka” o indeksie 5.

W ostatnim kroku, tworzymy nowy zbiór. By tego dokonać, przechodzimy przez wszystkie liczniki, dodając do zbioru tyle poszczególnych elementów, ile ma wartość odpowiadającego mu kubełka. W ten właśnie prosty sposób otrzymamy posortowany zbiór wejściowy.

grupa wsparcia matura z informatyki

Przykład – liczby całkowite

Nic lepiej nie pomoże zrozumieć algorytmu, jak prosty przykład. Weźmy zbiór { 1, 5, 1, 5, 1, 2, 4, 5 }. W pierwszym kroku wyznaczmy ymin i ymax. Wynoszą one w tym przypadku 1 oraz 5. Tworzymy więc 5 „kubełków”:

B1 = 0, B2 = 0, B3 = 0, B4 = 0, B5 = 0

W kolejnym kroku liczymy ilość wystąpień poszczególnych elementów, zapisując je w kubełkach:

B1 = 3, B2 = 1, B3 = 0, B4 = 1, B5 = 3

Kończymy zapisując do nowego zbioru daną ilość elementów o wartościach indeksów kubełków. W ten sposób otrzymujemy: { 1,1,1,2,4,5,5,5 }. Zbiór ten odpowiada posortowanemu zbiorowi wejściowemu. By dodatkowo ułatwić zrozumienie tego procesu, spójrzcie na poniższą animację:



Więcej przydatnych algorytmów znajdziesz w tej książce

Sortowanie kubełkowe – implementacje

C++

Java

Python

Przykład – liczby ułamkowe

Sortowanie kubełkowe nie służy jednak tylko i wyłącznie do sortowania liczb całkowitych. Można nim sortować także liczby typu float. Tu sprawa robi się jednak nieco bardziej skomplikowana. Podobnie jak w przypadku liczb całkowitych, tworzyć będziemy „kubełki”. Tym razem, nie będą one jedynie licznikami, a będą strukurami przechowującymi wartości w wyznaczonych zakresach. Przykładowo, kubełek o indeksie 0, będzie przechowywał liczby w zakresie [0, 1). Nie wystarczy nam więc jedynie dodać liczby do kubełków. W końcowym kroku należy posortować poszczególne kubełki, przy pomocy innego algorytmu sortowania np. sortowaniem przez wstawianie, który również omawialiśmy w „Piątku z sortowaniem”.

Poszczególne kroki będą więc wyglądać w następujący sposób:

  1. Wyznaczamy  ymin i ymax
  2. Tworzymy kubełki będące podzakresami
  3. Dodajemy poszczególne elementy zbioru do kubełków
  4. Sortujemy wszystkie kubełki
  5. Zapisujemy po kolei elementy ze wszystkich kubełków

Przykład – ułamki

Weźmy zbiór {0.48, 0.27, 0.12, 0.21, 0.43, 0.25}. W pierwszej kolejności wyznaczymy ymin i ymax, wynoszące 0.12 i 0.48, a następnie stwórzmy kubełki:

B1 = {}, B2 = {}, B3 = {}, B4 = {}

Kolejno umieszczamy każdy z elementów w kubełku, którego zakres odpowiada wartości danego elementu:

B1 = {0.12}, B2 = {0.27, 0.21, 0.25}, B3 = {}, B4 = {0.48, 0.43}

Jak zapewne widzicie, kubełki wymagają sortowania. To więc właśnie zrobimy:

B1 = {0.12}, B2 = {0.21, 0.25, 0.27}, B3 = {}, B4 = {0.43, 0.48}

W ostatnim kroku, łączymy wszystkie kubełki w nowy zbiór, otrzymując posortowany zbiór wejściowy mający postać {0.12, 0.21, 0.25, 0.27, 0.43, 0.48}.

Spójrzmy więc na animację, obrazującą działanie algorytmu w podanym przypadku:

Sortowanie kubełkowe dla ułamków dziesiętnych – implementacje

C++

Java

Python

Trochę teorii

Jest to niezwykle ciekawy algorytm, ze względu na swoją efektywność. Sortowanie kubełkowe, radzi sobie najlepiej ze zbiorami o dużej ilości elementów, lecz małym zakresie wartości. W przypadku zbioru stosunkowo małym zakresie, i dużej ilości elementów, algorytm ten będzie niezwykle efektywny, dążąc do optymistycznej złożoności O(n).

Niestety w pesymistycznym przypadku, ma on złożoność rzędu O(n2), czyli taką jak chociażby niesławne sortowanie bąbelkowe, którego opis znajdziecie tutaj.

Podsumowanie

Za nami kolejny algorytm sortowania, tym razem z dwoma implementacjami. Za tydzień spotykamy się ponownie, by poznać następny! Zapraszamy Was również na naszą facebookową grupę, na której znajdziecie materiały pomocnicze do matury z informatyki, dotyczące nie tylko algorytmów.

You Might Also Like
2 komentarze
  • Avatar photo
    mike_Y
    says:

    Cześć! Jestem uczniem liceum i akurat szukałem algorytmów sortujących ucząc się do matury. Trafiłem na twoją stronę. Przeczytałem artykuł, zrozumiałem algorytm, napisałem program, a następnie zdziwiłem się o ile jest krótszy od Twojego przykładowego. Czy to ja popełniłem gdzieś błąd? A może Ty napisałeś go specjalnie troszkę rozwleklej aby każdy go zrozumiał? Pozdrawiam!

    Poniżej wklejam moje rozwiązanie problemu w Pythonie 🙂

    from random import randrange as rr
    from pprint import pprint as pp

    tab = [rr(7) for i in range(20)]
    print(tab)

    def sortowanie_kubelkowe(tab):
    dict = {letter: tab.count(letter) for letter in set(tab)}
    tab.clear()
    for value, number_of_appearance in dict.items():
    for i in range(number_of_appearance):
    tab.append(value)
    return tab ,dict

    print(sortowanie_kubelkowe(tab))

    • Avatar photo
      msy
      says:

      Pominięto chyba najważniejsze zastosowanie sortowania kubełkowego – porządkowanie ciągów znaków, słów nad jakimś alfabetem i to dowolnej i różnej długości. Szczegóły w M.M.Sysło, Algorytmy, Helion 2016.

Dodaj komentarz

icon