Sortowanie kubełkowe polega na podzieleniu danych d na mniejsze częściowo posegregowane według określonych kryteriów partie danych, które w późniejszym czasie są sortowane indywidualnie. Pewnym szczególnym wariantem tego typu sortowania jest wcześniej już omawiany algorytm sortowania przez zliczanie. Dla danych liczbowych można algorytm sortowania kubełkowego przedstawić w sposób bardziej elastyczny wymagający znajomości maksimum i minimum wartości występujących w tablicy danych d. Wtedy to bowiem można określić kryteria przynależności danego elementu do pojemnika np. dla podziału zakresu danych zbioru d na k części zakres danych dla i-tego pojemnika będzie określony następującymi granicami:
[1]
Zapis wyrażenia w formacie TeX-a:
z_d = \frac{max - min}{k}\cdot i + min
[2]
Zapis wyrażenia w formacie TeX-a:
z_g = \frac{max - min}{k}\cdot (i + 1) + min
gdzie:
zd - dolna granica przynależności;
zg - górna granica przynależności
Przykład kodu wykorzystującego powyższą zasadę do sortowania wylosowanych liczb zmiennoprzecinkowych:
d = Array();
for(var i = 0; i < 100; i++){
d.push(Math.random() * 100 + 20);
}
console.log(d);
function getMinMax(table){
var minmax = [table[0], table[0]];
for(var i = 1; i < table.length; i++){
minmax[0] = Math.min(table[i], minmax[0]);
minmax[1] = Math.max(table[i], minmax[1]);
}
return minmax;
}
function createBuckets(k){
var buckets = Array();
for(var i = 0; i < k; i++){
buckets.push(Array());
}
return buckets;
}
function compare(a, b){
return a - b;
}
function bucketSort(data, k){
var minmax = getMinMax(data);
console.log("min: " + minmax[0] + " max: " + minmax[1]);
var w = (minmax[1] - minmax[0]) / k;
var buckets = createBuckets(k);
for(var i = 0; i < data.length; i++){
for(var kb = 0; kb < buckets.length; kb++){
if(w * (kb + 1) + minmax[0] >= data[i]){
buckets[kb].push(data[i]);
break;
}
}
}
var sorted = Array();
for(var i = 0; i < buckets.length; i++){
buckets[i].sort(compare);
console.log("Sorted " + i + " bucket " + buckets[i].join());
sorted = sorted.concat(buckets[i]);
}
console.log("Zwracam posortowaną tablicę:");
return sorted;
}
console.log(bucketSort(d, 10));
Złożoność obliczeniowa w najgorszym przypadku dla tego algorytmu wynosi n2 w najlepszym n.
