Sortowanie kubełkowe

Słownik kwalifikacji INF.03 - Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych

Co to jest sortowanie kubełkowe?

Sortowanie kubełkowe (ang. bucket sort) to algorytm sortowania polegający na podziale danych na kilka przedziałów, nazywanych kubełkami. Każdy element trafia do kubełka odpowiadającego jego wartości, następnie elementy w kubełkach są sortowane, a na końcu wszystkie kubełki są scalane w jedną uporządkowaną listę.

Zasada działania

Algorytm wykonuje zwykle następujące kroki:

  1. Ustala zakres wartości danych, np. od najmniejszej do największej liczby.
  2. Dzieli zakres na n przedziałów, czyli kubełków.
  3. Umieszcza każdy element w odpowiednim kubełku.
  4. Sortuje dane wewnątrz każdego kubełka, np. prostym sortowaniem przez wstawianie.
  5. Łączy kubełki w kolejności od najmniejszych do największych wartości.

Kiedy jest skuteczne?

Sortowanie kubełkowe działa najlepiej, gdy dane są w miarę równomiernie rozłożone w znanym zakresie. Wtedy elementy trafiają do różnych kubełków i sortowanie wewnątrz nich jest szybkie.

Przykład

Dla liczb z zakresu 0-99 można utworzyć kubełki:

  • 0-19
  • 20-39
  • 40-59
  • 60-79
  • 80-99

Liczba 35 trafi do kubełka 20-39, a liczba 82 do kubełka 80-99.

Ważne na egzaminie

Jeśli w pytaniu pojawia się opis: podział danych na przedziały/kubełki, sortowanie kubełków i ich scalenie, poprawną odpowiedzią jest sortowanie kubełkowe.