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:

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

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:

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

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. }

• Kod źródłowy Implementacja

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.

• Kod źródłowy Zadanie 1
• Kod źródłowy Zadanie 2