Przeczytaj

Sortowanie kubełkowe – implementacja w języku Java

Algorytm sortowania kubełkowego polega na zliczeniu wystąpień danych wartości w odpowiednich kubełkach. Na podstawie liczby elementów znajdujących się w danym kubełku należy utworzyć zbiór wynikowy.

Zbiorem wejściowym i wyjściowym (wynikowym) w języku Java może być dowolny kontenerkontenerkontener. W tym e‑materiale skorzystamy z tablic.

Załóżmy, że tablica wejściowa została już wczytana i utworzona.

Specyfikacja problemu:

Dane:

tabWejsciowa – tablica wejściowa zawierająca liczby całkowite
minLiczba – liczba całkowita; najmniejszy element w podanej tablicy
maxLiczba – liczba całkowita; największy element w podanej tablicy

Wynik:

tab – posortowana niemalejąco tablica liczb całkowitych

Już wiesz

Długość tablicy odczytujemy za pomocą atrybutu length.

static int[] przykladTab = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
System.out.println(przykladTab.length); // Wypisze 10 na wyjście standardowe

Algorytm sortowania kubełkowego stosujemy najczęściej dla typów całkowitoliczbowychtyp całkowitoliczbowytypów całkowitoliczbowych. Jednak możliwe jest wykorzystanie go (po zmianach) do sortowania liczb rzeczywistych.

Długość tablicy wynikowej nie powinna być krótsza od długości tablicy wejściowej. Jeśli w tablicy wejściowej są jedynie liczby dodatnie, można odnaleźć największą liczbę, a następnie utworzyć tablicę o długości tej liczby + 1. Nie jest to jednak optymalne rozwiązanie.

Przykład 1

Jeśli w tablicy wejściowej znajdowałyby się liczby: {1000, 999, 1002, 1002, 999}, to tworząc tablicę wynikową jedynie na podstawie największej z tych liczb, otrzymalibyśmy tablicę zawierającą 1003 elementy, przy czym potrzebujemy jedynie komórek na unikalne kubełki odpowiadające za wartości: 999, 1000, 1002. Oznacza to, że mielibyśmy nadmiarowo zaalokowane 1000 komórek pamięci. Jednak liczbę nadmiarowych komórek da się w tym algorytmie ograniczyć.

Z przedstawionego przykładu wynika, że można utworzyć mniejszą tablicę wynikową. W tym celu odnajdujemy najmniejszą liczbę w tablicy wejściowej i odejmujemy ją od największej liczby.

Przykład 2

Użyjmy tablicy z poprzedniego przykładu: {1000, 999, 1002, 1002, 999}. Tym razem odnajdujemy największą i najmniejszą liczbę.
minLiczba = 1002
minLiczba = 999
1002 - 999 = 3

W tablicy wejściowej znajdują się trzy unikalne elementy. Należy jednak pamiętać, że tablica wynikowa, którą chcemy utworzyć, powinna mieć co najmniej cztery elementy. Algorytm nie uwzględnia faktu, że w zbiorze nie ma liczby 1001 i przypisuje tej liczbie własny kubełek.

Ważne!

W tym przykładzie każda z liczb z przedziału <999, 1002> zajmuje jeden kubełek, numerowany od 0 do 3 włącznie.

Liczba 3 jest więc ostatnim indeksem, w którego komórce będziemy mogli coś zapisać, żeby nie wyjść poza przedział tablicy.

Deklaracja tablicy wygląda następująco:

int[] przyklad = new int[maxLiczba - minLiczba + 1];

W optymalnym algorytmie sortowania kubełkowego znajdujemy najmniejszą oraz największą liczbę, aby utworzyć tablicę wynikową o optymalnej długości.

Nie wspomnieliśmy jeszcze o sytuacji, w której sortuje się liczby ujemne. Przeanalizujmy przykład, w którym obliczymy długość tablicy w takim przypadku.

Przykład 3

Dla tablicy wejściowej {-5, -4, -3, -3, -4} istnieje pozorny problem, polegający na tym, że największą liczbą z tego zbioru jest liczba -3, a w języku Java nie można utworzyć tablicy w której indeks jest liczbą ujemną.

Długość tablicy wynikowej obliczymy, korzystając ze wzoru maxLiczba - minLiczba. Odnajdujemy najmniejszą liczbę, czyli -5, a następnie odejmujemy ją od największej liczby: -3 - (-5) = 2.
Otrzymujemy informację, że największym dopuszczalnym indeksem tablicy będzie indeks o numerze 2.
Postępujemy więc analogicznie do przykładu 2. Zwiększamy otrzymaną liczbę o 1, a następnie deklarujemy tablicę w następujący sposób:

int[] przyklad = new int[maxLiczba - minLiczba + 1];

Rzeczywiście, w sprawdzanej przez nas tablicy były 3 unikalne elementy. Wyznaczanie długości tablicy zliczającej w algorytmie nie ulega więc modyfikacji względem poprzedniego przykładu.

Algorytm nie zmienia się również w przypadku zbioru składającego się z liczb ujemnych i dodatnich. Przeanalizujmy ostatni już przykład wyznaczania rozmiaru tablicy pomocniczej.

Przykład 4

Dla tablicy {-5, 5} mamy następującą sytuację:
maxLiczba = 5
minLiczba = -5
5 - (-5) = 10
Ponownie do wyniku działania dodajemy 1, uzyskując na koniec tablicę kubełków składającą się z 11 elementów.

Możemy zauważyć tu marnotrawstwo pamięci. W omawianym przykładzie może wydawać się ono nieznaczące, jednak dla zbioru złożonego z liczb: ${- 2^{63^{}}, 2^{63}}$ mogłoby stanowić duże obciążenie dla programu.

Wynika to z faktu, że optymalny algorytm sortowania kubełkowego ma złożoność pamięciową $O (m a x - m i n + 1)$ .

Ważne!

Dla dużych rozpiętości danych algorytm sortowania kubełkowego jest nieoptymalny pamięciowo.

Zgodnie z założeniem przyjętym na początku tej sekcji – tablica wejściowa została już wprowadzona do programu. Rozwiązanie zaimplementujemy w ramach klasy SortowanieKubelkowe, która zawiera metodę main.

Lista kroków algorytmu:

Znajdź największą (maxLiczba) i najmniejszą (minLiczba) wartość z danego zbioru.
Stwórz tablicę pomocniczą (kubełków) o długości maxLiczba - minLiczba + 1.
Zlicz wystąpienia każdej z wartości, a następnie przypisz obliczone liczby wartości do odpowiednich kubełków.
Począwszy od kubełka o najmniejszej/największej wartości wykonuj kroki 5‑6.
Jeśli kubełek nie jest pusty, to do tablicy wynikowej wpisz wartość (indeksKubełka + minLiczba) do pierwszego niewypełnionego jeszcze indeksu.
Jeśli kubełek jest pusty, przejdź do kolejnego kubełka.
Jeśli nie ma już więcej kubełków, przejdź do kroku 7.
Zdekrementuj liczbę elementów w aktualnym kubełku i wróć do kroku 5.
Zwróć tablicę wynikową tab.

Przejdźmy do implementacji algorytmu. Najpierw tworzymy metodę pomocniczą do odnajdywania największej i najmniejszej liczby w danej tablicy. Zostanie ona zaimplementowana w ramach wspomnianej wcześniej klasy.

public static int[] znajdzMinMax(int[] tab){
	int minLiczba = tab[0];
	int maxLiczba = tab[0];
	for (int i = 1; i < tab.length; i++) {
		if (minLiczba > tab[i]) minLiczba = tab[i];
		if (maxLiczba < tab[i]) maxLiczba = tab[i];
	}
	return new int[]{minLiczba, maxLiczba};
}

W przytoczonej implementacji skorzystaliśmy ze stałych Integer.MAX_VALUE i Integer.MIN_VALUE. Stałe te pochodzą z klasy Integer, dostępnej w ramach Java.lang package. Aby ich użyć, nie trzeba dołączać żadnych pakietów ani klas.

public class SortowanieKubelkowe {
	static int[] tabWejsciowa = {999, 888, 222, 111, -444};
}

Metoda sortująca przedstawia się następująco:

Linia 1. public static int otwórz nawias kwadratowy zamknij nawias kwadratowy posortuj otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy tab zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. int otwórz nawias kwadratowy zamknij nawias kwadratowy kubelki średnik. Linia 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy MinMax znak równości znajdzMinMax otwórz nawias okrągły tab zamknij nawias okrągły średnik prawy ukośnik prawy ukośnik odnalezienie minimalnej i maksymalnej liczby. Linia 4. int min znak równości MinMax otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik prawy ukośnik prawy ukośnik przypisanie minimalnej liczby dla czytelnosci. Linia 5. int max znak równości MinMax otwórz nawias kwadratowy 1 zamknij nawias kwadratowy średnik prawy ukośnik prawy ukośnik przypisanie maksymalnej liczby dla czytelnosci. Linia 6. kubelki znak równości new int otwórz nawias kwadratowy max minus min plus 1 zamknij nawias kwadratowy średnik prawy ukośnik prawy ukośnik utworzenie tablicy o dlugosci max minus min plus 1. Linia 8. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny tab kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. kubelki otwórz nawias kwadratowy tab otwórz nawias kwadratowy i zamknij nawias kwadratowy minus min zamknij nawias kwadratowy plus plus średnik prawy ukośnik prawy ukośnik zliczenie liczb do odpowiednich kubełków. Linia 10. zamknij nawias klamrowy. Linia 12. int j znak równości 0 średnik. Linia 13. int i znak równości 0 średnik. Linia 15. while otwórz nawias okrągły i otwórz nawias ostrokątny tab kropka length zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. if otwórz nawias okrągły kubelki otwórz nawias kwadratowy j zamknij nawias kwadratowy wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy prawy ukośnik prawy ukośnik jeśli kubełek nie pusty. Linia 17. tab otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości min plus j średnik prawy ukośnik prawy ukośnik wypełnij element spod indeksu i wartością min plus j. Linia 18. i plus plus średnik. Linia 19. kubelki otwórz nawias kwadratowy j zamknij nawias kwadratowy minus minus średnik prawy ukośnik prawy ukośnik usuń element z kubełka. Linia 20. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 21. j plus plus średnik prawy ukośnik prawy ukośnik przejdź do nastepnego kubełka. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy. Linia 25. return tab średnik. Linia 26. zamknij nawias klamrowy.

public static int[] posortuj(int [] tab) {
	int[] kubelki; 
    int[] MinMax = znajdzMinMax(tab); //odnalezienie minimalnej i maksymalnej liczby
	int min = MinMax[0]; // przypisanie minimalnej liczby dla czytelnosci
	int max = MinMax[1]; // przypisanie maksymalnej liczby dla czytelnosci
	kubelki = new int[max - min + 1]; // utworzenie tablicy o dlugosci max - min + 1
    
	for (int i = 0; i < tab.length; i++) {
		kubelki[tab[i] - min]++; // zliczenie liczb do odpowiednich kubełków
	}
    
	int j = 0;
	int i = 0;
    
	while (i < tab.length) {
		if (kubelki[j] != 0) { // jeśli kubełek nie pusty
			tab[i] = min + j; // wypełnij element spod indeksu i wartością min + j
			i++;
			kubelki[j]--; // usuń element z kubełka
		} else {
			j++; // przejdź do nastepnego kubełka
		}
	}
    
	return tab;
}

Cały kod przyjmuje postać:

Linia 1. import java kropka util kropka Arrays średnik. Linia 3. public class SortowanieKubelkowe otwórz nawias klamrowy. Linia 4. static int otwórz nawias kwadratowy zamknij nawias kwadratowy tabWejsciowa znak równości otwórz nawias klamrowy 999 przecinek 888 przecinek 222 przecinek minus 444 przecinek 111 zamknij nawias klamrowy średnik. Linia 6. public static int otwórz nawias kwadratowy zamknij nawias kwadratowy znajdzMinMax otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy tab zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. int minLiczba znak równości tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 8. int maxLiczba znak równości tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 9. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny tab kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. if otwórz nawias okrągły minLiczba zamknij nawias ostrokątny tab otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły minLiczba znak równości tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 11. if otwórz nawias okrągły maxLiczba otwórz nawias ostrokątny tab otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły maxLiczba znak równości tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 12. zamknij nawias klamrowy. Linia 13. return new int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias klamrowy minLiczba przecinek maxLiczba zamknij nawias klamrowy średnik. Linia 14. zamknij nawias klamrowy. Linia 16. public static int otwórz nawias kwadratowy zamknij nawias kwadratowy posortuj otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy tab zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. int otwórz nawias kwadratowy zamknij nawias kwadratowy kubelki średnik. Linia 18. int otwórz nawias kwadratowy zamknij nawias kwadratowy MinMax znak równości znajdzMinMax otwórz nawias okrągły tab zamknij nawias okrągły średnik. Linia 19. int min znak równości MinMax otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 20. int max znak równości MinMax otwórz nawias kwadratowy 1 zamknij nawias kwadratowy średnik. Linia 21. kubelki znak równości new int otwórz nawias kwadratowy max minus min plus 1 zamknij nawias kwadratowy średnik. Linia 23. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny tab kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. kubelki otwórz nawias kwadratowy tab otwórz nawias kwadratowy i zamknij nawias kwadratowy minus min zamknij nawias kwadratowy plus plus średnik. Linia 25. zamknij nawias klamrowy. Linia 27. int j znak równości 0 średnik. Linia 28. int i znak równości 0 średnik. Linia 30. while otwórz nawias okrągły i otwórz nawias ostrokątny tab kropka length zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. if otwórz nawias okrągły kubelki otwórz nawias kwadratowy j zamknij nawias kwadratowy wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 32. tab otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości min plus j średnik. Linia 33. i plus plus średnik. Linia 34. kubelki otwórz nawias kwadratowy j zamknij nawias kwadratowy minus minus średnik. Linia 35. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 36. j plus plus średnik. Linia 37. zamknij nawias klamrowy. Linia 38. zamknij nawias klamrowy. Linia 40. return tab średnik. Linia 41. zamknij nawias klamrowy. Linia 43. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 44. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabWyjsc znak równości tabWejsciowa kropka clone otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 45. System kropka out kropka println otwórz nawias okrągły Arrays kropka toString otwórz nawias okrągły tabWejsciowa zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 46. System kropka out kropka println otwórz nawias okrągły Arrays kropka toString otwórz nawias okrągły posortuj otwórz nawias okrągły tabWyjsc zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 47. zamknij nawias klamrowy. Linia 48. zamknij nawias klamrowy.

import java.util.Arrays;

public class SortowanieKubelkowe {
    static int[] tabWejsciowa = {999, 888, 222, -444, 111};

    public static int[] znajdzMinMax(int[] tab){
        int minLiczba = tab[0];
        int maxLiczba = tab[0];
        for (int i = 1; i < tab.length; i++) {
            if (minLiczba > tab[i]) minLiczba = tab[i];
            if (maxLiczba < tab[i]) maxLiczba = tab[i];
        }
        return new int[]{minLiczba, maxLiczba};
    }

    public static int[] posortuj(int [] tab) {
        int[] kubelki;
        int[] MinMax = znajdzMinMax(tab);
        int min = MinMax[0];
        int max = MinMax[1];
        kubelki = new int[max - min + 1];

        for (int i = 0; i < tab.length; i++) {
            kubelki[tab[i] - min]++;
        }

        int j = 0;
        int i = 0;

        while (i < tab.length) {
            if (kubelki[j] != 0) {
                tab[i] = min + j;
                i++;
                kubelki[j]--;
            } else {
                j++;
            }
        }

        return tab;
    }

    public static void main(String[] args) {
        int[] tabWyjsc = tabWejsciowa.clone();
        System.out.println(Arrays.toString(tabWejsciowa));
        System.out.println(Arrays.toString(posortuj(tabWyjsc)));
    }
}

Metoda Arrays.toString() pozwala wypisać tablicę w postaci łańcucha znaków.
Program po wykonaniu wyświetli następujące tablice:
[999,888,222,-444,111]
[-444,111,222,888,999]

Ważne!

Aby użyć klasy Arrays i metod w niej dostępnych, należy najpierw zaimportować tę klasę poprzez:

import java.util.Arrays;

Sortowanie kubełkowe dla liczb rzeczywistych

Liczby rzeczywiste również można sortować za pomocą algorytmu sortowania kubełkowego, jednak różni się on od wcześniej przedstawionego.

W omawianych dotychczas przykładach sortowania liczb całkowitych algorytm przyjmował postać uproszczonego sortowania przez zliczanie.

W przypadku algorytmu dla liczb rzeczywistych tworzone są kubełki dla pewnych ściśle zdefiniowanych zakresów. Przykładowo, w każdym kubełku mogą znajdować się liczby z przedziału $< x, x + 1)$ dla liczb nieujemnych. Oznacza to, że jeżeli pod $x$ podstawimy liczbę $3$ , to w danym kubełku znajdą się liczby z przedziału $< 3, 4)$ . Dla liczb ujemnych w każdym kubełku znajdują się liczby z przedziału $(x - 1, x >$ . Gdy pod $x$ podstawimy $- 5$ , w kubełku znajdą się liczby z przedziału $(- 6, - 5 >$ .

Wiedząc, do jakiego przedziału należą sortowane liczby, możemy łatwo określić przedziały poszczególnych kubełków. Dzielimy długość przedziału przez liczbę kubełków – w ten sposób powstaje długość jednego przedziału.

Zastosujemy przedział wielkości 1. Oznacza to, że w danym kubełku dla liczb nieujemnych znajdą się liczby z przedziału $< x, x + 1)$ , natomiast dla liczb ujemnych przedział będzie prezentował się następująco: $(x - 1, x >$ .

Przykład 5

Jeżeli pod $x$ podstawimy liczbę $5$ , to przedział kubełka liczby znajdującej się w tym zakresie wyniesie $< 5, 6)$ .

Jeżeli pod $x$ podstawimy liczbę $- 5$ , to przedział kubełka będzie miał zakres $(- 6, - 5 >$ .

Zapoznaj się z kodem. Wszystkie elementy tablicy umieszczane są w kubełkach. Kubełki mają wcześniej określone przedziały. Program na końcu wypisuje zawartości kubełków.

import java.util.ArrayList;

public class Main {
    static int[] znajdzMinMax(double[] tab){
        int max = (int)tab[0];
        int min = (int)tab[0];
        for(int i = 1; i < tab.length; i++){
            if (max < (int)tab[i] ) max = (int)tab[i];
            if (min > (int)tab[i] ) min = (int)tab[i];
        }
        return new int[] {min, max};
    }


    public static void main(String[] args) {
        double tabWejsciowa[] = { 3.5, 2, 3, 4, -4, 2, 3, 2, 0, -5.5 };
        int [] MinMax = znajdzMinMax(tabWejsciowa);
        int max = MinMax[1];
        int min = MinMax[0];
        int dlugoscTab = max - min + 1;
        ArrayList<ArrayList<Double>> tablicaTablic = new ArrayList<ArrayList<Double>>();
        for(int i = 0; i<dlugoscTab; i++){
            tablicaTablic.add(new ArrayList<Double>());
        }
        for (int i = 0; i < tabWejsciowa.length; i++){
            double wartosc = tabWejsciowa[i];
            int ktoryKubelek = (int)wartosc - min;
            tablicaTablic.get(ktoryKubelek).add(wartosc);
        }
        for (int i = 0; i < dlugoscTab; i++){
            if (!(tablicaTablic.get(i).size() == 0)){
                System.out.print("Kubelek numer " + i + " : ");
                for (int j = 0; j < tablicaTablic.get(i).size(); j++){
                    System.out.print(tablicaTablic.get(i).get(j) + "; ");
                }
                System.out.println();
            }
        }
    }
}

Zwróć uwagę na 21. linię kodu.

Tworzymy pustą tablicę zawierającą wiele tablic, które z kolei zawierają obiekty klasy Double. Nie używamy w tym miejscu słowa kluczowego double, ponieważ interfejsy nie działają z typami prymitywnymi.

for(int i = 0; i<dlugoscTab; i++){
    tablicaTablic.add(new ArrayList<Double>());
}

W przedstawionym fragmencie kodu implementujemy wypełnienie tablicy głównej tablicami przechowującymi obiekty klasy Double.

for (int i = 0; i < tabWejsciowa.length; i++){
        double wartosc = tabWejsciowa[i];
        int ktoryKubelek = (int)wartosc - min;
        tablicaTablic.get(ktoryKubelek).add(wartosc);
}

Następnie wszystkie komórki tablicy wejściowej wczytywane są do odpowiednich kubełków w nieuporządkowany sposób.

for (int i = 0; i < dlugoscTab; i++){
        if (!(tablicaTablic.get(i).size() == 0)){
            System.out.print("Kubelek numer " + i + " : ");
            for (int j = 0; j < tablicaTablic.get(i).size(); j++){
            	System.out.print(tablicaTablic.get(i).get(j) + "; ");
            }
            System.out.println();
        }
}

Ostatni fragment odpowiada za wypisywanie zawartości tablicy tablic.

Przykładowy wynik wykonania kodu:

Kubelek numer 0 : -5.5; 
Kubelek numer 1 : -4.0; 
Kubelek numer 5 : 0.0; 
Kubelek numer 7 : 2.0; 2.0; 2.0; 
Kubelek numer 8 : 3.5; 3.0; 3.0; 
Kubelek numer 9 : 4.0;

W kolejnym kroku należy posortować elementy poszczególnych niepustych kubełków. Elementy wypisujemy w kolejności od najmniejszego do największego. Możemy w tym celu użyć dowolnego algorytmu sortującego. W omawianym przykładzie posłużymy się algorytmem sortowania bąbelkowegoPxgkD2R5Yalgorytmem sortowania bąbelkowego.

Wyjaśnijmy najpierw, w jakim celu dzielimy elementy na kubełki, skoro i tak skorzystamy z innego algorytmu sortowania.

Przeanalizujmy sytuację, w której mamy 100 kubełków – w każdym z nich znajduje się 10 elementów, co oznacza, że mamy w sumie 1000 elementów do posortowania.

Gdybyśmy do posortowania tych elementów zastosowali jedynie sortowanie bąbelkowe, algorytm miałby złożoność obliczeniową rzędu $n^2$ , czyli $1000^2$ , czyli $1000000$ .

W rozwiązaniu polegającym na osobnym sortowaniu każdego z kubełków złożoność obliczeniowa algorytmu sortowania bąbelkowego wyniesie $100 * 10^2$ , czyli $10000$

Porównajmy ze sobą dwie liczby:

(1)

1000^{2} > 100 \cdot 10^{2}

Możemy zauważyć, że zastosowanie sortowania bąbelkowego w tym przypadku wymaga większej liczby operacji.

Należy jednak pamiętać, że nie zawsze liczba elementów w każdym z kubełków będzie taka sama.

Ciekawostka

Dodatkowo (z racji tego, że kubełki znajdują się w oddzielnych obszarach pamięci) można wykorzystać wielowątkowośćwielowątkowośćwielowątkowość do sortowania poszczególnych kubełków, przyspieszając tym samym wykonanie całego programu, poprzez np. tworzenie wątku na każdy niepusty kubełek.

Więcej informacji na temat wielowątkowości znajdziesz w e‑materiałach Programowanie obiektowe – projekt, etap IVPz5V06riTProgramowanie obiektowe – projekt, etap IV oraz Programowanie obiektowe – projekt, etap VIP12JtasVMProgramowanie obiektowe – projekt, etap VI.

Do napisanego wcześniej programu dodajemy metodę sortującą z wykorzystaniem sortowania bąbelkowego.

Dla zainteresowanych

Spróbuj samodzielnie zaimplementować inny algorytm sortujący poszczególne kubełki.

static void sortowanieBabelkowe(ArrayList<Double> a) {
	boolean sortuj = true;
    while(sortuj){
        sortuj = false;
        for (int i = 0; i < a.size()-1; i++){
            if (a.get(i) > a.get(i+1)) {
                a.set(i, a.get(i) + a.get(i+1));
                a.set(i+1, a.get(i) - a.get(i+1));
                a.set(i, a.get(i)-a.get(i+1));
                sortuj = true;
            }
         }
    }
}

Po dodaniu sortowania poszczególnych kubełków cały kod wygląda następująco:

Linia 1. import java kropka util kropka ArrayList średnik. Linia 3. public class Main otwórz nawias klamrowy. Linia 4. static int otwórz nawias kwadratowy zamknij nawias kwadratowy znajdzMinMax otwórz nawias okrągły double otwórz nawias kwadratowy zamknij nawias kwadratowy tab zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. int max znak równości otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 6. int min znak równości otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 7. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny tab kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły max otwórz nawias ostrokątny otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły max znak równości otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 9. if otwórz nawias okrągły min zamknij nawias ostrokątny otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły min znak równości otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 10. zamknij nawias klamrowy. Linia 11. return new int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias klamrowy min przecinek max zamknij nawias klamrowy średnik. Linia 12. zamknij nawias klamrowy. Linia 14. static void sortowanieBabelkowe otwórz nawias okrągły ArrayList otwórz nawias ostrokątny Double zamknij nawias ostrokątny a zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. boolean sortuj znak równości true średnik. Linia 16. while otwórz nawias okrągły sortuj zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. sortuj znak równości false średnik. Linia 18. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny a kropka size otwórz nawias okrągły zamknij nawias okrągły minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. if otwórz nawias okrągły a kropka get otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias ostrokątny a kropka get otwórz nawias okrągły i plus 1 zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. a kropka set otwórz nawias okrągły i przecinek a kropka get otwórz nawias okrągły i zamknij nawias okrągły plus a kropka get otwórz nawias okrągły i plus 1 zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 21. a kropka set otwórz nawias okrągły i plus 1 przecinek a kropka get otwórz nawias okrągły i zamknij nawias okrągły minus a kropka get otwórz nawias okrągły i plus 1 zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 22. a kropka set otwórz nawias okrągły i przecinek a kropka get otwórz nawias okrągły i zamknij nawias okrągły minus a kropka get otwórz nawias okrągły i plus 1 zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 23. sortuj znak równości true średnik. Linia 24. zamknij nawias klamrowy. Linia 25. zamknij nawias klamrowy. Linia 26. zamknij nawias klamrowy. Linia 27. zamknij nawias klamrowy. Linia 30. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. double tabWejsciowa otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 3 kropka 5 przecinek 2 kropka 5 przecinek 3 przecinek 4 przecinek minus 4 przecinek 2 kropka 2 przecinek 3 przecinek 2 kropka 6 przecinek 0 przecinek minus 5 kropka 5 zamknij nawias klamrowy średnik. Linia 32. int otwórz nawias kwadratowy zamknij nawias kwadratowy MinMax znak równości znajdzMinMax otwórz nawias okrągły tabWejsciowa zamknij nawias okrągły średnik. Linia 33. int max znak równości MinMax otwórz nawias kwadratowy 1 zamknij nawias kwadratowy średnik. Linia 34. int min znak równości MinMax otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 35. int dlugoscTab znak równości max minus min plus 1 średnik. Linia 36. ArrayList otwórz nawias ostrokątny ArrayList otwórz nawias ostrokątny Double zamknij nawias ostrokątny zamknij nawias ostrokątny tablicaTablic znak równości new ArrayList otwórz nawias ostrokątny ArrayList otwórz nawias ostrokątny Double zamknij nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 37. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dlugoscTab średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 38. tablicaTablic kropka add otwórz nawias okrągły new ArrayList otwórz nawias ostrokątny Double zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 39. zamknij nawias klamrowy. Linia 40. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny tabWejsciowa kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 41. double wartosc znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 42. int ktoryKubelek znak równości otwórz nawias okrągły int zamknij nawias okrągły wartosc minus min średnik. Linia 44. tablicaTablic kropka get otwórz nawias okrągły ktoryKubelek zamknij nawias okrągły kropka add otwórz nawias okrągły wartosc zamknij nawias okrągły średnik. Linia 45. zamknij nawias klamrowy. Linia 46. prawy ukośnik prawy ukośnik sortowanie wszystkich kubełków po kolei kropka. Linia 47. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dlugoscTab średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 48. sortowanieBabelkowe otwórz nawias okrągły tablicaTablic kropka get otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 49. zamknij nawias klamrowy. Linia 50. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dlugoscTab średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 51. if otwórz nawias okrągły wykrzyknik otwórz nawias okrągły tablicaTablic kropka get otwórz nawias okrągły i zamknij nawias okrągły kropka size otwórz nawias okrągły zamknij nawias okrągły znak równości znak równości 0 zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 52. System kropka out kropka print otwórz nawias okrągły cudzysłów Kubelek numer cudzysłów plus i plus cudzysłów dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 53. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny tablicaTablic kropka get otwórz nawias okrągły i zamknij nawias okrągły kropka size otwórz nawias okrągły zamknij nawias okrągły średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 54. System kropka out kropka print otwórz nawias okrągły tablicaTablic kropka get otwórz nawias okrągły i zamknij nawias okrągły kropka get otwórz nawias okrągły j zamknij nawias okrągły plus cudzysłów średnik cudzysłów zamknij nawias okrągły średnik. Linia 55. zamknij nawias klamrowy. Linia 56. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 57. zamknij nawias klamrowy. Linia 58. zamknij nawias klamrowy. Linia 59. zamknij nawias klamrowy. Linia 60. zamknij nawias klamrowy.

import java.util.ArrayList;

public class Main {
    static int[] znajdzMinMax(double[] tab){
        int max = (int)tab[0];
        int min = (int)tab[0];
        for(int i = 1; i < tab.length; i++){
            if (max < (int)tab[i] ) max = (int)tab[i];
            if (min > (int)tab[i] ) min = (int)tab[i];
        }
        return new int[] {min, max};
    }

    static void sortowanieBabelkowe(ArrayList<Double> a) {
        boolean sortuj = true;
        while(sortuj) {
            sortuj = false;
            for (int i = 0; i < a.size()-1; i++) {
                if (a.get(i) >a.get(i+1)) {
                    a.set(i, a.get(i) + a.get(i+1));
                    a.set(i+1, a.get(i) - a.get(i+1));
                    a.set(i, a.get(i)-a.get(i+1));
                    sortuj = true;
                }
            }
        }
    }


    public static void main(String[] args) {
        double tabWejsciowa[] = { 3.5, 2.5, 3, 4, -4, 2.2, 3, 2.6, 0, -5.5 };
        int [] MinMax = znajdzMinMax(tabWejsciowa);
        int max = MinMax[1];
        int min = MinMax[0];
        int dlugoscTab = max - min + 1;
        ArrayList<ArrayList<Double>> tablicaTablic = new ArrayList<ArrayList<Double>>();
        for(int i = 0; i<dlugoscTab; i++){
            tablicaTablic.add(new ArrayList<Double>());
        }
        for (int i = 0; i < tabWejsciowa.length; i++) {
            double wartosc = tabWejsciowa[i];
            int ktoryKubelek = (int)wartosc - min;

            tablicaTablic.get(ktoryKubelek).add(wartosc);
        }
        //sortowanie wszystkich kubełków po kolei.
        for(int i = 0; i < dlugoscTab; i++){
            sortowanieBabelkowe(tablicaTablic.get(i));
        }
        for (int i = 0; i < dlugoscTab; i++) {
            if (!(tablicaTablic.get(i).size() == 0)) {
                System.out.print("Kubelek numer " + i + " : ");
                for (int j = 0; j < tablicaTablic.get(i).size(); j++) {
                    System.out.print(tablicaTablic.get(i).get(j) + "; ");
                }
                System.out.println();
            }
        }
    }
}

W kolejnym kroku należy zaimplementować wpisywanie elementów z kubełków do tablicy wynikowej, co można uzyskać za pomocą następującego kodu:

int g = 0;
double[] tabWynikowa = new double[tabWejsciowa.length];
for (int i = 0; i < dlugoscTab; i++) {
	if (!(tablicaTablic.get(i).size() == 0)) {
		for (int j = 0; j < tablicaTablic.get(i).size(); j++) {
			tabWynikowa[g++] = tablicaTablic.get(i).get(j);
		}
	}
}
for(int i = 0; i<tabWynikowa.length; i++){
	System.out.println(tabWynikowa[i]);
}

W przedstawionym fragmencie zaimplementowane zostało również wypisywanie zawartości tej tablicy.

Kod z tworzeniem tablicy wyjściowej wygląda następująco:

Linia 1. import java kropka util kropka ArrayList średnik. Linia 3. public class Main otwórz nawias klamrowy. Linia 4. static int otwórz nawias kwadratowy zamknij nawias kwadratowy znajdzMinMax otwórz nawias okrągły double otwórz nawias kwadratowy zamknij nawias kwadratowy tab zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. int max znak równości otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 6. int min znak równości otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 7. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny tab kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły max otwórz nawias ostrokątny otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły max znak równości otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 9. if otwórz nawias okrągły min zamknij nawias ostrokątny otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły min znak równości otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 10. zamknij nawias klamrowy. Linia 11. return new int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias klamrowy min przecinek max zamknij nawias klamrowy średnik. Linia 12. zamknij nawias klamrowy. Linia 14. static void sortowanieBabelkowe otwórz nawias okrągły ArrayList otwórz nawias ostrokątny Double zamknij nawias ostrokątny a zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. boolean sortuj znak równości true średnik. Linia 16. while otwórz nawias okrągły sortuj zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. sortuj znak równości false średnik. Linia 18. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny a kropka size otwórz nawias okrągły zamknij nawias okrągły minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. if otwórz nawias okrągły a kropka get otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias ostrokątny a kropka get otwórz nawias okrągły i plus 1 zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. a kropka set otwórz nawias okrągły i przecinek a kropka get otwórz nawias okrągły i zamknij nawias okrągły plus a kropka get otwórz nawias okrągły i plus 1 zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 21. a kropka set otwórz nawias okrągły i plus 1 przecinek a kropka get otwórz nawias okrągły i zamknij nawias okrągły minus a kropka get otwórz nawias okrągły i plus 1 zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 22. a kropka set otwórz nawias okrągły i przecinek a kropka get otwórz nawias okrągły i zamknij nawias okrągły minus a kropka get otwórz nawias okrągły i plus 1 zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 23. sortuj znak równości true średnik. Linia 24. zamknij nawias klamrowy. Linia 25. zamknij nawias klamrowy. Linia 26. zamknij nawias klamrowy. Linia 27. zamknij nawias klamrowy. Linia 30. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. double tabWejsciowa otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 3 kropka 5 przecinek 2 kropka 5 przecinek 3 przecinek 4 przecinek minus 4 przecinek 2 kropka 2 przecinek 3 przecinek 2 kropka 6 przecinek 0 przecinek minus 5 kropka 5 zamknij nawias klamrowy średnik. Linia 32. int otwórz nawias kwadratowy zamknij nawias kwadratowy MinMax znak równości znajdzMinMax otwórz nawias okrągły tabWejsciowa zamknij nawias okrągły średnik. Linia 33. int max znak równości MinMax otwórz nawias kwadratowy 1 zamknij nawias kwadratowy średnik. Linia 34. int min znak równości MinMax otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 35. int dlugoscTab znak równości max minus min plus 1 średnik. Linia 36. ArrayList otwórz nawias ostrokątny ArrayList otwórz nawias ostrokątny Double zamknij nawias ostrokątny zamknij nawias ostrokątny tablicaTablic znak równości new ArrayList otwórz nawias ostrokątny ArrayList otwórz nawias ostrokątny Double zamknij nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 37. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dlugoscTab średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 38. tablicaTablic kropka add otwórz nawias okrągły new ArrayList otwórz nawias ostrokątny Double zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 39. zamknij nawias klamrowy. Linia 40. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny tabWejsciowa kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 41. double wartosc znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 42. int ktoryKubelek znak równości otwórz nawias okrągły int zamknij nawias okrągły wartosc minus min średnik. Linia 44. tablicaTablic kropka get otwórz nawias okrągły ktoryKubelek zamknij nawias okrągły kropka add otwórz nawias okrągły wartosc zamknij nawias okrągły średnik. Linia 45. zamknij nawias klamrowy. Linia 46. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dlugoscTab średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 47. sortowanieBabelkowe otwórz nawias okrągły tablicaTablic kropka get otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 48. zamknij nawias klamrowy. Linia 49. int g znak równości 0 średnik. Linia 50. double otwórz nawias kwadratowy zamknij nawias kwadratowy tabWynikowa znak równości new double otwórz nawias kwadratowy tabWejsciowa kropka length zamknij nawias kwadratowy średnik. Linia 51. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dlugoscTab średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 52. if otwórz nawias okrągły wykrzyknik otwórz nawias okrągły tablicaTablic kropka get otwórz nawias okrągły i zamknij nawias okrągły kropka size otwórz nawias okrągły zamknij nawias okrągły znak równości znak równości 0 zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 53. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny tablicaTablic kropka get otwórz nawias okrągły i zamknij nawias okrągły kropka size otwórz nawias okrągły zamknij nawias okrągły średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 54. tabWynikowa otwórz nawias kwadratowy g plus plus zamknij nawias kwadratowy znak równości tablicaTablic kropka get otwórz nawias okrągły i zamknij nawias okrągły kropka get otwórz nawias okrągły j zamknij nawias okrągły średnik. Linia 55. zamknij nawias klamrowy. Linia 56. zamknij nawias klamrowy. Linia 57. zamknij nawias klamrowy. Linia 58. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny tabWynikowa kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 59. System kropka out kropka println otwórz nawias okrągły tabWynikowa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 60. zamknij nawias klamrowy. Linia 62. zamknij nawias klamrowy. Linia 63. zamknij nawias klamrowy.

import java.util.ArrayList;

public class Main {
    static int[] znajdzMinMax(double[] tab){
        int max = (int)tab[0];
        int min = (int)tab[0];
        for(int i = 0; i< tab.length; i++){
            if (max < (int)tab[i] ) max = (int)tab[i];
            if (min > (int)tab[i] ) min = (int)tab[i];
        }
        return new int[] {min, max};
    }

    static void sortowanieBabelkowe(ArrayList<Double> a) {
        boolean sortuj = true;
        while(sortuj) {
            sortuj = false;
            for (int i = 0; i < a.size()-1; i++) {
                if (a.get(i) >a.get(i+1)) {
                    a.set(i, a.get(i) + a.get(i+1));
                    a.set(i+1, a.get(i) - a.get(i+1));
                    a.set(i, a.get(i)-a.get(i+1));
                    sortuj = true;
                }
            }
        }
    }


    public static void main(String[] args) {
        double tabWejsciowa[] = { 3.5, 2.5, 3, 4, -4, 2.2, 3, 2.6, 0, -5.5 };
        int [] MinMax = znajdzMinMax(tabWejsciowa);
        int max = MinMax[1];
        int min = MinMax[0];
        int dlugoscTab = max - min + 1;
        ArrayList<ArrayList<Double>> tablicaTablic = new ArrayList<ArrayList<Double>>();
        for(int i = 0; i<dlugoscTab; i++){
            tablicaTablic.add(new ArrayList<Double>());
        }
        for (int i = 0; i < tabWejsciowa.length; i++) {
            double wartosc = tabWejsciowa[i];
            int ktoryKubelek = (int)wartosc - min;

            tablicaTablic.get(ktoryKubelek).add(wartosc);
        }
        for(int i = 0; i<dlugoscTab; i++){
            sortowanieBabelkowe(tablicaTablic.get(i));
        }
        int g = 0;
        double[] tabWynikowa = new double[tabWejsciowa.length];
        for (int i = 0; i < dlugoscTab; i++) {
            if (!(tablicaTablic.get(i).size() == 0)) {
                for (int j = 0; j < tablicaTablic.get(i).size(); j++) {
                    tabWynikowa[g++] = tablicaTablic.get(i).get(j);
                }
            }
        }
        for(int i = 0; i<tabWynikowa.length; i++){
            System.out.println(tabWynikowa[i]);
        }

    }
}

Słownik

kontener

(ang. container, collection) struktura danych, która w sposób zorganizowany przechowuje pewien zbiór danych; jednym z najpowszechniejszych kontenerów jest tablica, czyli uporządkowany zbiór o określonej z góry długości, który umożliwia dostęp do dowolnego elementu w dowolnym momencie poprzez indeks

stała

(ang. const) wartość, która w trakcie działania programu nie może zostać zmieniona; w języku Java stałe poprzedza się specyfikatorem final

typ całkowitoliczbowy

typ prymitywny, w którym nie ma wartości po przecinku; może przechowywać jedynie wartości całkowitoliczbowe, w tym wartości ujemne

wielowątkowość

cecha systemu operacyjnego, dzięki której w ramach jednego procesu może być wykonywanych kilka niezależnych wątków; wszystkie wątki w ramach tego samego procesu współdzielą tą samą przestrzeń adresową zawierającą kod programu i jego dane; wielowątkowość to także cecha procesorów, oznaczająca możliwość jednoczesnego wykonywania wielu wątków w sposób sprzętowy na pojedynczej jednostce wykonawczej – rdzeniu fizycznym

Film samouczek

Sprawdź się

Sortowanie kubełkowe – implementacja w języku Java

Sortowanie kubełkowe dla liczb rzeczywistych

Słownik