Sortowanie kubełkowe – algorytm i implementacja w C++

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ę:

Sortowanie kubełkowe – implementacja w C++

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 – implementacja w C++

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
Dodaj komentarz