Przeczytaj

Sortowanie przez zliczanie

Zapiszemy algorytm sortowania liczb całkowitych za pomocą algorytmu sortowania przez zliczanie w języku Java.

Specyfikacja:

Dane:

tabWejsciowa – zbiór elementów do posortowania; tablica liczb całkowitych

Wynik:

tabWynikowa – posortowana niemalejąco tablica liczb całkowitych

Wyszukiwanie największego i najmniejszego elementu zapiszemy w funkcji znajdzMinxMax().

public static int[] znajdzMinMax(int[] tabWejsciowa) {
    int min = tabWejsciowa[0];
    int max = tabWejsciowa[0];

    for(int i = 1; i < tabWejsciowa.length; i++) {
        if (min > tabWejsciowa[i]) min = tabWejsciowa[i];
        if (max < tabWejsciowa[i]) max = tabWejsciowa[i];
    }

    return new int[] { min, max };
}

Po wyszukaniu najmniejszego i największego elementu należy zliczyć elementy.

Wykorzystamy do tego funkcję zlicz(). Realizację tego kroku zaczniemy od weryfikacji, ile różnych elementów mamy do zliczenia. W tym celu odejmujemy od elementu największego element najmniejszy i dodajemy 1 (tablice w języku Java indeksujemy od 0).

Przykład 1

Wiemy już, że dla tablicy tab = {1, -5, -6, 4, 5, 2} elementem największym jest 5, a najmniejszym: -6. Możemy policzyć, że tablica zliczeń będzie składać się z 5 - (-6) + 1 = 12 elementów.

Na podstawie uzyskanego wyniku zerujemy tablicę tabZliczajaca.

public static int[] znajdzMinMax(int[] tabWejsciowa) {
    int min = tabWejsciowa[0];
    int max = tabWejsciowa[0];

    for(int i = 1; i < tabWejsciowa.length; i++) {
        if (min > tabWejsciowa[i]) min = tabWejsciowa[i];
        if (max < tabWejsciowa[i]) max = tabWejsciowa[i];
    }

    return new int[] { min, max };
}

public static int[] zlicz(int min, int max, int[] tabWejsciowa) {
    int[] tabZliczajaca = new int[max - min + 1];

    for(int i = 0; i < tabZliczajaca.length; i++) {
        tabZliczajaca[i] = 0;
    }
}

Następnie zliczamy elementy. W tym celu iterujemy po wszystkich elementach tablicy tabWejsciowa. Wyznaczamy indeks komórki w tablicy tabZliczajaca, której wartość będziemy inkrementować. Odejmujemy od aktualnie przetwarzanej wartości tablicy tabWejsciowa wartość odczytaną ze zmiennej min.

Zwracamy tablicę tabZliczajaca.

Linia 1. 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 tabWejsciowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. int min znak równości tabWejsciowa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 3. int max znak równości tabWejsciowa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 5. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny tabWejsciowa kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. if otwórz nawias okrągły min zamknij nawias ostrokątny tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły min znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 7. if otwórz nawias okrągły max otwórz nawias ostrokątny tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły max znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 8. zamknij nawias klamrowy. Linia 10. return new int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias klamrowy min przecinek max zamknij nawias klamrowy średnik. Linia 11. zamknij nawias klamrowy. Linia 13. public static int otwórz nawias kwadratowy zamknij nawias kwadratowy zlicz otwórz nawias okrągły int min przecinek int max przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy tabWejsciowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca znak równości new int otwórz nawias kwadratowy max minus min plus 1 zamknij nawias kwadratowy średnik. Linia 16. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny tabZliczajaca kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 18. zamknij nawias klamrowy. Linia 20. 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 21. tabZliczajaca otwórz nawias kwadratowy tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy minus min zamknij nawias kwadratowy plus plus średnik. Linia 22. zamknij nawias klamrowy. Linia 24. return tabZliczajaca średnik. Linia 25. zamknij nawias klamrowy.

public static int[] znajdzMinMax(int[] tabWejsciowa) {
    int min = tabWejsciowa[0];
    int max = tabWejsciowa[0];

    for(int i = 1; i < tabWejsciowa.length; i++) {
        if (min > tabWejsciowa[i]) min = tabWejsciowa[i];
        if (max < tabWejsciowa[i]) max = tabWejsciowa[i];
    }

    return new int[] { min, max };
}

public static int[] zlicz(int min, int max, int[] tabWejsciowa) {
    int[] tabZliczajaca = new int[max - min + 1];

    for(int i = 0; i < tabZliczajaca.length; i++) {
        tabZliczajaca[i] = 0;
    }

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

    return tabZliczajaca;
}

Przykład 2

Dla tablicy dane = {1, -5, -6, 4, 5, 2} możemy wygenerować następującą tablicę tabZliczajaca:

Indeks	Jaki klucz reprezentuje	Zawartość `tablicaZliczajaca[indeks]`
$0$	$- 6$	$1$
$1$	$- 5$	$1$
$2$	$- 4$	$0$
$3$	$- 3$	$0$
$4$	$- 2$	$0$
$5$	$- 1$	$0$
$6$	$0$	$0$
$7$	$1$	$1$
$8$	$2$	$1$
$9$	$3$	$0$
$10$	$4$	$1$
$11$	$5$	$1$

Funkcja zliczNieWieksze() modyfikuje tablicę tabZliczajaca tak, aby każdy element zawierał liczbę elementów nie większych od niego.

Zaczynając od komórki o indeksie 1, sumujemy kolejne elementy tabZliczajaca, dodając do aktualnie zapisanej wartości zawartość komórki o indeksie o jeden mniejszym. Uzyskujemy w ten sposób pozycję, na której powinien zostać umieszczony ostatni element o wskazanym kluczukluczkluczu.

public static int[] znajdzMinMax(int[] tabWejsciowa) {
    int min = tabWejsciowa[0];
    int max = tabWejsciowa[0];

    for(int i = 1; i < tabWejsciowa.length; i++) {
        if (min > tabWejsciowa[i]) min = tabWejsciowa[i];
        if (max < tabWejsciowa[i]) max = tabWejsciowa[i];
    }

    return new int[] { min, max };
}

public static int[] zlicz(int min, int max, int[] tabWejsciowa) {
    int[] tabZliczajaca = new int[max - min + 1];

    for(int i = 0; i < tabZliczajaca.length; i++) {
        tabZliczajaca[i] = 0;
    }

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

    return tabZliczajaca;
}

public static void zliczNieWieksze(int[] tabZliczajaca) {
    for(int i = 1; i < tabZliczajaca.length; i++) {
        tabZliczajaca[i] = tabZliczajaca[i] + tabZliczajaca[i - 1];
    }
}

Przykład 3

Po przeprowadzeniu operacji sumowania dla tablicy dane = {1, -5, -6, 4, 5, 2}, otrzymujemy następującą tablicę tabZliczajaca:

Indeks	Jaki klucz reprezentuje	Zawartość `tablicaZliczajaca[indeks]`
$0$	$- 6$	$1$
$1$	$- 5$	$2$
$2$	$- 4$	$2$
$3$	$- 3$	$2$
$4$	$- 2$	$2$
$5$	$- 1$	$2$
$6$	$0$	$2$
$7$	$1$	$3$
$8$	$2$	$4$
$9$	$3$	$4$
$10$	$4$	$5$
$11$	$5$	$6$

Zapiszemy funkcję posortuj().

Na początku funkcja wywołuje funkcję znajdzMinMax(), aby znaleźć wartość minimalną i maksymalną w tablicy wejściowej. Te wartości są potrzebne do stworzenia tablicy zliczającej.

Następnie funkcja wywołuje funkcję zlicz(), aby stworzyć tablicę zliczającą o rozmiarze równej liczbie elementów w zakresie wartości w tablicy wejściowej. Dla każdej wartości w tablicy wejściowej funkcja zlicza, ile razy ta wartość występuje i zapisuje to w tablicy zliczającej.

W trzecim kroku funkcja wywołuje funkcję zliczNieWieksze(), która modyfikuje tablicę zliczającą tak, aby każdy element zawierał liczbę elementów nie większych od niego. Dzięki temu można uzyskać indeksy elementów posortowanej tablicy wynikowej.

Następnie tworzona jest tablica wynikowa o takim samym rozmiarze jak tablica wejściowa tabWejsciowa.

Algorytm sortowania przez zliczanie polega na przeglądaniu tablicy wejściowej tabWejsciowa od końca i wstawianiu elementów na odpowiednie miejsca w tablicy wynikowej tabWynikowa. Dlatego funkcja posortuj() przegląda tablicę wejściową w pętli od końca, a następnie dla każdej liczby znajduje jej indeks w tablicy wynikowej i tablicy zliczającej, a następnie wpisuje ją na odpowiednie miejsce w tablicy wynikowej.

Na końcu funkcja zwraca posortowaną tablicę wynikową.

W tej implementacji zostały zawarte komunikaty przeprowadzające użytkownika przez każdy krok algorytmu.

Kod programu:

Linia 1. import java kropka util kropka Arrays średnik. Linia 3. public class SortowaniePrzezZliczanie otwórz nawias klamrowy. Linia 5. 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 tabWejsciowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. int min znak równości tabWejsciowa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 7. int max znak równości tabWejsciowa 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 tabWejsciowa kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. if otwórz nawias okrągły min zamknij nawias ostrokątny tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły min znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 11. if otwórz nawias okrągły max otwórz nawias ostrokątny tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły max znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 12. zamknij nawias klamrowy. Linia 14. return new int otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias klamrowy min przecinek max zamknij nawias klamrowy średnik. Linia 15. zamknij nawias klamrowy. Linia 17. public static int otwórz nawias kwadratowy zamknij nawias kwadratowy zlicz otwórz nawias okrągły int min przecinek int max przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy tabWejsciowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca znak równości new int otwórz nawias kwadratowy max minus min plus 1 zamknij nawias kwadratowy średnik. Linia 20. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny tabZliczajaca kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 22. zamknij nawias klamrowy. Linia 24. 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 25. tabZliczajaca otwórz nawias kwadratowy tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy minus min zamknij nawias kwadratowy plus plus średnik. Linia 26. zamknij nawias klamrowy. Linia 28. return tabZliczajaca średnik. Linia 29. zamknij nawias klamrowy. Linia 31. public static void zliczNieWieksze otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca zamknij nawias okrągły otwórz nawias klamrowy. Linia 32. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny tabZliczajaca kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy plus tabZliczajaca otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy średnik. Linia 34. zamknij nawias klamrowy. Linia 35. zamknij nawias klamrowy. Linia 37. 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 tabWejsciowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 38. 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 39. int min znak równości minmax otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 40. int max znak równości minmax otwórz nawias kwadratowy 1 zamknij nawias kwadratowy średnik. Linia 42. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca znak równości zlicz otwórz nawias okrągły min przecinek max przecinek tabWejsciowa zamknij nawias okrągły średnik. Linia 43. zliczNieWieksze otwórz nawias okrągły tabZliczajaca zamknij nawias okrągły średnik. Linia 45. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabWynikowa znak równości new int otwórz nawias kwadratowy tabWejsciowa kropka length zamknij nawias kwadratowy średnik. Linia 47. for otwórz nawias okrągły int i znak równości tabWejsciowa kropka length minus 1 średnik i zamknij nawias ostrokątny znak równości 0 średnik i minus minus zamknij nawias okrągły otwórz nawias klamrowy. Linia 48. System kropka out kropka println otwórz nawias okrągły cudzysłów Badana liczba dwukropek cudzysłów plus tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 49. System kropka out kropka println otwórz nawias okrągły cudzysłów tabWynikowa przed wykonaniem kroku dwukropek cudzysłów plus Arrays kropka toString otwórz nawias okrągły tabWynikowa zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 50. System kropka out kropka println otwórz nawias okrągły cudzysłów tabZliczajaca przed wykonaniem kroku dwukropek cudzysłów plus Arrays kropka toString otwórz nawias okrągły tabZliczajaca zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 51. System kropka out kropka println otwórz nawias okrągły cudzysłów Wykonanie algorytmu kropka cudzysłów zamknij nawias okrągły średnik. Linia 53. int indeksTabZliczajaca znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy minus min średnik. Linia 54. int indeksTabWynikowa znak równości tabZliczajaca otwórz nawias kwadratowy indeksTabZliczajaca zamknij nawias kwadratowy minus 1 średnik. Linia 56. tabWynikowa otwórz nawias kwadratowy indeksTabWynikowa zamknij nawias kwadratowy znak równości tabWejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 57. tabZliczajaca otwórz nawias kwadratowy indeksTabZliczajaca zamknij nawias kwadratowy minus minus średnik. Linia 59. System kropka out kropka println otwórz nawias okrągły cudzysłów tabWynikowa po wykonaniu kroku dwukropek cudzysłów plus Arrays kropka toString otwórz nawias okrągły tabWynikowa zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 60. System kropka out kropka println otwórz nawias okrągły cudzysłów tabZliczajaca po wykonaniu kroku dwukropek cudzysłów plus Arrays kropka toString otwórz nawias okrągły tabZliczajaca zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 61. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 62. zamknij nawias klamrowy. Linia 64. return tabWynikowa średnik. Linia 65. zamknij nawias klamrowy. Linia 67. 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 68. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabWejsciowa znak równości otwórz nawias klamrowy minus 2 przecinek 0 przecinek 3 przecinek 1 przecinek 1 przecinek 3 przecinek 2 zamknij nawias klamrowy średnik. Linia 70. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabWynikowa znak równości posortuj otwórz nawias okrągły tabWejsciowa zamknij nawias okrągły średnik. Linia 72. System kropka out kropka println otwórz nawias okrągły cudzysłów Po wykonaniu algorytmu tabWynikowa wyglada nastepujaco dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 73. System kropka out kropka println otwórz nawias okrągły Arrays kropka toString otwórz nawias okrągły tabWynikowa zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 74. zamknij nawias klamrowy. Linia 75. zamknij nawias klamrowy.

import java.util.Arrays;

public class SortowaniePrzezZliczanie {
    
    public static int[] znajdzMinMax(int[] tabWejsciowa) {
        int min = tabWejsciowa[0];
        int max = tabWejsciowa[0];
        
        for(int i = 1; i < tabWejsciowa.length; i++) {
            if (min > tabWejsciowa[i]) min = tabWejsciowa[i];
            if (max < tabWejsciowa[i]) max = tabWejsciowa[i];
        }
        
        return new int[] { min, max };
    }
    
    public static int[] zlicz(int min, int max, int[] tabWejsciowa) {
        int[] tabZliczajaca = new int[max - min + 1];
        
        for(int i = 0; i < tabZliczajaca.length; i++) {
            tabZliczajaca[i] = 0;
        }

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

        return tabZliczajaca;
    }

    public static void zliczNieWieksze(int[] tabZliczajaca) {
        for(int i = 1; i < tabZliczajaca.length; i++) {
            tabZliczajaca[i] = tabZliczajaca[i] + tabZliczajaca[i - 1];
        }
    }

    public static int[] posortuj(int [] tabWejsciowa){
        int[] minmax = znajdzMinMax(tabWejsciowa);
        int min = minmax[0];
        int max = minmax[1];
        
        int[] tabZliczajaca = zlicz(min, max, tabWejsciowa);
        zliczNieWieksze(tabZliczajaca);
        
        int[] tabWynikowa = new int[tabWejsciowa.length];
        
        for(int i = tabWejsciowa.length - 1; i >= 0; i--) {
            System.out.println("Badana liczba: " + tabWejsciowa[i]);
            System.out.println("tabWynikowa przed wykonaniem kroku: " + Arrays.toString(tabWynikowa));
            System.out.println("tabZliczajaca przed wykonaniem kroku: " + Arrays.toString(tabZliczajaca));
            System.out.println("Wykonanie algorytmu.");
            
            int indeksTabZliczajaca = tabWejsciowa[i] - min;
            int indeksTabWynikowa = tabZliczajaca[indeksTabZliczajaca] - 1;
            
            tabWynikowa[indeksTabWynikowa] = tabWejsciowa[i];
            tabZliczajaca[indeksTabZliczajaca]--;
            
            System.out.println("tabWynikowa po wykonaniu kroku: " + Arrays.toString(tabWynikowa));
            System.out.println("tabZliczajaca po wykonaniu kroku: " + Arrays.toString(tabZliczajaca));
            System.out.println();
        }
        
        return tabWynikowa;
    }

    public static void main(String[] args) {
        int[] tabWejsciowa = {-2, 0, 3, 1, 1, 3, 2};
		
        int[] tabWynikowa = posortuj(tabWejsciowa);
        
        System.out.println("Po wykonaniu algorytmu tabWynikowa wyglada nastepujaco:");
        System.out.println(Arrays.toString(tabWynikowa));
    }
}

Wynik wykonywania kodu będzie następujący:

Linia 1. Badana liczba dwukropek 2. Linia 2. tabWynikowa przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 3. tabZliczajaca przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 4 przecinek 5 przecinek 7 zamknij nawias kwadratowy. Linia 4. Wykonanie algorytmu kropka. Linia 5. tabWynikowa przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 2 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 6. tabZliczajaca przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 4 przecinek 4 przecinek 7 zamknij nawias kwadratowy. Linia 8. Badana liczba dwukropek 3. Linia 9. tabWynikowa przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 2 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 10. tabZliczajaca przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 4 przecinek 4 przecinek 7 zamknij nawias kwadratowy. Linia 11. Wykonanie algorytmu kropka. Linia 12. tabWynikowa przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 2 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 13. tabZliczajaca przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 4 przecinek 4 przecinek 6 zamknij nawias kwadratowy. Linia 15. Badana liczba dwukropek 1. Linia 16. tabWynikowa przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 2 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 17. tabZliczajaca przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 4 przecinek 4 przecinek 6 zamknij nawias kwadratowy. Linia 18. Wykonanie algorytmu kropka. Linia 19. tabWynikowa przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 1 przecinek 2 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 20. tabZliczajaca przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 3 przecinek 4 przecinek 6 zamknij nawias kwadratowy. Linia 22. Badana liczba dwukropek 1. Linia 23. tabWynikowa przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 1 przecinek 2 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 24. tabZliczajaca przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 3 przecinek 4 przecinek 6 zamknij nawias kwadratowy. Linia 25. Wykonanie algorytmu kropka. Linia 26. tabWynikowa przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 27. tabZliczajaca przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 2 przecinek 4 przecinek 6 zamknij nawias kwadratowy. Linia 29. Badana liczba dwukropek 3. Linia 30. tabWynikowa przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 31. tabZliczajaca przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 2 przecinek 4 przecinek 6 zamknij nawias kwadratowy. Linia 32. Wykonanie algorytmu kropka. Linia 33. tabWynikowa przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 3 przecinek 3 zamknij nawias kwadratowy. Linia 34. tabZliczajaca przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 2 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 36. Badana liczba dwukropek 0. Linia 37. tabWynikowa przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 3 przecinek 3 zamknij nawias kwadratowy. Linia 38. tabZliczajaca przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 2 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 39. Wykonanie algorytmu kropka. Linia 40. tabWynikowa przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 3 przecinek 3 zamknij nawias kwadratowy. Linia 41. tabZliczajaca przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 1 przecinek 2 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 43. Badana liczba dwukropek minus 2. Linia 44. tabWynikowa przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 3 przecinek 3 zamknij nawias kwadratowy. Linia 45. tabZliczajaca przecinek przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 1 przecinek 2 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 46. Wykonanie algorytmu kropka. Linia 47. tabWynikowa przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy minus 2 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 3 przecinek 3 zamknij nawias kwadratowy. Linia 48. tabZliczajaca przecinek po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 1 przecinek 1 przecinek 2 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 50. Po wykonaniu algorytmu tabWynikowa wyglada następująco dwukropek. Linia 51. otwórz nawias kwadratowy minus 2 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 3 przecinek 3 zamknij nawias kwadratowy.

Badana liczba: 2
tabWynikowa, przed wykonaniem kroku: [0, 0, 0, 0, 0, 0, 0]
tabZliczajaca, przed wykonaniem kroku: [1, 1, 2, 4, 5, 7]
Wykonanie algorytmu.
tabWynikowa, po wykonaniu kroku: [0, 0, 0, 0, 2, 0, 0]
tabZliczajaca, po wykonaniu kroku: [1, 1, 2, 4, 4, 7]

Badana liczba: 3
tabWynikowa, przed wykonaniem kroku: [0, 0, 0, 0, 2, 0, 0]
tabZliczajaca, przed wykonaniem kroku: [1, 1, 2, 4, 4, 7]
Wykonanie algorytmu.
tabWynikowa, po wykonaniu kroku: [0, 0, 0, 0, 2, 0, 3]
tabZliczajaca, po wykonaniu kroku: [1, 1, 2, 4, 4, 6]

Badana liczba: 1
tabWynikowa, przed wykonaniem kroku: [0, 0, 0, 0, 2, 0, 3]
tabZliczajaca, przed wykonaniem kroku: [1, 1, 2, 4, 4, 6]
Wykonanie algorytmu.
tabWynikowa, po wykonaniu kroku: [0, 0, 0, 1, 2, 0, 3]
tabZliczajaca, po wykonaniu kroku: [1, 1, 2, 3, 4, 6]

Badana liczba: 1
tabWynikowa, przed wykonaniem kroku: [0, 0, 0, 1, 2, 0, 3]
tabZliczajaca, przed wykonaniem kroku: [1, 1, 2, 3, 4, 6]
Wykonanie algorytmu.
tabWynikowa, po wykonaniu kroku: [0, 0, 1, 1, 2, 0, 3]
tabZliczajaca, po wykonaniu kroku: [1, 1, 2, 2, 4, 6]

Badana liczba: 3
tabWynikowa, przed wykonaniem kroku: [0, 0, 1, 1, 2, 0, 3]
tabZliczajaca, przed wykonaniem kroku: [1, 1, 2, 2, 4, 6]
Wykonanie algorytmu.
tabWynikowa, po wykonaniu kroku: [0, 0, 1, 1, 2, 3, 3]
tabZliczajaca, po wykonaniu kroku: [1, 1, 2, 2, 4, 5]

Badana liczba: 0
tabWynikowa, przed wykonaniem kroku: [0, 0, 1, 1, 2, 3, 3]
tabZliczajaca, przed wykonaniem kroku: [1, 1, 2, 2, 4, 5]
Wykonanie algorytmu.
tabWynikowa, po wykonaniu kroku: [0, 0, 1, 1, 2, 3, 3]
tabZliczajaca, po wykonaniu kroku: [1, 1, 1, 2, 4, 5]

Badana liczba: -2
tabWynikowa, przed wykonaniem kroku: [0, 0, 1, 1, 2, 3, 3]
tabZliczajaca, przed wykonaniem kroku: [1, 1, 1, 2, 4, 5]
Wykonanie algorytmu.
tabWynikowa, po wykonaniu kroku: [-2, 0, 1, 1, 2, 3, 3]
tabZliczajaca, po wykonaniu kroku: [0, 1, 1, 2, 4, 5]

Po wykonaniu algorytmu tabWynikowa wyglada następująco:
[-2, 0, 1, 1, 2, 3, 3]

Do wypisania tablic użyliśmy klasy Arrays i jej metody toString, aby ją zastosować, musieliśmy ją zaimportować w następujący sposób: import java.util.Arrays; w pierwszej linijce kodu.

Ciekawostka

Algorytm ten jest podobny w działaniu do algorytmu sortowania kubełkowego. Jeśli chcesz zapoznać się z jego działaniem, zajrzyj do e‑materiału Sortowanie kubełkowePPpmzST7zSortowanie kubełkowe.

Polecenie 1

Na podstawie przedstawionej analizy algorytmu, napisz program w języku Java sortujący nierosnąco podane elementy tablicy dane[] metodą sortowania przez zliczanie (couting sort).

Specyfikacja problemu

Dane:

dane[] – tablica liczb całkowitych

Wynik:

posortowana nierosnąco tablica liczb całkowitych dane[]

RmVx0bnUaxLHo

Polecenie 2

Porównaj swoje rozwiązanie z przedstawionym w filmie. Jakie różnice dostrzegasz?

Rx1KEhnRvigY9

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Rdaa7MPvCkM8f

Przycisk do pobrania TXT z kodem źródłowym z filmu.

Plik TXT o rozmiarze 952.00 B w języku polskim

Słownik

klucz

w kontekście sortowania przez zliczanie może być rozumiany jako coś jednoznacznie identyfikującego obiekt; przykładem klucza jest wartość lub słowo

sortowanie stabilne

rodzaj sortowania gwarantujący umieszczenie w tablicy wynikowej elementów o tej samej wartości, względem siebie, w takiej samej kolejności jak w tablicy wejściowej

Wprowadzenie

Schemat interaktywny

Sortowanie przez zliczanie

Słownik