Bubble Sortera algoritm i Java: Array Sortering Program & Exempel

Vad är Bubble sortera?

Bubble Sort är en enkel jämförelsebaserad sorteringsalgoritm som jämför det första elementet i arrayen med nästa. Om det aktuella elementet i arrayen är numeriskt större än nästa, byts elementen ut. På samma sätt kommer algoritmen att gå igenom hela elementet i arrayen.

Algoritmen har fått sitt namn från hur det största värdet i det osorterade området stadigt stiger till sin slutliga position, ungefär som en bubbla som stiger till vattenytan. Efter den första fullständiga passagen upptar det största elementet det sista indexet. Efter den andra passagen låses det näst största elementet på plats, och processen upprepas tills matrisen är helt ordnad.

I den här artikeln ska vi skapa en Java program för att genomföra Bubble Sortera. Kontrollera utdata från koden som hjälper dig att förstå programlogiken och granska sedan den optimerade versionen och komplexitetsanalysen som följer.

Hur gör det BubblFungerar sorteringsalgoritmen e?

Bubble Sort fungerar genom upprepade processer över arrayen. Varje processering går från det första indexet till slutet av den för närvarande osorterade regionen, jämför angränsande värden och byter plats.ping dem när de visas i fel ordning. Eftersom det största återstående värdet alltid flyttas längst till höger i den osorterade regionen krymper regionen med exakt en position efter varje pass.

Hela processen kan delas upp i fyra repeterbara steg:

1. Jämföra: Jämför elementet vid index j-1 med elementet vid index j.
2. Swap: Om det vänstra elementet är större än det högra elementet, byt ut de två värdena med en temporär variabel.
3. Förskott: Flytta en position åt höger och upprepa tills slutet av det osorterade området är nått.
4. Upprepa: Börja en ny passning över en region som är ett element kortare och stoppa efter n-1 passningar eller när en passning inte utför några byten.

Tabellen nedan tracvisar exempelmatrisen {860, 8, 200, 9} som används i programmet senare på den här sidan. Den visar exakt vilket värde som återställs till sin slutliga position i slutet av varje omgång.

Observera att det tredje passet utför en jämförelse men ingen växling. En optimerad implementering detekterar det villkoret och stoppar omedelbart, vilket är den enskilt mest värdefulla förbättringen du kan tillämpa på den här algoritmen.

Bubble Sorteringsalgoritm Pseudokod

Innan du skriver Java syntax, det hjälper till att uttrycka logiken i språkneutral pseudokod. Versionen nedan inkluderar flaggan för tidig utgång, så den täcker både det klassiska och det optimerade beteendet.

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 yttre loopen styr antalet passager, och den inre loopen styr jämförelserna inom ett enda passeringspass. Den övre gränsen för den inre loopen är n – i – 1 eftersom de sista i-positionerna redan har sina slutliga värden.

Java Program att implementera Bubble Sortera

Följande program sorterar en heltalsmatris i stigande ordning. Extra print-satser har avsiktligt hållits inuti looparna, eftersom läsning av pass-by-pass trace är det snabbaste sättet för en nybörjare att förstå hur swapparna ackumuleras.

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();

    }
}

Produktion:

---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 förklaring: Ocuco-landskapet bubbleSort Metoden tar emot arrayen via referens, så anroparen ser det sorterade resultatet utan något returvärde. Variabeln temp håller ett värde under treradsbytet, vilket är anledningen till att algoritmen bara behöver O(1) extra minne. Uttrycket n – i i det inre loopvillkoret garanterar att redan sorterade positioner vid svansen aldrig återbesöks.

optimerad Bubble Sortera in programmet Java

Programmet ovan utför alltid n-1 genomgångar, även när arrayen sorteras tidigt. Att lägga till en enda boolesk flagga åtgärdar den ineffektiviteten. Om ett komplett genomgång avslutas utan ett enda byte garanteras att arrayen sorteras och den yttre loopen kan stoppas omedelbart.

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);
    }
}

Produktion:

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

Inmatningsmatrisen var redan sorterad, så den optimerade versionen slutfördes efter ett enda pass istället för fyra. På nästan sorterade data förvandlar denna ändring en kvadratisk arbetsbelastning till en nästan linjär, vilket är den främsta anledningen. Bubble Sort förekommer fortfarande i riktig kod då och då.

Tidskomplexitet och rumskomplexitet hos Bubble Sortera

Komplexitet beskriver hur körtiden växer i takt med att inmatningsstorleken växer. Bubble Sortera antalet jämförelser i den ooptimerade versionen är fixerat till n(n-1)/2, vilket placerar den stadigt i den kvadratiska klassen.

Eftersom varje utbyte sker inuti den ursprungliga arrayen och endast en temporär variabel används, Bubble Sort är en in-place-algoritm med O(1) hjälputrymme. Det är också en stabil sortering, vilket innebär att två poster som innehåller samma nyckel behåller sin ursprungliga relativa ordning efter sortering.

Fördelar och nackdelar med Bubble Sortera

Att förstå båda sidor hjälper dig att avgöra när algoritmen är ett acceptabelt val och när den bör ersättas.

Fördelar

• Enkelhet: Logiken ryms på ungefär tio rader, vilket gör det enkelt att skriva korrekt under intervjuförhållanden.
• Drift på plats: Ingen hjälpmatris allokeras, så minnesanvändningen växer inte med inmatningsstorleken.
• Stabilitet: Lika nycklar behåller sin ursprungliga ordning, vilket är viktigt när man sorterar poster efter ett sekundärt fält.
• Tidig upptäckt av utgång: Den utbytta flaggan identifierar en redan sorterad array i ett enda pass.

Nackdelar

• Kvadratisk tillväxt: Att sortera 10 000 element kräver i värsta fall nästan 50 miljoner jämförelser.
• Överdrivet skriver: Algoritmen utför betydligt fler byten än Selection Sort, vilket är kostsamt för minne med långsamma skrivoperationer.
• Dålig skalbarhet: Produktionsarbetsbelastningar föredrar nästan alltid Quicksort, Merge Sort eller den inbyggda metoden Arrays.sort.

Bubble-sortering kontra annan sortering Algorithms

Tabellen nedan jämför Bubble Sortera med de sorteringstekniker som nybörjare möter härnäst, så att du kan se exakt var varje teknik vinner.

Bubble Sort och Insertion Sort delar samma linjära bästa fall, men Insertion Sort utför färre växlingar på delvis sorterad data. Urvalssort utför alltid exakt n-1 växlingar, vilket gör det vidtraceffektiv när skrivningar är dyra, även om det offrar stabiliteten. För alla arrayer större än några hundra element är Quicksort eller Heap Sort det rätta valet.

När du väl är bekväm med array-traverseringsmönster som används här, visas samma loopstruktur i många klassiska övningar som Fibonacci-serien i Java och Java palindromprogram. Reviewing Java arrayer och desto bredare Java handledning kommer att stärka de grunder som denna algoritm är beroende av.

Vanliga frågor