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

Odwiedź Binarnie.pl na FB

Cześć, jeżeli publikowane treści okażą się dla Ciebie pomocne to zapraszam Cię do polubienia Binarnie.pl na Facebook'u 👍 Bądź pewien, że nic nowego Cię nie ominie 👨🏻‍💻


This will close in 20 seconds