Bubble Lajittele algoritmi Java: Taulukon lajitteluohjelma ja esimerkki

Mikä on Bubble Lajittele?

Bubble Sort on yksinkertainen vertailuun perustuva lajittelualgoritmi, joka vertaa taulukon ensimmäistä alkiota seuraavaan. Jos taulukon nykyinen alkio on numeerisesti suurempi kuin seuraava, alkiot vaihdetaan. Samoin algoritmi käy läpi koko taulukon alkion.

Algoritmi on saanut nimensä siitä, miten lajittelemattoman alueen suurin arvo nousee tasaisesti lopulliseen sijaintiinsa, aivan kuten kupla nousee veden pintaan. Ensimmäisen täydellisen läpimenon jälkeen suurin elementti täyttää viimeisen indeksin. Toisen läpimenon jälkeen toiseksi suurin elementti lukitaan paikalleen, ja prosessi toistuu, kunnes taulukko on täysin järjestetty.

Tässä artikkelissa luomme Java ohjelma toteuttaa Bubble Lajittele. Tarkista koodin tuloste, joka auttaa sinua ymmärtämään ohjelman logiikkaa, ja tarkastele sitten optimoitua versiota ja sitä seuraavaa monimutkaisuusanalyysia.

Miten BubblToimiiko lajittelualgoritmi?

BubblLajittelu toimii toistuvien läpikäyntien avulla taulukon läpi. Jokainen läpikäynti kulkee ensimmäisestä indeksistä parhaillaan lajittelemattoman alueen loppuun, vertaa vierekkäisiä arvoja ja vaihtaaping ne aina, kun ne esiintyvät väärässä järjestyksessä. Koska suurin jäljellä oleva arvo siirtyy aina lajittelemattoman alueen oikeaan reunaan, alue kutistuu täsmälleen yhden pykälän jokaisen kierroksen jälkeen.

Koko prosessi voidaan jakaa neljään toistettavaan vaiheeseen:

1. Vertailla: Vertaile indeksin j-1 alkiota indeksin j alkioon verrattuna.
2. Vaihtaa: Jos vasen elementti on suurempi kuin oikea elementti, vaihda kahden arvon arvot käyttämällä väliaikaista muuttujaa.
3. Advance: Siirrä yksi sijainti oikealle ja toista, kunnes lajittelemattoman alueen loppu on saavutettu.
4. Toistaa: Aloita uusi suoritus yhden elementin lyhyemmästä alueesta ja lopeta n-1 suorituksen jälkeen tai kun suoritus ei suorita vaihtoja.

Alla oleva taulukko tracon esimerkkitaulukko {860, 8, 200, 9}, jota käytetään ohjelmassa myöhemmin tällä sivulla. Se näyttää tarkalleen, mikä arvo asettuu lopulliseen asemaansa jokaisen läpimenon lopussa.

Huomaa, että kolmannella kierroksella suoritetaan vertailu, mutta ei vaihtoa. Optimoitu toteutus havaitsee tämän ehdon ja pysähtyy välittömästi, mikä on arvokkain yksittäinen parannus, jonka voit soveltaa tähän algoritmiin.

Bubble Lajittelualgoritmi Pseudokoodi

Ennen kirjoittamista Java syntaksin osalta se auttaa ilmaisemaan logiikan kielineutraalilla pseudokoodilla. Alla oleva versio sisältää varhaisen poistumisen lipun, joten se kattaa sekä klassisen että optimoidun toiminnan.

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

Ulompi silmukka kontrolloi läpimenojen määrää ja sisempi silmukka kontrolloi yhden läpimenon sisällä tapahtuvia vertailuja. Sisemmän silmukan yläraja on n – i – 1, koska viimeiset i paikkaa pitävät jo lopulliset arvonsa hallussaan.

Java Toteutettava ohjelma Bubble Lajittele

Seuraava ohjelma lajittelee kokonaislukutaulukon nousevaan järjestykseen. Ylimääräiset tulostuslausekkeet on jätetty silmukoiden sisään tarkoituksella, koska pass-by-pass-lausekkeiden lukeminen trace on nopein tapa aloittelijalle ymmärtää, miten swapit kertyvät.

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

    }
}

lähtö:

---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 selitys: kuplalajittelu metodi vastaanottaa taulukon viitteenä, joten kutsuja näkee lajitellun tuloksen ilman paluuarvoa. temp säilyttää yhden arvon kolmen rivinvaihdon aikana, minkä vuoksi algoritmi tarvitsee vain O(1) lisämuistia. Lauseke n – i sisemmässä silmukassa ehto takaa, että jo lajiteltuja sijainteja häntässä ei koskaan palata.

optimoitu Bubble Lajittele ohjelma Java

Yllä oleva ohjelma suorittaa aina n-1 läpimenoa, vaikka taulukko lajiteltaisiin aikaisin. Yhden totuusarvon lipun lisääminen korjaa tämän tehottomuuden. Jos täydellinen läpimeno päättyy ilman yhtäkään vaihtoa, taulukon lajittelu on taattua ja ulompi silmukka voi pysähtyä välittömästi.

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

lähtö:

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

Syötetaulukko oli jo lajiteltu, joten optimoitu versio valmistui yhden käsittelykerran jälkeen neljän sijaan. Lähes lajitellulla datalla tämä muutos muuttaa neliöllisen työmäärän lähes lineaariseksi, mikä on pääsyy Bubble Sort esiintyy edelleen ajoittain oikeassa koodissa.

Aikakompleksisuus ja tilakompleksisuus Bubble Lajittele

Kompleksisuus kuvaa, miten suoritusaika kasvaa syötteen koon kasvaessa. BubblLajittele optimoimattomassa versiossa vertailujen lukumääräksi on kiinteä n(n-1)/2, mikä sijoittaa sen vahvasti toisen asteen luokkaan.

Koska jokainen vaihto tapahtuu alkuperäisen taulukon sisällä ja käytetään vain yhtä väliaikaista muuttujaa, Bubble Sort on paikallinen algoritmi, jossa on O(1) aputilaa. Se on myös stabiili lajittelu, mikä tarkoittaa, että kaksi samaa avainta sisältävää tietuetta säilyttävät alkuperäisen suhteellisen järjestyksensä lajittelun jälkeen.

Edut ja haitat Bubble Lajittele

Molempien puolien ymmärtäminen auttaa sinua päättämään, milloin algoritmi on hyväksyttävä valinta ja milloin se tulisi korvata.

edut

• Yksinkertaisuus: Logiikka mahtuu noin kymmenelle riville, mikä helpottaa kirjoittamista oikein haastatteluolosuhteissa.
• Paikan päällä tapahtuva toiminta: Apumatriisia ei ole allokoitu, joten muistin käyttö ei kasva syötteen koon mukana.
• vakaus: Yhtäsuuruiset avaimet säilyttävät alkuperäisen järjestyksensä, millä on merkitystä lajiteltaessa tietueita toissijaisen kentän mukaan.
• Varhainen poistumisen havaitseminen: Vaihdettu lippu tunnistaa jo lajitellun taulukon yhdellä kertaa.

Haitat

• Neliöllinen kasvu: 10 000 elementin lajittelu vaatii pahimmassa tapauksessa lähes 50 miljoonaa vertailua.
• Ylimääräinen kirjoittaa: Algoritmi suorittaa paljon enemmän vaihtoja kuin valintalajittelu, joka on muistia kuluttavaa hitaiden kirjoitustoimintojen vuoksi.
• Huono skaalautuvuus: Tuotantotyökuormat suosivat lähes aina Quicksort-, Merge Sort- tai sisäänrakennettua Arrays.sort-metodia.

Bubble-lajittelu vs. muu lajittelu Algorithms

Alla oleva taulukko vertaa BubblLajittele aloittelijoiden seuraavaksi kohtaamilla lajittelutekniikoilla, jotta näet tarkalleen, missä kukin voittaa.

BubblLajittelulla ja lisäyslajittelulla on sama lineaarinen paras tapaus, mutta lisäyslajittelu suorittaa vähemmän vaihtoja osittain lajitellulle datalle. Valintalajittelu suorittaa aina täsmälleen n-1 vaihtoa, mikä tekee siitätracaktiivinen, kun kirjoittaminen on kallista, vaikkakin se heikentää vakautta. Muutaman sadan alkion taulukoille pikalajittelu tai kekolajittelu on oikea valinta.

Kun olet tottunut tässä käytettyihin taulukon läpikäymismalleihin, sama silmukkarakenne esiintyy monissa klassisissa harjoituksissa, kuten Fibonaccin sarja Java ja Java palindromiohjelma. Revnäkeminen Java taulukot ja sitä leveämpi Java oppitunti vahvistaa tämän algoritmin perusperiaatteita.

UKK