Rozdziela elementy do kubełków według zakresów wartości i sortuje każdy kubełek osobno.
Sortowanie kubełkowe to algorytm nieporównawczy – zamiast zestawiać elementy operatorami </>, wykorzystuje same wartości kluczy jako indeksy do tablicy kubełków.
Zasada działania (ten wariant): tworzymy tablicę "kubełków" – po jednym dla każdej możliwej wartości w danych. Następnie iterujemy po danych wejściowych i dla każdej wartości zwiększamy licznik w odpowiednim kubełku. Na koniec odczytujemy kubełki w kolejności i tworzymy posortowaną tablicę.
Kiedy używać: gdy znamy zakres wartości i jest on niewielki w stosunku do liczby elementów. Idealne dla danych typu wiek osób (0–120), oceny (1–6), czy elementy z ograniczonego zbioru.
Cecha charakterystyczna: stabilny i nie wykonuje porównań elementów.
Prześledź obie fazy algorytmu: najpierw zliczanie – każdy element z tablicy wejściowej trafia do kubełka o indeksie równym jego wartości – a potem odczyt, czyli czytanie kubełków po kolei, od najmniejszej wartości do największej.
Tablica wejściowa:
Kubełki (indeks = wartość):
Wynik:
Tablica wejściowa. Naciśnij „Krok" lub „Auto".
funkcja sortuj_kubelkowo(T, n): jeżeli n = 0: zwróć T // znajdujemy maksymalną wartość max_wartosc ← T[0] dla i od 1 do n - 1: jeżeli T[i] > max_wartosc: max_wartosc ← T[i] // tworzymy kubełki - jeden dla każdej możliwej wartości kubelki ← tablica zer o rozmiarze max_wartosc + 1 // zliczamy wystąpienia dla i od 0 do n - 1: kubelki[T[i]] ← kubelki[T[i]] + 1 // odbudowujemy posortowaną tablicę wynik ← pusta lista dla i od 0 do max_wartosc: dla j od 1 do kubelki[i]: dodaj i do wynik zwróć wynik
def sortowanie_kubelkowe(tablica):
if not tablica:
return tablica
max_wartosc = max(tablica)
kubelki = [0] * (max_wartosc + 1)
# zliczamy wystąpienia
for x in tablica:
kubelki[x] += 1
# odtwarzamy posortowaną tablicę
wynik = []
for i in range(max_wartosc + 1):
wynik.extend([i] * kubelki[i])
return wynik
# Przykład użycia
dane = [4, 2, 2, 8, 3, 3, 1]
print(sortowanie_kubelkowe(dane))
# Wynik: [1, 2, 2, 3, 3, 4, 8]W ogólnej wersji bucket sortu każdy kubełek obejmuje zakres wartości (np. 0–9, 10–19...), a jego zawartość trzeba dodatkowo posortować innym algorytmem, np. przez wstawianie. Tutaj, dla uproszczenia, każdy kubełek odpowiada jednej konkretnej wartości – więc nic już nie trzeba sortować, wystarczy policzyć wystąpienia i odczytać kubełki po kolei. To wariant czasem nazywany sortowaniem przez zliczanie (counting sort).
Nie wprost – indeksem kubełka jest tu sama wartość, a tablica nie może mieć ujemnych indeksów. Rozwiązanie jest proste: znajdujemy najmniejszą wartość w danych, dodajemy jej wartość bezwzględną do każdego elementu (żeby wszystkie stały się nieujemne), sortujemy, a na końcu tę samą wartość odejmujemy z powrotem.
To sortowanie pozycyjne (rozkłada elementy po wartości), a nie porównawcze – nigdy nie zestawia ze sobą dwóch elementów operatorem < czy >, jak robią to sortowanie szybkie czy sortowanie przez scalanie. Dzięki temu w dobrych warunkach osiąga O(n + k) – szybciej niż dolna granica O(n log n) dla sortowań porównawczych – ale kosztem dodatkowej pamięci O(k) i założenia, że zakres wartości jest znany i rozsądnie mały.
Gdy zakres wartości (k) jest dużo większy niż liczba elementów (n) – np. n = 100 liczb z zakresu 0–1 000 000. Wtedy tworzymy milion kubełków, z których prawie wszystkie zostają puste, a złożoność pamięciowa O(k) przestaje mieć jakikolwiek sens w porównaniu z rozmiarem danych.
Dla samych liczb pytanie o stabilność jest bezprzedmiotowe – nie da się odróżnić dwóch kubełków o tej samej wartości. Ale gdyby elementy niosły dodatkowe dane (np. sortowalibyśmy rekordy po jednym z pól), trzeba by dopisywać je do kubełka w kolejności napotkania, a przy odczycie zachować tę kolejność – wtedy algorytm pozostaje stabilny.
O(n + k)O(k)Czasowa O(n + k) – gdzie n to rozmiar tablicy wejściowej, a k to największa wartość (czyli liczba kubełków). Każdy element trafia do swojego kubełka w czasie stałym, a odczyt wszystkich kubełków kosztuje O(k) niezależnie od tego, ile z nich jest pustych – stąd suma O(n + k).
Dlaczego to szybciej niż O(n log n)? Każdy algorytm porównawczy – jak sortowanie szybkie czy sortowanie przez scalanie – ma dolne ograniczenie złożoności Ω(n log n): żaden z nich nie zejdzie poniżej tego progu. Sortowanie kubełkowe w ogóle nie porównuje elementów, więc to ograniczenie go nie dotyczy – przy znanym, niewielkim zakresie wartości kluczy osiąga czas liniowy O(n + k), gdy k jest porównywalne z n.
Pamięć O(k). To główny koszt tego podejścia: dla dużego zakresu wartości (np. liczb od 0 do 1 000 000 przy n = 100) algorytm tworzy milion kubełków, z czego niemal wszystkie zostają puste – wtedy jest bardzo nieefektywny pamięciowo, mimo że nadal formalnie poprawny.
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: