Sortowanie kubełkowe

Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 6535 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:

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.

Propozycje książek
tytuł: Algorytmy. Ilustrowany przewodnik autor: Aditya Bhargava

Tytuł:

Algorytmy. Ilustrowany przewodnik

Autor:

Aditya Bhargava

tytuł: Algorytmy. Struktury danych i złożoność obliczeniowa autor: Feliks Kurp

Tytuł:

Algorytmy. Struktury danych i złożoność obliczeniowa

Autor:

Feliks Kurp

tytuł: Algorytmy w Pythonie. Techniki programowania dla praktyków autor: Piotr Wróblewski

Tytuł:

Algorytmy w Pythonie. Techniki programowania dla praktyków

Autor:

Piotr Wróblewski

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

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 kryptograficzne w Pythonie. Wprowadzenie

Autor:

Shannon W. Bray

tytuł: Algorytmy sztucznej inteligencji. Ilustrowany przewodnik autor: Rishal Hurbans

Tytuł:

Algorytmy sztucznej inteligencji. Ilustrowany przewodnik

Autor:

Rishal Hurbans

tytuł: Algorytmy bez tajemnic  autor: Thomas H. Cormen

Tytuł:

Algorytmy bez tajemnic

Autor:

Thomas H. Cormen

tytuł: Algorytmy dla bystrzaków autor: John Paul Mueller, Luca Massaron

Tytuł:

Algorytmy dla bystrzaków

Autor:

John Paul Mueller, Luca Massaron

tytuł: Algorytmy Data Science. Siedmiodniowy przewodnik. Wydanie II autor: David Natingga

Tytuł:

Algorytmy Data Science. Siedmiodniowy przewodnik. Wydanie II

Autor:

David Natingga

tytuł: Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji autor: Giuseppe Bonaccorso

Tytuł:

Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji

Autor:

Giuseppe Bonaccorso

W związku z tym, że firma Helion nie wywiązuje się z swoich zobowiązań naliczania prowizji za każdą zakupioną książkę a kontakt z ową frmą jest nie możliwy autor strony zmuszony został do zablokowania linkowania książek. Za wszelkie niedogodności z tym związane z góry przepraszam i obiecuję włączenie linkowania gdy tylko sprawa zostanie wyjaśniona