Bubble Sorter algoritme i Java: Matrisesorteringsprogram og eksempel

Hva er Bubble sortere?

Bubble Sort er en enkel sammenligningsbasert sorteringsalgoritme som sammenligner det første elementet i matrisen med det neste. Hvis det gjeldende elementet i matrisen er numerisk større enn det neste, byttes elementene om. På samme måte vil algoritmen gå gjennom hele elementet i matrisen.

Algoritmen har fått navnet sitt fra måten den største verdien i det usorterte området jevnt stiger til sin endelige posisjon, omtrent som en boble som stiger til vannoverflaten. Etter den første fullstendige gjennomgangen opptar det største elementet den siste indeksen. Etter den andre gjennomgangen låses det nest største elementet på plass, og prosessen gjentas til matrisen er fullstendig ordnet.

I denne artikkelen skal vi lage en Java program for å implementere Bubble Sorter. Sjekk utdataene fra koden som vil hjelpe deg å forstå programlogikken, og se deretter gjennom den optimaliserte versjonen og kompleksitetsanalysen som følger.

Hvordan gjør BubblFungerer e-sorteringsalgoritmen?

Bubble Sort fungerer gjennom gjentatte passeringer over matrisen. Hver passering går fra den første indeksen til slutten av det for øyeblikket usorterte området, sammenligner nærliggende verdier og bytter.ping dem når de vises i feil rekkefølge. Fordi den største gjenværende verdien alltid beveger seg helt til høyre i det usorterte området, krymper området med nøyaktig én posisjon etter hver passering.

Hele prosessen kan deles inn i fire repeterbare trinn:

1. Sammenligne: Undersøk elementet ved indeks j-1 mot elementet ved indeks j.
2. Swap: Hvis det venstre elementet er større enn det høyre elementet, bytt ut de to verdiene ved hjelp av en midlertidig variabel.
3. Avansere: Flytt én posisjon til høyre og gjenta til slutten av det usorterte området er nådd.
4. Gjenta: Start en ny passasje over et område som er ett element kortere, og stopp etter n-1 passasje eller når en passasje ikke utfører noen bytter.

Tabellen nedenfor tracviser eksempelmatrisen {860, 8, 200, 9} som brukes i programmet senere på denne siden. Den viser nøyaktig hvilken verdi som setter seg i sin endelige posisjon på slutten av hver omgang.

Legg merke til at den tredje omgangen utfører en sammenligning, men ingen bytte. En optimalisert implementering oppdager denne tilstanden og stopper umiddelbart, noe som er den mest verdifulle forbedringen du kan bruke på denne algoritmen.

Bubble Sorteringsalgoritme pseudokode

Før du skriver Java syntaks, det bidrar til å uttrykke logikken i språknøytral pseudokode. Versjonen nedenfor inkluderer flagget for tidlig exit, slik at den dekker både den klassiske og den optimaliserte oppførselen.

procedure bubbleSort(array A, integer n)
    for i from 0 to n - 2 do
        swapped := false
        for j from 1 to n - i - 1 do
            // compare the adjacent pair
            if A[j - 1] > A[j] then
                swap A[j - 1] and A[j]
                swapped := true
            end if
        end for
        // no swap in a full pass means the array is sorted
        if swapped = false then
            break
        end if
    end for
end procedure

Den ytre løkken styrer antall passeringer, og den indre løkken styrer sammenligningene innenfor en enkelt passering. Den øvre grensen for den indre løkken er n – i – 1 fordi de siste i-posisjonene allerede har sine endelige verdier.

Java Program for implementering Bubble Sorter

Følgende program sorterer en heltallsmatrise i stigende rekkefølge. Ekstra print-setninger er med vilje holdt inne i løkkene, fordi lesing av pass-by-pass trace er den raskeste måten for en nybegynner å forstå hvordan swappene akkumuleres.

package com.guru99;

public class BubbleSort {

    public static void main(String[] args)
    {
        int arr[] = {860, 8, 200, 9};

        System.out.println("---Array BEFORE Bubble Sort---");

        printArray(arr);

        bubbleSort(arr); //sorting array elements using bubble sort

        System.out.println("---Array AFTER Bubble Sort---");

        printArray(arr);

    }

    static void bubbleSort(int[] array)
    {
        int n = array.length;
        int temp = 0;
        for(int i = 0; i < n; i++) // Looping through the array length
        {   System.out.println("Sort Pass Number " + (i + 1));
            for(int j = 1; j < (n - i); j++)
            {
                System.out.println("Comparing " + array[j - 1] + " and " + array[j]);
                if(array[j - 1] > array[j])
                {
                    //swap elements
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    System.out.println(array[j] + " is greater than " + array[j - 1]);
                    System.out.println("Swapping Elements: New Array After Swap");
                    printArray(array);
                }

            }
        }

    }

    static void printArray(int[] array){

        for(int i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + " ");
        }
        System.out.println();

    }
}

Utgang:

---Array BEFORE Bubble Sort---
860 8 200 9
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Swapping Elements: New Array After Swap
8 860 200 9
Comparing 860 and 200
860 is greater than 200
Swapping Elements: New Array After Swap
8 200 860 9
Comparing 860 and 9
860 is greater than 9
Swapping Elements: New Array After Swap
8 200 9 860
Sort Pass Number 2
Comparing 8 and 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860
Sort Pass Number 3
Comparing 8 and 9
Sort Pass Number 4
---Array AFTER Bubble Sort---
8 9 200 860

Code forklaring: Ocuco boblesortering Metoden mottar arrayet via referanse, slik at kalleren ser det sorterte resultatet uten noen returverdi. Variabelen temp holder én verdi under trelinjebyttet, og det er derfor algoritmen bare trenger O(1) ekstra minne. Uttrykket n – i i den indre løkkebetingelsen garanterer at allerede sorterte posisjoner ved halen aldri blir besøkt på nytt.

Optimalisert Bubble Sorter programmet inn Java

Programmet ovenfor utfører alltid n-1 passeringer, selv når arrayet blir sortert tidlig. Å legge til et enkelt boolsk flagg fikser denne ineffektiviteten. Hvis en fullstendig passering fullføres uten en eneste bytte, er det garantert at arrayet blir sortert, og den ytre løkken kan stoppe umiddelbart.

package com.guru99;

public class OptimizedBubbleSort {

    public static void main(String[] args) {
        int arr[] = {5, 12, 33, 47, 58};
        bubbleSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }

    static void bubbleSort(int[] array) {
        int n = array.length;
        int passes = 0;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 1; j < n - i; j++) {
                if (array[j - 1] > array[j]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    swapped = true;
                }
            }
            passes++;
            // Early exit: the array is already sorted
            if (!swapped) {
                break;
            }
        }
        System.out.println("Passes executed: " + passes);
    }
}

Utgang:

Passes executed: 1
[5, 12, 33, 47, 58]

Inndataarrayet var allerede sortert, så den optimaliserte versjonen ble ferdig etter én omgang i stedet for fire. På nesten sorterte data gjør denne endringen en kvadratisk arbeidsmengde til en nesten lineær, noe som er hovedårsaken. Bubble Sort dukker fortsatt opp i ekte kode fra tid til annen.

Tidskompleksitet og romkompleksitet av Bubble Sorter

Kompleksitet beskriver hvordan kjøretiden øker etter hvert som inndatastørrelsen øker. Bubble Sort-antall sammenligninger i den uoptimaliserte versjonen er fastsatt til n(n-1)/2, noe som plasserer den solidt i den kvadratiske klassen.

Fordi hver utveksling skjer inne i den opprinnelige tabellen, og bare én midlertidig variabel brukes, Bubble Sort er en in-place-algoritme med O(1) hjelperom. Det er også en stabil sortering, som betyr at to poster som har samme nøkkel beholder sin opprinnelige relative rekkefølge etter sortering.

Fordeler og ulemper ved Bubble Sorter

Å forstå begge sider hjelper deg med å avgjøre når algoritmen er et akseptabelt valg og når den bør erstattes.

Fordeler

• Enkelhet: Logikken passer på omtrent ti linjer, noe som gjør det enkelt å skrive riktig under intervjuforhold.
• Drift på stedet: Ingen hjelpematrise er tildelt, så minnebruken vokser ikke med inndatastørrelsen.
• Stabilitet: Like nøkler beholder sin opprinnelige rekkefølge, noe som er viktig når man sorterer poster etter et sekundært felt.
• Tidlig utgangsdeteksjon: Det byttede flagget identifiserer en allerede sortert matrise i én omgang.

Ulemper

• Kvadratisk vekst: Å sortere 10 000 elementer krever i verste fall nesten 50 millioner sammenligninger.
• Overdreven skriving: Algoritmen utfører langt flere bytter enn Selection Sort, som er kostbart for minne med langsomme skriveoperasjoner.
• Dårlig skalerbarhet: Produksjonsarbeidsbelastninger favoriserer nesten alltid Quicksort, Merge Sort eller den innebygde Arrays.sort-metoden.

Bubble-sortering vs. annen sortering Algorithms

Tabellen nedenfor sammenligner Bubble Sorter med sorteringsteknikkene som nybegynnere møter neste gang, slik at du kan se nøyaktig hvor hver enkelt vinner.

Bubble Sortering og innsettingssortering deler samme lineære beste tilfelle, men innsettingssortering utfører færre bytter på delvis sorterte data. Utvalgssortering utfører alltid nøyaktig n-1 bytter, noe som gjør det minsttraceffektiv når skriving er dyrt, selv om det går på bekostning av stabilitet. For enhver matrise større enn noen få hundre elementer er Quicksort eller Heap Sort det riktige valget.

Når du er komfortabel med array-traverseringsmønstrene som brukes her, vises den samme løkkestrukturen i mange klassiske øvelser som Fibonacci-serien i Java og Java palindromprogram. Revser Java arrays og bredere Java tutorial vil styrke de grunnleggende elementene denne algoritmen er avhengig av.

Spørsmål og svar