Sortowanie kubełkowe

powrót

Sortowanie kubełkowe należy do algorytmów, które porządkują dane w czasie liniowym. Dane, które będziemy sortować muszą jednak spełniać pewne założenia - muszą być równo rozłożone i musimy znać ich zakres. Nie może być takiej sytuacji, że jeśli chcemy posortować, powiedzmy milion liczb całkowitych, należących do przedziału [0, 1000 000 000], gdzie 900 tysięcy jest nie większych niż np. 10 milionów. 

Zalety algorytmu:

• złożoność czasowa jest rzędu $$O(n)$$
• algorytm nie sortuje w miejscu, potrzebuje dodatkowej tablicy na kubełki
• jest łatwy w implementacji

Algorytm posiada także wady:

• dane muszą być równomiernie rozłożone, aby złożoność była liniowa
• trzeba znać dokładny rozstęp zbioru (różnicę między największą i najmniejszą wartością do posortowania)

Działanie algorytmu

Na początku założenia:

• liczby do posortowania znajdują się w przedziale [0, 2000 000 000)
• liczby są równomiernie rozłożone
• dla n liczb tworzymy n kubełków

W pierwszej kolejności wyznaczamy długość przedziału pojedynczego kubełka: $$p=2000000000/n$$

Dla ułatwienia, sortować będziemy 10 liczb, zatem$$p=2000000000/10=200000000$$

Poszczególne kubełki będą reprezentować następujące przedziały:

1. [0, 200 000 000)
2. [200 000 000, 400 000 000)
3. [400 000 000, 600 000 000)
4. [600 000 000, 800 000 000)
5. [800 000 000, 1000 000 000)
6. [1000 000 000, 1200 000 000)
7. [1200 000 000, 1400 000 000)
8. [1400 000 000, 1600 000 000)
9. [1600 000 000, 1800 000 000)
10. [1800 000 000, 2000 000 000)

Sortować będziemy zbiór dziesięciu liczb całkowitych:

300 000 000, 2399, 900 000 000, 1899 999 999, 500 000 001, 1400 200 000, 1799 999 999, 123 456 678, 1999 999 999, 1210 000 000

Każdą z tych liczb wkładamy do odpowiedniego kubełka:

1. [0, 200 000 000): 2399, 123 456 678, 
2. [200 000 000, 400 000 000): 300 000 000,
3. [400 000 000, 600 000 000): 500 000 001,
4. [600 000 000, 800 000 000)
5. [800 000 000, 1000 000 000): 900 000 000
6. [1000 000 000, 1200 000 000)
7. [1200 000 000, 1400 000 000): 1210 000 000
8. [1400 000 000, 1600 000 000):  1400 200 000,
9. [1600 000 000, 1800 000 000): 1799 999 999,
10. [1800 000 000, 2000 000 000): 1899 999 999, 1999 999 999

Następnie przeglądamy każdy kubełek i jeśli jest w nim więcej niż jeden element, wykonujemy sortowanie dowolnym algorytmem. Zauważmy, że liczby są równomiernie rozłożone, co za tym idzie, każdy kubełek będzie miał co najwyżej kilka elementów. Do posortowania takiego kubełka wystarczy niewielka liczba operacji (załóżmy k operacji), zatem złożoność będzie cały czas liniowa. 

Ostatecznie przechodzimy przez kolejne kubełki i wypisujemy liczby w kolejności napotkania.

Implementacja sortowania kubełkowego

//sortowanie kubełkowe
//algorytm.edu.pl
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int liczba, n;
	
	//cout<<"Ile liczb będziesz chciał posortować? ";
	cin>>n;
	
	int p = 2000000000/n;  //zakres jednego kubełka 
	//przedziały dla kolejnych kubełkow: 
	//[0, p), [p, 2p), [2p, 3p), ..., [(n-1)p, n*p)
	
	vector  kubelki[n]; //tworzymy kubełki
	
	//wczytanie liczb i wrzucenie ich do odpowiednich kubełków
	for(int i=0;i<n;i++)
	{
		cin>>liczba; 
		//wrzucam liczbę do odpowiedniego kubełka
		kubelki[liczba/p].push_back(liczba);
	}
	//sortowanie elementów w poszczególnych kubełkach
	for(int i=0;i<n;i++)
	//sortujemy tylko, jesli kubełek ma co najmniej dwie liczby
	if(kubelki[i].size()>1) 
		sort(kubelki[i].begin(), kubelki[i].end());
	
	//wypisanie posortowanych liczb
	for(int i=0;i<n;i++)
		for(int j=0;j<kubelki[i].size();j++)
			cout<<kubelki[i][j]<<' ';
	
	return 0;
}

Uwagi!

Dla czytelności kodu, poszczególne kubełki posortowano algorytmem sort, który nie sortuje w miejscu. 

Ponieważ nie jest znana maksymalna liczba elementów w kubełku, użyto wektora, do którego możemy dodać dowolną ilość liczb.