Bubble Rendezési algoritmus Java: Tömbrendező program és példa

Mi a Bubble Rendezés?

BubblAz e Sort egy egyszerű összehasonlításon alapuló rendezési algoritmus, amely a tömb első elemét összehasonlítja a következővel. Ha a tömb aktuális eleme számszerűen nagyobb, mint a következő, akkor az elemek felcserélődnek. Hasonlóképpen, az algoritmus a tömb teljes elemét bejárja.

Az algoritmus a nevét onnan kapta, ahogyan a rendezetlen régióban lévő legnagyobb érték folyamatosan emelkedik a végső pozíciójába, hasonlóan ahhoz, ahogy egy buborék a víz felszínére emelkedik. Az első teljes menet után a legnagyobb elem foglalja el az utolsó indexet. A második menet után a második legnagyobb elem rögzül a helyén, és a folyamat addig ismétlődik, amíg a tömb teljesen rendezett nem lesz.

Ebben a cikkben létrehozunk egy Java program megvalósításához BubblRendezés. Ellenőrizd a kód kimenetét, amely segít megérteni a program logikáját, majd tekintsd át az optimalizált verziót és az azt követő bonyolultsági elemzést.

Hogyan működik a BubblRendező algoritmus működik?

BubblAz e Rendezés ismételt menetekkel működik a tömbön. Minden menet az első indextől a jelenleg rendezetlen régió végéig halad, összehasonlítja a szomszédos értékeket, és felcseréli azokat.ping őket, valahányszor rossz sorrendben jelennek meg. Mivel a legnagyobb megmaradt érték mindig a rendezetlen régió jobb szélére kerül, a régió minden egyes áthaladás után pontosan egy pozícióval zsugorodik.

A teljes folyamat négy ismétlődő lépésre bontható:

1. Összehasonlítás: Vizsgáld meg a j-1 indexű elemet a j indexű elemmel szemben.
2. Csere: Ha a bal oldali elem nagyobb, mint a jobb oldali elem, akkor cserélje fel a két értéket egy ideiglenes változó segítségével.
3. Előleg: Lépjen egy pozícióval jobbra, és ismételje meg a műveletet, amíg el nem éri a rendezetlen régió végét.
4. Ismétlés: Új menetet kezdünk egy eggyel rövidebb régión, és n-1 menet után, vagy ha a menet nem hajt végre cserét, állunk meg.

Az alábbi táblázat traca programban később ezen az oldalon használt {860, 8, 200, 9} minta tömböt mutatja. Ez pontosan megmutatja, hogy melyik érték stabilizálódik a végső pozíciójában minden menet végén.

Figyeljük meg, hogy a harmadik menet összehasonlítást hajt végre, de cserét nem. Egy optimalizált implementáció észleli ezt a feltételt, és azonnal leáll, ami az algoritmuson alkalmazható legértékesebb fejlesztés.

BubblRendezési algoritmus pszeudokód

Írás előtt Java szintaxisban segít a logika nyelvsemleges pszeudokódban való kifejezésében. Az alábbi verzió tartalmazza a korai kilépési jelzőt, így mind a klasszikus, mind az optimalizált viselkedést lefedi.

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

A külső ciklus a menetek számát, a belső ciklus pedig az egyetlen meneten belüli összehasonlításokat vezérli. A belső ciklus felső korlátja n – i – 1, mivel az utolsó i pozíció már tartalmazza a végső értékét.

Java Megvalósítandó program Bubble Rendezés

A következő program egy egész tömböt növekvő sorrendbe rendez. A ciklusokban szándékosan extra kiírási utasításokat tartottunk, mivel az áthaladás-áthaladás olvasása tracAz e a leggyorsabb módja annak, hogy egy kezdő megértse, hogyan halmozódnak fel a swapok.

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

    }
}

output:

---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 magyarázat: Az buborékrendezés A metódus hivatkozásként kapja meg a tömböt, így a hívó a rendezett eredményt visszatérési érték nélkül látja. temp egy értéket tart meg a háromsoros csere során, ezért az algoritmusnak csak O(1) extra memóriára van szüksége. A kifejezés n – i a belső ciklus feltétele garantálja, hogy a farok már rendezett pozícióit soha többé nem kell újra megnézni.

optimalizált Bubble Program rendezése Java

A fenti program mindig n-1 menetet hajt végre, még akkor is, ha a tömb korán rendezetté válik. Egyetlen logikai jelző hozzáadása megoldja ezt a hatékonysági problémát. Ha egy teljes menet egyetlen csere nélkül fejeződik be, a tömb garantáltan rendezett lesz, és a külső ciklus azonnal leállhat.

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

output:

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

A bemeneti tömb már rendezett volt, így az optimalizált verzió egyetlen menet után befejeződött négy helyett. Majdnem rendezett adatokon ez a változás a kvadratikus munkaterhelést majdnem lineárissá alakítja, ami a fő oka annak, hogy BubblAz e Sort időről időre még mindig megjelenik a valódi kódban.

Időbeli és térbeli komplexitás Bubble Rendezés

A komplexitás leírja, hogyan növekszik a futási idő a bemeneti méret növekedésével. BubblA rendezetlen változatban az összehasonlítások száma n(n-1)/2-re van rögzítve, ami határozottan a kvadratikus osztályba sorolja azt.

Mivel minden csere az eredeti tömbön belül történik, és csak egy ideiglenes változót használunk, BubblAz e Sort egy helybeni algoritmus O(1) segédtárhellyel. Stabil rendezés is, ami azt jelenti, hogy két, azonos kulccsal rendelkező rekord megőrzi eredeti relatív sorrendjét a rendezés után.

Előnyei és hátrányai Bubble Rendezés

Mindkét oldal megértése segít eldönteni, hogy mikor elfogadható az algoritmus, és mikor kell lecserélni.

Előnyök

• Egyszerűség: A logika nagyjából tíz sorban elfér, ami megkönnyíti a helyes írást interjúkörülmények között.
• Helyszíni működés: Nincs lefoglalva segédtömb, így a memóriahasználat nem növekszik a bemeneti mérettel.
• Stabilitás: Az egyenlő kulcsok megtartják eredeti sorrendjüket, ami fontos a rekordok másodlagos mező szerinti rendezésekor.
• Korai kilépésészlelés: A felcserélt jelző egyetlen menetben már rendezett tömböt azonosít.

Hátrányok

• Négyzetes növekedés: 10 000 elem rendezése a legrosszabb esetben is közel 50 millió összehasonlítást igényel.
• Túlzott írások: Az algoritmus sokkal több cserét hajt végre, mint a Kijelöléses rendezés, ami költséges a memóriahasználattal és lassú írási műveletekkel.
• Gyenge skálázhatóság: Az éles munkaterhelések szinte mindig a Quicksort, az Merge Sort vagy a beépített Arrays.sort metódust részesítik előnyben.

Bubble Rendezés vs. Egyéb Rendezés Algorithms

Az alábbi táblázat összehasonlítja BubblRendezd a kezdők által következő rendezési technikákkal, így pontosan láthatod, hogy melyik hol nyer.

BubblA rendezés és a beszúró rendezés ugyanazt a lineáris legjobb esetet használja, de a beszúró rendezés kevesebb cserét hajt végre részben rendezett adatokon. A szelekciós rendezés mindig pontosan n-1 cserét hajt végre, ami azt jelenti, hogytracaktív, ha az írás költséges, bár ez a stabilitást feláldozza. Néhány száz elemnél nagyobb tömbök esetén a Quicksort vagy a Heap Sort a helyes választás.

Miután már ismeri az itt használt tömbbejárási mintákat, ugyanez a ciklusstruktúra számos klasszikus gyakorlatban is megjelenik, például a Fibonacci-sorozat Java és a Java palindrom program. Reviwing Java tömbök és szélesebb Java oktatói megerősíti azokat az alapokat, amelyekre ez az algoritmus épül.

GYIK