Sortowanie kubełkowe
Algorytm sortowania kubełkowego (ang. bucket sort) to algorytm porządkujący dane w czasie liniowym. Dane, które mają zostać posortowane, muszą spełniać pewne kryteria. Po pierwsze, powinny być równo rozłożone. Po drugie, musimy znać ich zakres. W przypadku tego algorytmu sortowanie odbywa się w miejscu.
Algorytmy, w których sortowanie odbywa się w miejscu, do posortowania zbioru danych potrzebują stałej ilości pamięci komputera, niezależnej od rozmiaru danych wejściowych. W ich przypadku wszelkie potrzebne do otrzymania wyniku obliczenia są wykonywane w pamięci, w której znajdują się dane.
Nazwa tego sortowania łączy się z jego działaniem. Zakres danych do sortowania dzielony jest na określoną liczbę kubełków. Następnie dane przypisywane są do odpowiednich kubełków i sortowane w ich ramach.
Implementację sortowania kubełkowego przedstawiamy w e‑materiałach:
Sortowanie kubełkowe w języku C++Sortowanie kubełkowe w języku C++,
Sortowanie kubełkowe w języku JavaSortowanie kubełkowe w języku Java,
Sortowanie kubełkowe w języku PythonSortowanie kubełkowe w języku Python.
Więcej zadań? Sortowanie kubełkowe – zadania maturalneSortowanie kubełkowe – zadania maturalne
Prześledzisz kolejne kroki algorytmu sortowania kubełkowego.
Wyjaśnisz, w których sytuacjach warto zastosować sortowanie kubełkowe, a kiedy jest to rozwiązanie nieefektywne.
Scharakteryzujesz złożoność czasową algorytmu sortowania kubełkowego.
Zastosujesz sortowanie kubełkowe do porządkowania wybranych zbiorów danych.