Wszystkie zagadnienia: Algorytmy
średni bucket sortmatura rozszerzona z informatyki

Sortowanie kubełkowe

Rozdziela elementy do kubełków według zakresów wartości i sortuje każdy kubełek osobno.

01

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:

4228331

Kubełki (indeks = wartość):

0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0

Wynik:

Tablica wejściowa. Naciśnij „Krok" lub „Auto".

02

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
03

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]
04

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.

05

Ć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

CzasowaO(n + k)
PamięciowaO(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:

Zadania z działu: Programowanie

↗

Powiązane zagadnienia