Strona główna » Algorytmy » Sortowanie » Sortowanie Kubełkowe
 

Sortowanie Kubełkowe

O algorytmie

Sortowanie kubełkowe (ang. bucket sort) wrzuca elementy sortowanej tablicy do n kubełków. Każdy kubełek zawiera liczby z określonego przedziału. Każdy kubełek oddzielnie zostaje posortowany. Algorytm na sam koniec tworzy tablicę końcową pobierając kolejne dane z kolejnych kubełków. Zaletą tego rozwiązania jest dowolność sortowanych danych.

Algorytm najlepszą złożoność ma dla danych równo rozłożonych. Wtedy złożoność czasowa wynosi tyle samo co w przypadku algorytmu sortowanie Szybkiego. Jednak w przypadku, gdy w każdym kubełku znajdzie się tylko jeden element to algorytm zachowuje się jak Sortowanie przez zliczanie. Przyjmuje się, że dane powinny być z przedziału [0, 1]. W przypadku, gdy liczby są spoza tego zakresu wystarczy rozpatrywaną liczbę podzielić przez maksymalny element listy i na tej podstawie przyporządkować element do kubełka.

Przykład

Zakres dowolny

Załóżmy, że tablica do posortowania to L:={15, 24, 21, 31, 4, 26, 11, 12}. Na początek należy ustalić zakres liczb (o ile nie jest podany), a następnie stwierdzić na ile kubełków zostanie podzielona lista. W tym przypadku zakres wynosi [4, 31], a dane zostaną podzielna na n = 4 kubełków. Następny krok polega na przyporządkowaniu danych do każdego kubełka:

Kubełek1.2.3.4.
Zakres[4, 11)[11, 18)[18, 25)[25, 31]
Elementy{4, 11}{15, 12}{24, 21}{26, 31}

Teraz dane w każdym kubełku można posortować dowolnym algorytmem:

Kubełek1.2.3.4.
Elementy{4, 11}{12, 15}{21, 24}{26, 31}

Ostatni krok polega na utworzeniu nowej listy, która będzie zawierać wszystkie elementy z kubełków. Innymi słowy pobierane są elementy z kolejnych kubełków w niezmienionej kolejności. Wtedy ostateczne wersja posortowanej listy L to L'={4, 11, 12, 15, 21, 24, 26, 31}.

Zakres [0, 1]

W przypadku ustalenie, że zakres sortowanych liczb wynosi [0, 1] ustalanie zakresów liczb w każdym z kubełków staje się bardziej oczywiste. W tym przypadku można to zastosować dzieląc każdą liczbę przez maksymalną liczbę z zakresu i na tej podstawie określić do którego kubełka należy liczba. Wtedy liczby mają następujące wartości:

Element152421314261112
Wartość~ 0.48~ 0.77~ 0.681~ 0.12~ 0.84~ 0.35~ 0.38

Wtedy przyporządkowanie elementów do kubełków wygląda następująco:

Kubełek1.2.3.4.
Zakres[0, 0.25)[0.25, 0.5)[0.5, 0.75)[0.75, 1]
Elementy{4}{15, 12, 11}{21}{24, 26, 31}

Dalsza część jest zgodna z poprzednim przykładem. Drugi przypadek tworzy bardziej przejrzyste zakresy przyporządkowania, ale wybrana metoda przyporządkowywania jest dowolna. Obie sprowadzają się do tego samego, a pierwsza jest uogólnieniem drugiej, która z kolei tworzy uniwersalny sposób dla dowolnego typu danych.

Implementacja

Ze względu na modyfikowanie listy w funkcji bucketSort() funkcja przyjmuje wektor liczb oraz ten sam typ zmiennej zwraca. Do sortowania wewnątrz kubełka został zastosowany algorytm sortowanie Szybkiego:

  1. void bucketSort(vector<unsigned int> &lista, int k) {
  2.   vector< vector<unsigned int> > kubelki;
  3.   for(int i = 0; i < k; i++)
  4.     kubelki.push_back(vector<unsigned int>());
  5.   unsigned int max = lista[0];
  6.   for(int i = 0; i < lista.size(); i++){
  7.     if(lista[i] > max){
  8.       max= lista[i];
  9.     }
  10.   }
  11.   max++;
  12.   for(int i = 0; i < lista.size(); i++)
  13.     kubelki[double(lista[i])/double(max)*k].push_back(lista[i]);
  14.   for(int i = 0; i < k; i++)
  15.     sort(kubelki[i].begin(), kubelki[i].end());
  16.   lista.clear();
  17.   for(int i = 0; i < k; i++)
  18.     for(int j = 0; j < kubelki[i].size(); j++)
  19.       lista.push_back(kubelki[i][j]);
  20. }

(1.) Funkcja nie będzie zwracać nic - posortuje wektor lista w miejscu. Argument k określa do ilu kubełków trafią elementy tablicy. (2.) Utworzenie listy kubełków i (3. - 4.) dodanie do niej k kubełków. (5. - 10.) Wyszukiwanie największego elementu na liście. (11.) Zakres max warto zwiększyć o 1, ponieważ jeśli trafi się liczba będąca maksymalną wartością listy to uzyskamy, że chcemy wsadzić ją do kubełka k, który ni istnieje, bo kubełki będą numerowane od 0 do k-1. (12. - 13.) Wszystkie elementy są wrzucane do odpowiedniego kubełka. (14. - 15.) Następnie każdy kubełek jest oddzielnie sortowany. (16.) Wszystkie pierwotne elementy lista zostają usunięte, a (17. - 19.) kolejne elementy z kolejnych kubełków zostają dodane na ich miejsce.

Testowanie funkcji

Powyższą funkcję bucketSort() można przetestować przy pomocy poniższego kodu. Po uruchomieniu program najpierw wczyta n - ile elementów ma lista, potem k - do ilu kubełków mają być powrzucane elementy, a potem n liczb naturalnych, które są kolejnymi elementami listy.

  1. int main () {
  2.   int n, k, t;
  3.   cin >> n >> k;
  4.   vector< unsigned int > lista;
  5.   for(int i = 0; i < n; i++){
  6.     cin >> t;
  7.     lista.push_back(t);
  8.   }
  9.   bucketSort(lista, k);
  10.   for(int i = 0; i < n; i++)
  11.     cout << lista[i] << " ";
  12.   system("pause");
  13.   return 0;
  14. }

Zadania

Zadanie 1

Napisz rekurencyjną wersję algorytmu.

Zadanie 2

Napisz program, który posortuje listę na której znajdują się zarówno elementy dodatnie jak i ujemne.