Sortowanie kubełkowe

Stronę tą wyświetlono już: 2038 razy

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:

zakres dolny dla podziału danych przy sortowaniu kubełkowym [1]

Zapis wyrażenia w formacie TeX-a:

z_d = \frac{max - min}{k}\cdot i + min

zakres dolny dla podziału danych przy sortowaniu kubełkowym [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:

Listing 1
  1. d = Array();
  3. for(var i = 0; i < 100; i++){
  4. d.push(Math.random() * 100 + 20);
  5. }
  7. console.log(d);
  9. function getMinMax(table){
  10. var minmax = [table[0], table[0]];
  11. for(var i = 1; i < table.length; i++){
  12. minmax[0] = Math.min(table[i], minmax[0]);
  13. minmax[1] = Math.max(table[i], minmax[1]);
  14. }
  15. return minmax;
  16. }
  18. function createBuckets(k){
  19. var buckets = Array();
  20. for(var i = 0; i < k; i++){
  21. buckets.push(Array());
  22. }
  23. return buckets;
  24. }
  26. function compare(a, b){
  27. return a - b;
  28. }
  30. function bucketSort(data, k){
  31. var minmax = getMinMax(data);
  32. console.log("min: " + minmax[0] + " max: " + minmax[1]);
  33. var w = (minmax[1] - minmax[0]) / k;
  34. var buckets = createBuckets(k);
  35. for(var i = 0; i < data.length; i++){
  36. for(var kb = 0; kb < buckets.length; kb++){
  37. if(w * (kb + 1) + minmax[0] >= data[i]){
  38. buckets[kb].push(data[i]);
  39. break;
  40. }
  41. }
  42. }
  43. var sorted = Array();
  44. for(var i = 0; i < buckets.length; i++){
  45. buckets[i].sort(compare);
  46. console.log("Sorted " + i + " bucket " + buckets[i].join());
  47. sorted = sorted.concat(buckets[i]);
  48. }
  49. console.log("Zwracam posortowaną tablicę:");
  50. return sorted;
  51. }
  53. console.log(bucketSort(d, 10));

Złożoność obliczeniowa w najgorszym przypadku dla tego algorytmu wynosi n2 w najlepszym n.

Tematy powiązane

Komentarze