Sortowanie kubełkowe
Stronę tą wyświetlono już: 5165 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:
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.

Tytuł:
Matematyka dyskretna dla praktyków. Algorytmy i uczenie maszynowe w Pythonie
Autor:
Ryan T. White, Archana Tikayat Ray

Tytuł:
Algorytmy kryptograficzne w Pythonie. Wprowadzenie
Autor:
Shannon W. Bray

Tytuł:
Algorytmy sztucznej inteligencji. Ilustrowany przewodnik
Autor:
Rishal Hurbans

Tytuł:
Algorytmy bez tajemnic
Autor:
Thomas H. Cormen

Tytuł:
Algorytmy dla bystrzaków
Autor:
John Paul Mueller, Luca Massaron

Tytuł:
Algorytmy Data Science. Siedmiodniowy przewodnik. Wydanie II
Autor:
David Natingga

Tytuł:
Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji
Autor:
Giuseppe Bonaccorso

Tytuł:
Struktury danych i algorytmy w języku Java. Przewodnik dla początkujących
Autor:
James Cutajar

Tytuł:
C++. Struktury danych i algorytmy
Autor:
Wisnu Anggoro

Tytuł:
Struktury danych i algorytmy w języku C#. Projektowanie efektywnych aplikacji
Autor:
Marcin Jamro