Strefa wyzwań - I_P_R_W14_M13_Java Sortowanie przez wstawianie

R15YEsGC1T9gc

Już wiesz

Jak działa metoda sortowania przez wstawianie.
Jak działa algorytm sortowania przez wstawianie dla konkretnego przykładu.
Jaka jest złożoność obliczeniowa algorytmu sortowania przez wstawianie.
Ile porównań wykonywanych jest w przypadku pesymistycznym, a ile w optymistycznym.

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

Ćwiczenie 1

Uzupełnij algorytm sortowania przez wstawianie, tak aby poprawnie sortował ciąg liczb całkowitych podanych w tablicy zawartej w programie w kolejności niemalejącej. Wypisz posortowaną tablicę, oddzielając jej elementy znakiem spacji.

Swoje rozwiązanie przetestuj na tablicy tab = {27, 26, 4, 5, 24, 23, 15, 12, 1, 0, 9, 84}.

Specyfikacja problemu:

Dane:

n – liczba naturalna
tab – tablica n liczb całkowitych

Wynik:

tab – posortowana niemalejąco tablica n liczb całkowitych

RCgx4MWgjwJYm

public class Main {

    public static void main(String[] args) {

        int[] tab = {27, 26, 4, 5, 24, 23, 15, 12, 1, 0, 9, 84};
        int n = tab.length;
        int a;
        int j;

        for (int i = 1; i < n; i++) {
            a = tab[i];
            j = i - 1;

            while (j >= 0 && tab[j] > a) {
                tab[j + 1] = tab[j];
                j--;
            }
            tab[j + 1] = a;
        }

        for (int i = 0; i < n; i++) 
            System.out.print(tab[i] + " ");
    }
}

Ćwiczenie 2

Pewien przedsiębiorca postanowił udostępnić usługę sortowania przez wstawianie na zasadzie komercyjnej. Cenę za posortowanie tablicy rosnąco ustalił w następujący sposób: jest to suma połowy liczby porównań elementów tablicy (kontrola granic tablicy nie jest liczona do porównań) i opłaty stałej 2,50 zł. Napisz program, który wypisze na standardowe wejście cenę posortowania podanej tablicy.

Uzupełnij poniższy algorytm sortowania przez wstawianie, aby sortował rosnąco tablicę n-elementową wypełnioną liczbami całkowitymi. Swoje rozwiązanie przetestuj na tablicy dane = {14, 32, 35, 45, 12, 8, 17, 9}.

Przykład 1

Dla tablicy, w której znajdują się liczby 14, 32, 35, 7 program wykona 5 porównań elementów tablicy.

Specyfikacja problemu:

Dane:

n – liczba naturalna
dane – tablica n liczb całkowitych

Wynik:

cena – liczba całkowita

ReuJgFl2Fw81E

Linia 1. public class Main otwórz nawias klamrowy. Linia 3. static void sortowaniePrzezWstawianie otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy dane zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. int licznikPorownan znak równości 0 średnik. Linia 5. int n znak równości dane kropka length średnik. Linia 7. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. int element znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 9. int j znak równości i minus 1 średnik. Linia 11. while otwórz nawias okrągły j zamknij nawias ostrokątny znak równości 0 ampersant ampersant dane otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias ostrokątny element zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. dane otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 13. j minus minus średnik. Linia 14. licznikPorownan plus plus średnik. Linia 15. zamknij nawias klamrowy. Linia 17. dane otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości element średnik. Linia 18. zamknij nawias klamrowy. Linia 20. double cena znak równości licznikPorownan asterysk 0 kropka 5 plus 2 kropka 5 średnik. Linia 22. System kropka out kropka println otwórz nawias okrągły cena zamknij nawias okrągły średnik. Linia 23. zamknij nawias klamrowy. Linia 25. 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 26. int otwórz nawias kwadratowy zamknij nawias kwadratowy dane znak równości otwórz nawias klamrowy 14 przecinek 32 przecinek 35 przecinek 45 przecinek 12 przecinek 8 przecinek 17 przecinek 9 zamknij nawias klamrowy średnik. Linia 28. sortowaniePrzezWstawianie otwórz nawias okrągły dane zamknij nawias okrągły średnik. Linia 29. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy.

public class Main {

    static void sortowaniePrzezWstawianie(int[] dane) {
        int licznikPorownan = 0;
        int n = dane.length;

        for (int i = 1; i < n; i++) {
            int element = dane[i];
            int j = i - 1;

            while (j >= 0 && dane[j] > element) {
                dane[j + 1] = dane[j];
                j--;
                licznikPorownan++;
            }

            dane[j + 1] = element;
        }

        double cena = licznikPorownan * 0.5 + 2.5;

        System.out.println(cena);
    }

    public static void main(String[] args) {
        int[] dane = {14, 32, 35, 45, 12, 8, 17, 9};

        sortowaniePrzezWstawianie(dane);
    }
}

Misja druga: Ćwicz i zwyciężaj

I_P_R_W14_M13_Java Sortowanie przez wstawianie