Bubble Algoritam sortiranja u Java: Program za sortiranje polja i primjer

Što je Bubble Sortiraj?

BubblSortiranje je jednostavan algoritam sortiranja temeljen na usporedbi koji uspoređuje prvi element polja sa sljedećim. Ako je trenutni element polja numerički veći od sljedećeg, elementi se zamjenjuju. Slično tome, algoritam će proći kroz cijeli element polja.

Algoritam je dobio ime po načinu na koji se najveća vrijednost u nesortiranom području stalno penje do svoje konačne pozicije, slično mjehuriću koji se diže na površinu vode. Nakon prvog potpunog prolaza, najveći element zauzima posljednji indeks. Nakon drugog prolaza, drugi najveći element se zaključava na mjestu i proces se ponavlja sve dok niz nije potpuno uređen.

U ovom članku ćemo stvoriti Java program za provedbu Bubble Sortiraj. Provjerite izlaz koda koji će vam pomoći da shvatite logiku programa, a zatim pregledajte optimiziranu verziju i analizu složenosti koja slijedi.

Kako BubblRadi li algoritam sortiranja?

BubblSortiranje funkcionira ponovljenim prolaskom kroz niz. Svaki prolaz ide od prvog indeksa do kraja trenutno nesortiranog područja, uspoređujući susjedne vrijednosti i zamjenjujući ih.ping ih kad god se pojave u pogrešnom redoslijedu. Budući da najveća preostala vrijednost uvijek putuje u krajnju desnu stranu nesortiranog područja, područje se smanjuje za točno jednu poziciju nakon svakog prolaza.

Cijeli proces može se podijeliti u četiri koraka koja se mogu ponavljati:

1. Usporedite: Usporedite element na indeksu j-1 s elementom na indeksu j.
2. swap: Ako je lijevi element veći od desnog elementa, zamijenite dvije vrijednosti pomoću privremene varijable.
3. unaprijed: Pomaknite se za jednu poziciju udesno i ponavljajte dok se ne dođe do kraja nesortiranog područja.
4. Ponoviti: Započni novi prolaz preko regije koja je za jedan element kraća i zaustavi se nakon n-1 prolaza ili kada prolaz ne izvrši zamjene.

Tablica ispod tracje primjer niza {860, 8, 200, 9} korištenog u programu kasnije na ovoj stranici. Točno pokazuje koja vrijednost se na kraju svakog prolaza postavlja na svoju konačnu poziciju.

Primijetite da treći prolaz izvodi usporedbu, ali ne i zamjenu. Optimizirana implementacija detektira taj uvjet i odmah se zaustavlja, što je najvrjednije poboljšanje koje možete primijeniti na ovaj algoritam.

BubblPseudokod algoritma sortiranja e

Prije pisanja Java sintaksa, pomaže u izražavanju logike u jezično neutralnom pseudokodu. Verzija u nastavku uključuje zastavicu ranog izlaza, tako da pokriva i klasično i optimizirano ponašanje.

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

Vanjska petlja kontrolira broj prolaza, a unutarnja petlja kontrolira usporedbe unutar jednog prolaza. Gornja granica unutarnje petlje je n – i – 1 jer posljednjih i pozicija već sadrži svoje konačne vrijednosti.

Java Program za provedbu Bubble Razvrstaj

Sljedeći program sortira niz cijelih brojeva u rastućem redoslijedu. Dodatne naredbe ispisa su namjerno zadržane unutar petlji, jer čitanje prolaznog niza tracTo je najbrži način za početnike da shvate kako se swapovi akumuliraju.

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

    }
}

Izlaz:

---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 obrazloženje: The Sortiranje mjehurićima Metoda prima niz referencom, tako da pozivatelj vidi sortirani rezultat bez ikakve povratne vrijednosti. Varijabla temp sadrži jednu vrijednost tijekom zamjene triju redaka, zbog čega algoritmu treba samo O(1) dodatne memorije. Izraz n – i u uvjetu unutarnje petlje jamči da se već sortirane pozicije na repu nikada ne posjećuju ponovno.

Optimizirano Bubble Razvrstaj program u Java

Gornji program uvijek izvodi n-1 prolaza, čak i kada se niz rano sortira. Dodavanje jedne logičke vrijednosti ispravlja tu neučinkovitost. Ako se cijeli prolaz završi bez ijedne zamjene, niz je zajamčeno sortiran i vanjska petlja može se odmah zaustaviti.

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

Izlaz:

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

Ulazni niz je već bio sortiran, pa je optimizirana verzija završila nakon jednog prolaza umjesto četiri. Na gotovo sortiranim podacima ova promjena pretvara kvadratno opterećenje u gotovo linearno, što je glavni razlog. BubblSortiranje se još uvijek povremeno pojavljuje u stvarnom kodu.

Vremenska složenost i prostorna složenost Bubble Razvrstaj

Složenost opisuje kako vrijeme izvođenja raste s povećanjem ulazne veličine. Za BubblBroj usporedbi u neoptimiziranoj verziji sortiranja je fiksan na n(n-1)/2, što ga čvrsto smješta u kvadratnu klasu.

Budući da se svaka izmjena događa unutar izvornog niza i koristi se samo jedna privremena varijabla, BubblSortiranje je algoritam na mjestu s O(1) pomoćnim prostorom. Također je stabilno sortiranje, što znači da dva zapisa s istim ključem zadržavaju svoj izvorni relativni redoslijed nakon sortiranja.

Prednosti i nedostaci Bubble Razvrstaj

Razumijevanje obje strane pomaže vam da odlučite kada je algoritam prihvatljiv izbor i kada ga treba zamijeniti.

Prednosti

• Jednostavnost: Logika stane u otprilike deset redaka, što olakšava ispravno pisanje u uvjetima intervjua.
• Rad na licu mjesta: Nije dodijeljen pomoćni niz, tako da korištenje memorije ne raste s veličinom ulaza.
• Stabilnost: Jednaki ključevi zadržavaju svoj izvorni redoslijed, što je važno pri sortiranju zapisa po sekundarnom polju.
• Rano otkrivanje izlaska: Zastavica zamjene identificira već sortirani niz u jednom prolazu.

Nedostaci

• Kvadratni rast: Sortiranje 10 000 elemenata zahtijeva gotovo 50 milijuna usporedbi u najgorem slučaju.
• Prekomjerno piše: Algoritam izvodi puno više zamjena nego sortiranje odabirom, koje je skupo za memoriju sa sporim operacijama pisanja.
• Slaba skalabilnost: Produkcijska opterećenja gotovo uvijek favoriziraju Quicksort, Merge Sort ili ugrađenu metodu Arrays.sort.

Bubble Sortiranje u odnosu na druga sortiranja Algorithms

Donja tablica uspoređuje Bubble Sortirajte pomoću tehnika sortiranja koje početnici susreću sljedeće, tako da možete točno vidjeti gdje koja pobjeđuje.

BubblSortiranje i sortiranje umetanjem dijele isti linearni najbolji slučaj, ali sortiranje umetanjem izvodi manje zamjena na djelomično sortiranim podacima. Sortiranje odabirom uvijek izvodi točno n-1 zamjena, što ga čini...tracposebno kada su zapisi skupi, iako žrtvuje stabilnost. Za bilo koji niz veći od nekoliko stotina elemenata, Quicksort ili Heap Sort je ispravan izbor.

Nakon što se upoznate s ovdje korištenim obrascima prolaska kroz nizove, ista struktura petlje pojavljuje se u mnogim klasičnim vježbama kao što je Fibonaccijev niz u Java i Java palindromski program. Reviewing Java nizovi i šire Java udžbenik ojačat će osnove na kojima ovaj algoritam ovisi.

Pitanja i odgovori