Sortowanie kubełkowe
Rozdziela elementy do kubełków według zakresów wartości i sortuje każdy kubełek osobno.
Opis
Sortowanie kubełkowe układa liczby bez porównywania ich ze sobą. Zamiast tego po prostu liczysz, ile razy pojawia się każda wartość.
Jak to działa: dla każdej możliwej wartości przygotowujesz osobny licznik. Przechodzisz przez tablicę i za każdym razem, gdy widzisz jakąś liczbę, dodajesz jej licznikowi jeden. Na końcu wypisujesz wartości po kolei – każdą tyle razy, ile ją naliczyłeś. Tak powstaje gotowa, posortowana tablica.
Kiedy się sprawdza: gdy liczby są z małego zakresu, na przykład oceny 1–6 albo wiek osób. Wtedy liczników jest niewiele i wszystko idzie szybko. Gdy wartości mogą być ogromne (np. do miliona), metoda marnuje mnóstwo miejsca na puste liczniki.
Na maturze: rozpoznaj, że przy małym, znanym zakresie wartości to zwykle najszybszy sposób sortowania.
Wizualizacja
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".
Pseudokod
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
Implementacja w Pythonie i C++
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]#include <vector>
#include <iostream>
using namespace std;
vector<int> sortowanie_kubelkowe(const vector<int>& t) {
if (t.empty()) return t;
int maks = t[0];
for (int x : t)
if (x > maks) maks = x;
// jeden kubełek (licznik) na każdą możliwą wartość
vector<int> kubelki(maks + 1, 0);
// zliczamy wystąpienia
for (int x : t)
kubelki[x]++;
// odtwarzamy posortowaną tablicę
vector<int> wynik;
for (int i = 0; i <= maks; i++)
for (int j = 0; j < kubelki[i]; j++)
wynik.push_back(i);
return wynik;
}
int main() {
vector<int> dane = {4, 2, 2, 8, 3, 3, 1};
vector<int> posortowane = sortowanie_kubelkowe(dane);
for (int x : posortowane) cout << x << " ";
// Wynik: 1 2 2 3 3 4 8
}Najczęściej zadawane pytania
Czym ten wariant różni się od "klasycznego" sortowania kubełkowego z zakresami?
W ogólnej, klasycznej wersji sortowania kubełkowego 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.
Czy sortowanie kubełkowe radzi sobie z liczbami ujemnymi?
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.
Czym sortowanie kubełkowe różni się od algorytmów takich jak sortowanie szybkie czy przez scalanie?
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.
Kiedy sortowanie kubełkowe sprawdza się słabo?
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.
Czy sortowanie kubełkowe jest stabilne?
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.
Ćwiczenie
Popracujemy na tablicy [2, 0, 3, 2, 1, 0, 2]. Policz odpowiednie wartości i wpisz je, potem kliknij Sprawdź.
Najpierw zliczamy, ile razy pojawia się każda wartość. Wartość 0 występuje razy, wartość 1 występuje raz, wartość 2 występuje razy, a wartość 3 występuje raz.
Uzupełnij tabelę liczników kubełków:
| Wartość | Ile razy wystąpiła |
|---|---|
| 0 | |
| 1 | |
| 2 | |
| 3 |
Teraz odczytujemy kubełki po kolei, od najmniejszej wartości. Posortowana tablica to [0, 0, 1, 2, 2, 2, 3], więc jej pierwszy element to , a ostatni to .
Dla tej tablicy n (liczba elementów) wynosi , a największa wartość, czyli liczba potrzebnych kubełków minus jeden, to .
Złożoność obliczeniowa
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.
Przećwicz w zadaniach maturalnych
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Powiązane zagadnienia
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: