Bubble Lajittele algoritmi Java: Taulukon lajitteluohjelma ja esimerkki
Toimituksellinen tiimi
⚡ Älykäs yhteenveto
Bubble Lajittele algoritmi Java vertaa toistuvasti vierekkäisiä taulukon alkioita ja vaihtaa niitä, kunnes sekvenssi on järjestyksessä. Tässä artikkelissa selitetään toimintamekanismi, pseudokoodi, täydellinen Java toteutus, optimoitu variantti, monimutkaisuusanalyysi ja käytännön vertailut muihin lajittelutekniikoihin.
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:
- Vertailla: Vertaile indeksin j-1 alkiota indeksin j alkioon verrattuna.
- Vaihtaa: Jos vasen elementti on suurempi kuin oikea elementti, vaihda kahden arvon arvot käyttämällä väliaikaista muuttujaa.
- Advance: Siirrä yksi sijainti oikealle ja toista, kunnes lajittelemattoman alueen loppu on saavutettu.
- 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.
| Siirtää | Taulukko reitin alussa | Suoritetut vertailut | Matriisi passin lopussa | Elementti lukittu |
|---|---|---|---|---|
| 1 | 860, 8, 200, 9 | 3 | 8, 200, 9, 860 | 860 |
| 2 | 8, 200, 9, 860 | 2 | 8, 9, 200, 860 | 200 |
| 3 | 8, 9, 200, 860 | 1 | 8, 9, 200, 860 | 9 |
| 4 | 8, 9, 200, 860 | 0 | 8, 9, 200, 860 | 8 |
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.
| skenaario | Syöttöehto | Ajan monimutkaisuus | Avaruuden monimutkaisuus |
|---|---|---|---|
| Paras tapaus | Taulukko on jo lajiteltu, optimoitu versio | O (n) | O (1) |
| Keskimääräinen tapaus | Elementit satunnaisessa järjestyksessä | O(n²) | O (1) |
| Pahimmassa tapauksessa | Käänteisessä järjestyksessä lajiteltu taulukko | O(n²) | O (1) |
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.
💡 Vinkki: Tuotannossa Java koodi, mieluiten Arrays.sort() alkukantaisille ja Kokoelmat.sort() listoille. Molemmat käyttävät tarkasti viritettyjä algoritmeja, Dual-Pivot Quicksortia ja TimSortia, jotka toimivat paremmin kuin käsin kirjoitettu Bubble Lajittele suuruusluokkien mukaan.
Bubble-lajittelu vs. muu lajittelu Algorithms
Alla oleva taulukko vertaa BubblLajittele aloittelijoiden seuraavaksi kohtaamilla lajittelutekniikoilla, jotta näet tarkalleen, missä kukin voittaa.
| algoritmi | Paras tapaus | Keskimääräinen kotelo | Pahimmassa tapauksessa | Tila | Vakaa |
|---|---|---|---|---|---|
| Bubble Lajittele | O (n) | O(n²) | O(n²) | O (1) | Kyllä |
| Valinta Lajittele | O(n²) | O(n²) | O(n²) | O (1) | Ei |
| Lisäyslajittelu | O (n) | O(n²) | O(n²) | O (1) | Kyllä |
| Pikavalinta | O (n log n) | O (n log n) | O(n²) | O (log n) | Ei |
| Keon lajittelu | O (n log n) | O (n log n) | O (n log n) | O (1) | Ei |
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.
