Sprawdź się

Pokaż ćwiczenia:

Ćwiczenie 1

Uzupełnij brakujące miejsca w kodzie tak, aby otrzymać działający program realizujący algorytm sortowania pozycyjnego słów. Dane powinny zostać posortowane leksykograficznie. Swój program przetestuj dla danych magda, ala, adam, ewa. Skorzystaj z wybranego przez siebie stabilnego algorytmu sortowania.

Specyfikacja problemu:

Dane:

dane – jednowymiarowa tablica zawierająca imiona do posortowania

Wynik:

program wypisuje posortowaną tablicę dane w porządku leksykograficznym; kolejne elementy tablicy wypisywane są w nowej linii

R1xGiXcMgx5ea

Przykładowe rozwiązanie zadania:

Linia 1. public class Main otwórz nawias klamrowy. Linia 3. static void przygotujSlowa otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy dane przecinek int dlugoscNajdluzszegoSlowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. while otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły otwórz nawias ostrokątny dlugoscNajdluzszegoSlowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów ` cudzysłów średnik. Linia 7. zamknij nawias klamrowy. Linia 8. zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy. Linia 11. static void wyczyscNapisy otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy dane zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka replace otwórz nawias okrągły cudzysłów ` cudzysłów przecinek cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 14. zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy. Linia 17. static void radixSort otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy dane zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. int dlugoscNajdluzszegoSlowa znak równości dane otwórz nawias kwadratowy 0 zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 20. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny dane kropka length minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. if otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły zamknij nawias ostrokątny dlugoscNajdluzszegoSlowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. dlugoscNajdluzszegoSlowa znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy. Linia 26. przygotujSlowa otwórz nawias okrągły dane przecinek dlugoscNajdluzszegoSlowa zamknij nawias okrągły średnik. Linia 28. for otwórz nawias okrągły int i znak równości dlugoscNajdluzszegoSlowa 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 29. sortowaniePrzezZliczanie otwórz nawias okrągły dane przecinek i zamknij nawias okrągły średnik. Linia 30. zamknij nawias klamrowy. Linia 32. wyczyscNapisy otwórz nawias okrągły dane zamknij nawias okrągły średnik. Linia 33. zamknij nawias klamrowy. Linia 35. static void sortowaniePrzezZliczanie otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy dane przecinek int indeksZnaku zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. int otwórz nawias kwadratowy zamknij nawias kwadratowy tablicaZliczenLiczb znak równości new int otwórz nawias kwadratowy 27 zamknij nawias kwadratowy średnik. Linia 39. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. int odczytanyKodZnaku znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka charAt otwórz nawias okrągły indeksZnaku zamknij nawias okrągły minus apostrof ` apostrof średnik. Linia 41. tablicaZliczenLiczb otwórz nawias kwadratowy odczytanyKodZnaku zamknij nawias kwadratowy plus plus średnik. Linia 43. zamknij nawias klamrowy. Linia 45. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny 27 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 46. tablicaZliczenLiczb otwórz nawias kwadratowy i zamknij nawias kwadratowy plus znak równości tablicaZliczenLiczb otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy średnik. Linia 47. zamknij nawias klamrowy. Linia 49. String otwórz nawias kwadratowy zamknij nawias kwadratowy temp znak równości new String otwórz nawias kwadratowy dane kropka length zamknij nawias kwadratowy średnik. Linia 51. for otwórz nawias okrągły int i znak równości dane 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 52. int odczytanyKodZnaku znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka charAt otwórz nawias okrągły indeksZnaku zamknij nawias okrągły minus apostrof ` apostrof średnik. Linia 53. int indeksWTablicyWynikowej znak równości tablicaZliczenLiczb otwórz nawias kwadratowy odczytanyKodZnaku zamknij nawias kwadratowy minus 1 średnik. Linia 54. temp otwórz nawias kwadratowy indeksWTablicyWynikowej zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 55. tablicaZliczenLiczb otwórz nawias kwadratowy odczytanyKodZnaku zamknij nawias kwadratowy minus minus średnik. Linia 56. 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 temp kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 59. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości temp otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 60. zamknij nawias klamrowy. Linia 62. zamknij nawias klamrowy. Linia 64. 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 65. String otwórz nawias kwadratowy zamknij nawias kwadratowy dane znak równości otwórz nawias klamrowy. Linia 66. cudzysłów magda cudzysłów przecinek. Linia 67. cudzysłów ala cudzysłów przecinek. Linia 68. cudzysłów adam cudzysłów przecinek. Linia 69. cudzysłów ewa cudzysłów. Linia 70. zamknij nawias klamrowy średnik. Linia 72. radixSort otwórz nawias okrągły dane zamknij nawias okrągły średnik. Linia 73. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 74. System kropka out kropka println otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 75. zamknij nawias klamrowy. Linia 76. zamknij nawias klamrowy. Linia 77. zamknij nawias klamrowy.

public class Main {

    static void przygotujSlowa(String[] dane, int dlugoscNajdluzszegoSlowa) {
        for (int i = 0; i < dane.length; i++) {
            while (dane[i].length() < dlugoscNajdluzszegoSlowa) {
                dane[i] = dane[i] + "`";
            }
        }
    }

    static void wyczyscNapisy(String[] dane) {
        for (int i = 0; i < dane.length; i++) {
            dane[i] = dane[i].replace("`", "");
        }
    }

    static void radixSort(String[] dane) {
        int dlugoscNajdluzszegoSlowa = dane[0].length();

        for (int i = 1; i < dane.length - 1; i++) {
            if(dane[i].length() > dlugoscNajdluzszegoSlowa) {
                dlugoscNajdluzszegoSlowa = dane[i].length();
            }
        }    

        przygotujSlowa(dane, dlugoscNajdluzszegoSlowa);

        for (int i = dlugoscNajdluzszegoSlowa - 1; i >= 0; i--) {
            sortowaniePrzezZliczanie(dane, i);
        }

        wyczyscNapisy(dane);
    }

    static void sortowaniePrzezZliczanie(String[] dane, int indeksZnaku) {

        int[] tablicaZliczenLiczb = new int[27];

        for (int i = 0; i < dane.length; i++) {
            int odczytanyKodZnaku = dane[i].charAt(indeksZnaku) - '`';
            tablicaZliczenLiczb[odczytanyKodZnaku]++;

        }

        for (int i = 1; i < 27; i++) {
            tablicaZliczenLiczb[i] += tablicaZliczenLiczb[i - 1];
        }

        String[] temp = new String[dane.length];

        for (int i = dane.length - 1; i >= 0; i--) {
            int odczytanyKodZnaku = dane[i].charAt(indeksZnaku) - '`';
            int indeksWTablicyWynikowej = tablicaZliczenLiczb[odczytanyKodZnaku] - 1;
            temp[indeksWTablicyWynikowej] = dane[i];
            tablicaZliczenLiczb[odczytanyKodZnaku]--;
        }

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

    }

    public static void main(String[] args) {
        String[] dane = {
            "magda",
            "ala",
            "adam",
            "ewa"
        };

        radixSort(dane);
        for (int i = 0; i < dane.length; i++) {
            System.out.println(dane[i]);
        }
    }
}

Ćwiczenie 2

Zmodyfikuj podany kod tak, aby sortował pozycyjnie ciągi znaków utworzone z cyfr. Dane powinny być posortowane w porządku odwrotnym do leksykograficznego. W porządku leksykograficznym ciąg „11” powinien znaleźć się przed ciągiem „9” (traktujemy liczby jakby to były słowa). W tym zadaniu jednak stosujemy porządek odwrotny do leksykograficznego, zatem „9” powinno stać przed „11”. W sortowaniu pozycyjnym zastosuj wybrany przez siebie stabilny algorytm sortowania.

Specyfikacja problemu:

Dane:

dane – jednowymiarowa tablica przechowująca łańcuchy znaków będące ciągami cyfr do posortowania

Wynik:

program wypisuje posortowaną w porządku odwrotnym do leksykograficznego tablicę dane; kolejne elementy tablicy wypisywane są w nowej linii

RBkjE1B5Fg1pN

Przykładowe rozwiązanie zadania:

Linia 1. public class Main otwórz nawias klamrowy. Linia 3. static void przygotujSlowa otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy dane przecinek int dlugoscNajdluzszegoSlowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. while otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły otwórz nawias ostrokątny dlugoscNajdluzszegoSlowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów prawy ukośnik cudzysłów średnik. Linia 7. zamknij nawias klamrowy. Linia 8. zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy. Linia 11. static void wyczyscNapisy otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy dane zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka replace otwórz nawias okrągły cudzysłów prawy ukośnik cudzysłów przecinek cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 14. zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy. Linia 17. static void radixSort otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy dane zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. int dlugoscNajdluzszegoSlowa znak równości dane otwórz nawias kwadratowy 0 zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 20. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny dane kropka length minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. if otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły zamknij nawias ostrokątny dlugoscNajdluzszegoSlowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. dlugoscNajdluzszegoSlowa znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy. Linia 26. przygotujSlowa otwórz nawias okrągły dane przecinek dlugoscNajdluzszegoSlowa zamknij nawias okrągły średnik. Linia 28. for otwórz nawias okrągły int i znak równości dlugoscNajdluzszegoSlowa 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 29. sortowanieBabelkowe otwórz nawias okrągły dane przecinek i zamknij nawias okrągły średnik. Linia 30. zamknij nawias klamrowy. Linia 32. wyczyscNapisy otwórz nawias okrągły dane zamknij nawias okrągły średnik. Linia 33. zamknij nawias klamrowy. Linia 35. static void sortowanieBabelkowe otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy slowa przecinek int indeksZnaku zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. int n znak równości slowa kropka length średnik. Linia 37. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n minus 1 średnik i plus plus zamknij nawias okrągły. Linia 38. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny n minus i minus 1 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 39. if otwórz nawias okrągły slowa otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły zamknij nawias ostrokątny indeksZnaku ampersant ampersant slowa otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły zamknij nawias ostrokątny indeksZnaku zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. if otwórz nawias okrągły slowa otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka charAt otwórz nawias okrągły indeksZnaku zamknij nawias okrągły otwórz nawias ostrokątny slowa otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy kropka charAt otwórz nawias okrągły indeksZnaku zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 41. String pom znak równości slowa otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 42. slowa otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości slowa otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy średnik. Linia 43. slowa otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości pom średnik. Linia 44. zamknij nawias klamrowy. Linia 45. zamknij nawias klamrowy. Linia 46. zamknij nawias klamrowy. Linia 47. zamknij nawias klamrowy. Linia 49. 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 50. String otwórz nawias kwadratowy zamknij nawias kwadratowy dane znak równości otwórz nawias klamrowy. Linia 51. cudzysłów 0123 cudzysłów przecinek. Linia 52. cudzysłów 94141 cudzysłów przecinek. Linia 53. cudzysłów 119 cudzysłów przecinek. Linia 54. cudzysłów 4964 cudzysłów przecinek. Linia 55. cudzysłów 750 cudzysłów przecinek. Linia 56. cudzysłów 0 cudzysłów. Linia 57. zamknij nawias klamrowy średnik. Linia 59. radixSort otwórz nawias okrągły dane zamknij nawias okrągły średnik. Linia 60. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 61. System kropka out kropka println otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 62. zamknij nawias klamrowy. Linia 63. zamknij nawias klamrowy. Linia 64. zamknij nawias klamrowy.

public class Main {

    static void przygotujSlowa(String[] dane, int dlugoscNajdluzszegoSlowa) {
        for (int i = 0; i < dane.length; i++) {
            while (dane[i].length() < dlugoscNajdluzszegoSlowa) {
                dane[i] = dane[i] + "/";
            }
        }
    }

    static void wyczyscNapisy(String[] dane) {
        for (int i = 0; i < dane.length; i++) {
            dane[i] = dane[i].replace("/", "");
        }
    }

    static void radixSort(String[] dane) {
        int dlugoscNajdluzszegoSlowa = dane[0].length();

        for (int i = 1; i < dane.length - 1; i++) {
            if(dane[i].length() > dlugoscNajdluzszegoSlowa) {
                dlugoscNajdluzszegoSlowa = dane[i].length();
            }
        }    

        przygotujSlowa(dane, dlugoscNajdluzszegoSlowa);

        for (int i = dlugoscNajdluzszegoSlowa - 1; i >= 0; i--) {
            sortowanieBabelkowe(dane, i);
        }

        wyczyscNapisy(dane);
    }

    static void sortowanieBabelkowe(String[] slowa, int indeksZnaku) {
        int n = slowa.length;
        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < n - i - 1; j++) {
                if (slowa[j].length() > indeksZnaku && slowa[j + 1].length() > indeksZnaku) {
                    if (slowa[j].charAt(indeksZnaku) < slowa[j + 1].charAt(indeksZnaku)) {
                        String pom = slowa[j];
                        slowa[j] = slowa[j + 1];
                        slowa[j + 1] = pom;
                    }
                }
            }
    }

    public static void main(String[] args) {
        String[] dane = {
                "0123",
                "94141",
                "119",
                "4964",
                "750",
                "0"
        };

        radixSort(dane);
        for (int i = 0; i < dane.length; i++) {
            System.out.println(dane[i]);
        }
    }
}

Ćwiczenie 3

Organizatorzy debaty na podstawie zgłoszeń przygotowali listę dziennikarzy, którzy po kolei będą zadawać pytania politykom. Kolejność pytań miała zostać ustalona według porządku alfabetycznego. Zgłoszenia przychodziły jednak w losowej kolejności. Dziennikarka o nazwisku Kornas do ostatniej chwili nie potwierdziła swojej obecności na debacie – miała połączyć się ze studiem telefonicznie. Zespół odpowiedzialny za połączenie oczekuje na informację, która w kolejności powinna być ta osoba. Użyj sortowania pozycyjnego słów, aby wyznaczyć kolejność (indeks) tej dziennikarki w posortowanej liście.

W sortowaniu pozycyjnym skorzystaj z dowolnego stabilnego algorytmu sortowania. Zwróć uwagę, że stosujemy numerację od 0.

Dla ułatwienia nazwiska zapisano małymi literami oraz bez znaków diakrytycznych.

Specyfikacja problemu:

Dane:

dane – jednowymiarowa tablica zawierająca nazwiska dziennikarek i dziennikarzy

Wynik:

program wypisuje posortowaną w kolejności leksykograficznej tablicę dane oraz indeks elementu kornas w posortowanej tablicy dane

RAbi753hnQCNW

Przykładowe rozwiązanie zadania:

Linia 1. public class Main otwórz nawias klamrowy. Linia 3. static void przygotujNazwiska otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy dane przecinek int dlugoscNajdluzszegoNazwiska zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. while otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły otwórz nawias ostrokątny dlugoscNajdluzszegoNazwiska zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów ` cudzysłów średnik. Linia 7. zamknij nawias klamrowy. Linia 8. zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy. Linia 11. static void wyczyscNapisy otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy dane zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka replace otwórz nawias okrągły cudzysłów ` cudzysłów przecinek cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 14. zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy. Linia 17. static void radixSort otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy dane zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. int dlugoscNajdluzszegoNazwiska znak równości dane otwórz nawias kwadratowy 0 zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 20. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny dane kropka length minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. if otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły zamknij nawias ostrokątny dlugoscNajdluzszegoNazwiska zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. dlugoscNajdluzszegoNazwiska znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy. Linia 26. przygotujNazwiska otwórz nawias okrągły dane przecinek dlugoscNajdluzszegoNazwiska zamknij nawias okrągły średnik. Linia 28. for otwórz nawias okrągły int i znak równości dlugoscNajdluzszegoNazwiska 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 29. sortowaniePrzezZliczanie otwórz nawias okrągły dane przecinek i zamknij nawias okrągły średnik. Linia 30. zamknij nawias klamrowy. Linia 32. wyczyscNapisy otwórz nawias okrągły dane zamknij nawias okrągły średnik. Linia 33. zamknij nawias klamrowy. Linia 35. static void sortowaniePrzezZliczanie otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy dane przecinek int indeksZnaku zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. int otwórz nawias kwadratowy zamknij nawias kwadratowy tablicaZliczenLiczb znak równości new int otwórz nawias kwadratowy 27 zamknij nawias kwadratowy średnik. Linia 39. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. int odczytanyKodZnaku znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka charAt otwórz nawias okrągły indeksZnaku zamknij nawias okrągły minus apostrof ` apostrof średnik. Linia 41. tablicaZliczenLiczb otwórz nawias kwadratowy odczytanyKodZnaku zamknij nawias kwadratowy plus plus średnik. Linia 43. zamknij nawias klamrowy. Linia 45. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny 27 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 46. tablicaZliczenLiczb otwórz nawias kwadratowy i zamknij nawias kwadratowy plus znak równości tablicaZliczenLiczb otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy średnik. Linia 47. zamknij nawias klamrowy. Linia 49. String otwórz nawias kwadratowy zamknij nawias kwadratowy temp znak równości new String otwórz nawias kwadratowy dane kropka length zamknij nawias kwadratowy średnik. Linia 51. for otwórz nawias okrągły int i znak równości dane 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 52. int odczytanyKodZnaku znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka charAt otwórz nawias okrągły indeksZnaku zamknij nawias okrągły minus apostrof ` apostrof średnik. Linia 53. int indeksWTablicyWynikowej znak równości tablicaZliczenLiczb otwórz nawias kwadratowy odczytanyKodZnaku zamknij nawias kwadratowy minus 1 średnik. Linia 54. temp otwórz nawias kwadratowy indeksWTablicyWynikowej zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 55. tablicaZliczenLiczb otwórz nawias kwadratowy odczytanyKodZnaku zamknij nawias kwadratowy minus minus średnik. Linia 56. 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 temp kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 59. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości temp otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 60. zamknij nawias klamrowy. Linia 62. zamknij nawias klamrowy. Linia 64. static int znajdzNazwisko otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy dane zamknij nawias okrągły otwórz nawias klamrowy. Linia 65. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 66. if otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka equals otwórz nawias okrągły cudzysłów kornas cudzysłów zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 67. return i średnik. Linia 68. zamknij nawias klamrowy. Linia 69. zamknij nawias klamrowy. Linia 70. return minus 1 średnik. Linia 71. zamknij nawias klamrowy. Linia 73. 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 74. String otwórz nawias kwadratowy zamknij nawias kwadratowy dane znak równości otwórz nawias klamrowy. Linia 75. cudzysłów kaluza cudzysłów przecinek. Linia 76. cudzysłów wasniewski cudzysłów przecinek. Linia 77. cudzysłów klasa cudzysłów przecinek. Linia 78. cudzysłów fil cudzysłów przecinek. Linia 79. cudzysłów leszko cudzysłów przecinek. Linia 80. cudzysłów radtke cudzysłów przecinek. Linia 81. cudzysłów stepniak cudzysłów przecinek. Linia 82. cudzysłów falek cudzysłów przecinek. Linia 83. cudzysłów skrzypek cudzysłów przecinek. Linia 84. cudzysłów smykowska cudzysłów przecinek. Linia 85. cudzysłów sroka cudzysłów przecinek. Linia 86. cudzysłów kornas cudzysłów przecinek. Linia 87. cudzysłów pustelnik cudzysłów. Linia 88. zamknij nawias klamrowy średnik. Linia 90. radixSort otwórz nawias okrągły dane zamknij nawias okrągły średnik. Linia 92. System kropka out kropka println otwórz nawias okrągły znajdzNazwisko otwórz nawias okrągły dane zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 93. zamknij nawias klamrowy. Linia 94. zamknij nawias klamrowy.

public class Main {

    static void przygotujNazwiska(String[] dane, int dlugoscNajdluzszegoNazwiska) {
        for (int i = 0; i < dane.length; i++) {
            while (dane[i].length() < dlugoscNajdluzszegoNazwiska) {
                dane[i] = dane[i] + "`";
            }
        }
    }

    static void wyczyscNapisy(String[] dane) {
        for (int i = 0; i < dane.length; i++) {
            dane[i] = dane[i].replace("`", "");
        }
    }

    static void radixSort(String[] dane) {
        int dlugoscNajdluzszegoNazwiska = dane[0].length();

        for (int i = 1; i < dane.length - 1; i++) {
            if(dane[i].length() > dlugoscNajdluzszegoNazwiska) {
                dlugoscNajdluzszegoNazwiska = dane[i].length();
            }
        }    

        przygotujNazwiska(dane, dlugoscNajdluzszegoNazwiska);

        for (int i = dlugoscNajdluzszegoNazwiska - 1; i >= 0; i--) {
            sortowaniePrzezZliczanie(dane, i);
        }

        wyczyscNapisy(dane);
    }

    static void sortowaniePrzezZliczanie(String[] dane, int indeksZnaku) {

        int[] tablicaZliczenLiczb = new int[27];

        for (int i = 0; i < dane.length; i++) {
            int odczytanyKodZnaku = dane[i].charAt(indeksZnaku) - '`';
            tablicaZliczenLiczb[odczytanyKodZnaku]++;

        }

        for (int i = 1; i < 27; i++) {
            tablicaZliczenLiczb[i] += tablicaZliczenLiczb[i - 1];
        }

        String[] temp = new String[dane.length];

        for (int i = dane.length - 1; i >= 0; i--) {
            int odczytanyKodZnaku = dane[i].charAt(indeksZnaku) - '`';
            int indeksWTablicyWynikowej = tablicaZliczenLiczb[odczytanyKodZnaku] - 1;
            temp[indeksWTablicyWynikowej] = dane[i];
            tablicaZliczenLiczb[odczytanyKodZnaku]--;
        }

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

    }

    static int znajdzNazwisko(String[] dane) {
        for (int i = 0; i < dane.length; i++) {
            if (dane[i].equals("kornas")) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String[] dane = {
            "kaluza",
            "wasniewski",
            "klasa",
            "fil",
            "leszko",
            "radtke",
            "stepniak",
            "falek",
            "skrzypek",
            "smykowska",
            "sroka",
            "kornas",
            "pustelnik"
        };
        
        radixSort(dane);

        System.out.println(znajdzNazwisko(dane));
    }
}

Przeczytaj

Dla nauczyciela