Strefa wyzwań - I_P_W14_M12_Java Sortowanie metodą bąbelkową

RF7VY1C3G78X2

Już wiesz

na czym polega działanie algorytmu sortowania bąbelkowego i jakie usprawnienia można w nim zastosować,
jak ocenić jego złożoność czasową i pamięciową,
jak przebiega sortowanie bąbelkowe na przykładowym ciągu,
jak działa implementacja algorytmu w języku Java oraz jak przygotować własną wersję programu.

Teraz czas, aby sprawdzić wiedzę i umiejętności w praktyce.

Ćwiczenie 1

Napisz program, który wykorzystując metodę bąbelkową, wyznaczy i przesunie na początek ciągu liczbowego (reprezentowanego w programie jako tablica) najmniejszy jego element. Po wyznaczeniu i przesunięciu najmniejszego elementu na początek ciągu, wypisz go.

Specyfikacja problemu:

Dane:

ciag – ciąg liczb całkowitych zapisany w tablicy; tablica liczb całkowitych
n – długość ciągu (rozmiar tablicy); liczba całkowita

Wynik:

najmniejszaLiczba – najmniejsza liczba ciągu; liczba całkowita

RAIgvsiDixtVz1

Przykładowe rozwiązanie zadania:

public class Main {
    public static void main(String[] args) {
        int[] ciąg = {8, 13, 54, 9, 0, 3};
        int n = ciąg.length;
        int najmniejszaLiczba;
        for (int i = 0; i &lt; n - 1; i++) {
            boolean zmieniono = false;
            for (int j = 0; j &lt; n - i - 1; j++) {
                if (ciąg[j] &gt; ciąg[j + 1]) {
                    zmieniono = true;
                    int pomocnicza = ciąg[j];
                    ciąg[j] = ciąg[j + 1];
                    ciąg[j + 1] = pomocnicza;
                }
            }
    
            if (!zmieniono) {
                break;
            }
        }
    
        najmniejszaLiczba = ciąg[0];
        
        System.out.print(najmniejszaLiczba);
    }

}

Ćwiczenie 2

W przedstawionym programie zadeklarowano tablicę liczb całkowitych o nazwie tablica. Uzupełnij program tak, aby posortował zadeklarowaną tablicę w kolejności niemalejącej, a następnie wypisał jej elementy, oddzielając je znakiem spacji.

Specyfikacja problemu:

Dane:

tablica – tablica liczb całkowitych
n – rozmiar tablicy; liczba całkowita

Wynik:

tablica – tablica z posortowanymi niemalejąco liczbami całkowitymi

RiHd4RGMlHh1D1

Przykładowe rozwiązanie zadania:

Linia 1. public class Main otwórz nawias klamrowy. Linia 2. 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 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy tablica znak równości otwórz nawias klamrowy 543 przecinek 65 przecinek 453 przecinek 43 przecinek 12 przecinek 4 przecinek 76 przecinek 8765 przecinek 843 przecinek 546 przecinek 52 przecinek 89 przecinek 73 przecinek 26 przecinek 89 przecinek 94 przecinek 368 przecinek 874 przecinek 78 przecinek 42 przecinek 15 przecinek 78 zamknij nawias klamrowy średnik. Linia 4. int n znak równości tablica kropka length średnik. Linia 5. boolean zmianyDokonane średnik. Linia 6. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny for otwórz nawias okrągły int i znak równości 0 średnik i ampersant lt średnik n minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. zmianyDokonane znak równości false średnik. Linia 8. for otwórz nawias okrągły int j znak równości 0 średnik j ampersant lt średnik n minus i minus 1 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. if otwórz nawias okrągły tablica otwórz nawias kwadratowy j zamknij nawias kwadratowy ampersant gt średnik tablica otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. zmianyDokonane znak równości true średnik. Linia 11. int zmiennaTymczasowa znak równości tablica otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 12. tablica otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości tablica otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy średnik. Linia 13. tablica otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości zmiennaTymczasowa średnik. Linia 14. zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy. Linia 17. if otwórz nawias okrągły wykrzyknik zmianyDokonane zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. break średnik. Linia 19. zamknij nawias klamrowy. Linia 20. zamknij nawias klamrowy. Linia 22. for otwórz nawias okrągły int i znak równości 0 średnik i ampersant lt średnik tablica kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. System kropka out kropka print otwórz nawias okrągły tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 24. zamknij nawias klamrowy. Linia 25. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 27. zamknij nawias klamrowy.

public class Main {
    public static void main(String[] args) {
        int[] tablica = {543, 65, 453, 43, 12, 4, 76, 8765, 843, 546, 52, 89, 73, 26, 89, 94, 368, 874, 78, 42, 15, 78};
        int n = tablica.length;
        boolean zmianyDokonane;
        for (int i = 0; i &lt; n - 1; i++) {
            zmianyDokonane = false;
            for (int j = 0; j &lt; n - i - 1; j++) {
                if (tablica[j] &gt; tablica[j + 1]) {
                    zmianyDokonane = true;
                    int zmiennaTymczasowa = tablica[j];
                    tablica[j] = tablica[j + 1];
                    tablica[j + 1] = zmiennaTymczasowa;
                }
            }
    
            if (!zmianyDokonane) {
                break;
            }
        }
    
        for (int i = 0; i &lt; tablica.length; i++) {
            System.out.print(tablica[i] + " ");
        }
    }

}

Ćwiczenie 3

W pewnej kręgielni zapisywano najlepsze wyniki oraz imiona osób, które je osiągnęły. W celu ogłoszenia rankingu graczy, należy posortować tablicę imion według odpowiadających im wyników (od najwyższego do najniższego). Wykorzystaj sortowanie bąbelkowe z optymalizacją, aby wydrukować listę graczy w kolejności od najlepszego do najsłabszego (nierosnąco względem wyniku, rozpoczynając od gracza z najwyższym wynikiem), oddzielając ich imiona znakiem nowej linii.

Specyfikacja problemu:

Dane:

wyniki – tablica liczb całkowitych
imiona – tablica ciągów znaków
n – rozmiar tablicy (identyczny dla obu tablic); liczba całkowita

Wynik:

imiona – tablica ciągów znaków – imion graczy, posortowana według nierosnących wartości zdobytych przez nich punktów

RAsu5ooFYcbRs1

Przykładowe rozwiązanie zadania:

Linia 1. public class Main otwórz nawias klamrowy. Linia 2. 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 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy wyniki znak równości otwórz nawias klamrowy. Linia 4. 84 przecinek. Linia 5. 102 przecinek. Linia 6. 77 przecinek. Linia 7. 121 przecinek. Linia 8. 111 przecinek. Linia 9. 190 przecinek. Linia 10. 138. Linia 11. zamknij nawias klamrowy średnik. Linia 12. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny String otwórz nawias kwadratowy zamknij nawias kwadratowy imiona znak równości otwórz nawias klamrowy. Linia 13. cudzysłów Aleks cudzysłów przecinek. Linia 14. cudzysłów Bartek cudzysłów przecinek. Linia 15. cudzysłów Czarek cudzysłów przecinek. Linia 16. cudzysłów Darek cudzysłów przecinek. Linia 17. cudzysłów Euzebiusz cudzysłów przecinek. Linia 18. cudzysłów Franek cudzysłów przecinek. Linia 19. cudzysłów Gabriel cudzysłów. Linia 20. zamknij nawias klamrowy średnik. Linia 22. int n znak równości wyniki kropka length średnik. Linia 23. boolean zmianyDokonane średnik. Linia 25. for otwórz nawias okrągły int i znak równości 0 średnik i ampersant lt średnik n minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. zmianyDokonane znak równości false średnik. Linia 27. for otwórz nawias okrągły int j znak równości 1 średnik j ampersant lt średnik n minus i średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. if otwórz nawias okrągły wyniki otwórz nawias kwadratowy j zamknij nawias kwadratowy ampersant gt średnik wyniki otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. zmianyDokonane znak równości true średnik. Linia 31. int wynikTymczasowy znak równości wyniki otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 32. wyniki otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości wyniki otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 33. wyniki otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy znak równości wynikTymczasowy średnik. Linia 35. String imieTymczasowe znak równości imiona otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 36. imiona otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości imiona otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy średnik. Linia 37. imiona otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy znak równości imieTymczasowe średnik. Linia 38. zamknij nawias klamrowy. Linia 39. zamknij nawias klamrowy. Linia 41. if otwórz nawias okrągły wykrzyknik zmianyDokonane zamknij nawias okrągły otwórz nawias klamrowy. Linia 42. break średnik. Linia 43. zamknij nawias klamrowy. Linia 44. zamknij nawias klamrowy. Linia 46. for otwórz nawias okrągły int i znak równości 0 średnik i ampersant lt średnik n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 47. System kropka out kropka println otwórz nawias okrągły imiona otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 48. zamknij nawias klamrowy. Linia 49. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 51. zamknij nawias klamrowy.

public class Main {
    public static void main(String[] args) {
        int[] wyniki = {
                84,
                102,
                77,
                121,
                111,
                190,
                138
        };
        String[] imiona = {
                "Aleks",
                "Bartek",
                "Czarek",
                "Darek",
                "Euzebiusz",
                "Franek",
                "Gabriel"
        };
    
        int n = wyniki.length;
        boolean zmianyDokonane;
    
        for (int i = 0; i &lt; n - 1; i++) {
            zmianyDokonane = false;
            for (int j = 1; j &lt; n - i; j++) {
                if (wyniki[j] &gt; wyniki[j - 1]) {
                    zmianyDokonane = true;
    
                    int wynikTymczasowy = wyniki[j];
                    wyniki[j] = wyniki[j - 1];
                    wyniki[j - 1] = wynikTymczasowy;
    
                    String imieTymczasowe = imiona[j];
                    imiona[j] = imiona[j - 1];
                    imiona[j - 1] = imieTymczasowe;
                }
            }
    
            if (!zmianyDokonane) {
                break;
            }
        }
    
        for (int i = 0; i &lt; n; i++) {
            System.out.println(imiona[i]);
        }
    }

}

Misja druga: Ćwicz i zwyciężaj

I_P_W14_M12_Java Sortowanie metodą bąbelkową