Bubble Sorteeralgoritme in Java: Array-sorteerprogramma en voorbeeld
Redactie
⚡ Slimme samenvatting
Bubble Sorteeralgoritme in Java Vergelijkt herhaaldelijk aangrenzende array-elementen en verwisselt ze totdat de volgorde correct is. Dit artikel legt het werkingsmechanisme, pseudocode en een complete beschrijving uit. Java Implementatie, geoptimaliseerde variant, complexiteitsanalyse en praktische vergelijkingen met andere sorteertechnieken.
Wat is Bubble Sorteren?
BubbleSort is een eenvoudig vergelijkingsalgoritme dat het eerste element van een array vergelijkt met het volgende. Als het huidige element numeriek groter is dan het volgende, worden de elementen verwisseld. Op deze manier doorloopt het algoritme alle elementen van de array.
Het algoritme dankt zijn naam aan de manier waarop de grootste waarde in het ongesorteerde gedeelte gestaag naar zijn uiteindelijke positie stijgt, net zoals een bubbel naar het wateroppervlak stijgt. Na de eerste volledige doorgang bevindt het grootste element zich op de laatste index. Na de tweede doorgang wordt het op één na grootste element vastgezet en herhaalt het proces zich totdat de array volledig geordend is.
In dit artikel gaan we een Java programma om te implementeren Bubble Sorteer. Controleer de uitvoer van de code om de programmalogica te begrijpen, en bekijk vervolgens de geoptimaliseerde versie en de complexiteitsanalyse die volgen.
Hoe doet de BubblWerkt het sorteeralgoritme?
BubbleSort werkt door herhaaldelijk door de array te gaan. Elke keer loopt de array van de eerste index naar het einde van het momenteel ongesorteerde gedeelte, waarbij aangrenzende waarden worden vergeleken en verwisseld.ping Ze worden verwijderd wanneer ze in de verkeerde volgorde verschijnen. Omdat de grootste overgebleven waarde altijd naar de uiterste rechterkant van het ongesorteerde gebied beweegt, krimpt het gebied na elke doorgang met precies één positie.
Het volledige proces kan worden onderverdeeld in vier herhaalbare stappen:
- Vergelijken: Vergelijk het element op index j-1 met het element op index j.
- swap: Als het linkerelement groter is dan het rechterelement, wissel dan de twee waarden om met behulp van een tijdelijke variabele.
- Van te voren: Schuif één positie naar rechts en herhaal dit totdat het einde van het ongesorteerde gebied is bereikt.
- Herhaling: Begin een nieuwe doorgang over een regio die één element korter is, en stop na n-1 doorgangen of wanneer een doorgang geen wisselingen uitvoert.
De tafel onder tracDe voorbeeldreeks {860, 8, 200, 9} die later in het programma op deze pagina wordt gebruikt, laat precies zien welke waarde aan het einde van elke iteratie op zijn uiteindelijke positie terechtkomt.
| Passeren | Array aan het begin van de pass | Uitgevoerde vergelijkingen | Array aan het einde van de doorgang | Element vergrendeld |
|---|---|---|---|---|
| 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 |
Merk op dat de derde stap een vergelijking uitvoert, maar geen verwisseling. Een geoptimaliseerde implementatie detecteert die situatie en stopt onmiddellijk, wat de meest waardevolle verbetering is die je op dit algoritme kunt toepassen.
Bubble Sort-algoritme pseudocode
Voor het schrijven Java Syntaxis helpt om de logica uit te drukken in taalneutrale pseudocode. De onderstaande versie bevat de vlag voor vroegtijdige beëindiging, waardoor zowel het klassieke als het geoptimaliseerde gedrag wordt afgedekt.
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
De buitenste lus bepaalt het aantal iteraties, en de binnenste lus bepaalt de vergelijkingen binnen één iteratie. De bovengrens van de binnenste lus is n – i – 1, omdat de laatste i posities al hun eindwaarden bevatten.
Java Programma ter implementatie Bubble Sorteren
Het volgende programma sorteert een array van gehele getallen in oplopende volgorde. Extra print-statements zijn opzettelijk binnen de lussen geplaatst, omdat het lezen van de pass-by-pass-uitvoer anders onnodig zou zijn. tracDit is de snelste manier voor een beginner om te begrijpen hoe de swaps zich ophopen.
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 uitleg: De bubbleSort De methode ontvangt de array via referentie, waardoor de aanroeper het gesorteerde resultaat ziet zonder een retourwaarde. De variabele temp behoudt één waarde tijdens de drieregelige swap, waardoor het algoritme slechts O(1) extra geheugen nodig heeft. De uitdrukking n – i De voorwaarde in de binnenste lus garandeert dat reeds gesorteerde posities aan het einde nooit opnieuw worden bezocht.
Geoptimaliseerde Bubble Programma sorteren Java
Het bovenstaande programma voert altijd n-1 passes uit, zelfs als de array al vroeg gesorteerd is. Door een enkele boolean-vlag toe te voegen, wordt deze inefficiëntie verholpen. Als een volledige pass zonder één enkele swap is voltooid, is de array gegarandeerd gesorteerd en kan de buitenste lus direct stoppen.
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]
De invoerarray was al gesorteerd, waardoor de geoptimaliseerde versie na één doorgang in plaats van vier klaar was. Bij bijna gesorteerde data verandert deze wijziging een kwadratische werklast in een bijna lineaire, wat de belangrijkste reden is. BubblSort komt nog steeds af en toe voor in echte code.
Tijdcomplexiteit en ruimtecomplexiteit van Bubble Sorteren
Complexiteit beschrijft hoe de looptijd toeneemt naarmate de invoergrootte toeneemt. Bubble Sorteer het aantal vergelijkingen in de niet-geoptimaliseerde versie, dat vaststaat op n(n-1)/2, waardoor het stevig in de kwadratische klasse valt.
| Scenario | Invoervoorwaarde | Tijdcomplexiteit | Complexiteit van de ruimte |
|---|---|---|---|
| Beste geval | Array is al gesorteerd, geoptimaliseerde versie | O (n) | O (1) |
| gemiddeld geval | Elementen in willekeurige volgorde | O(n²) | O (1) |
| Het slechtste geval | Array gesorteerd in omgekeerde volgorde | O(n²) | O (1) |
Omdat elke uitwisseling plaatsvindt binnen de oorspronkelijke array en er slechts één tijdelijke variabele wordt gebruikt, BubbleSort is een in-place sorteeralgoritme met O(1) hulpruimte. Het is ook een stabiele sorteermethode, wat betekent dat twee records met dezelfde sleutel hun oorspronkelijke relatieve volgorde behouden na het sorteren.
Voor- en nadelen van Bubble Sorteren
Door beide kanten te begrijpen, kun je beter bepalen wanneer een algoritme een acceptabele keuze is en wanneer het vervangen moet worden.
Voordelen
- Eenvoud: De logica past in ongeveer tien regels, waardoor het gemakkelijk is om het correct te formuleren tijdens een sollicitatiegesprek.
- In-situ werking: Er wordt geen hulparray toegewezen, waardoor het geheugenverbruik niet toeneemt met de grootte van de invoer.
- Stabiliteit: Gelijke sleutels behouden hun oorspronkelijke volgorde, wat belangrijk is bij het sorteren van records op een secundair veld.
- Vroegtijdige detectie van uitgangen: De 'swapperd'-vlag geeft aan dat de array al in één keer gesorteerd is.
Nadelen
- Kwadratische groei: Het sorteren van 10,000 elementen vereist in het ergste geval bijna 50 miljoen vergelijkingen.
- Overmatig schrijven: Het algoritme voert veel meer swaps uit dan Selection Sort, wat geheugenintensief is vanwege de trage schrijfbewerkingen.
- Slechte schaalbaarheid: In productieomgevingen geven we bijna altijd de voorkeur aan Quicksort, Merge Sort of de ingebouwde Arrays.sort-methode.
💡Tip: In de maak Java code, liever Arrays.sort () voor primitieve volkeren en Collecties.sort() voor lijsten. Beide gebruiken zeer verfijnde algoritmes, respectievelijk Dual-Pivot Quicksort en TimSort, die beter presteren dan een handgeschreven lijst. Bubble Sorteer op orde van grootte.
Bubble Sorteermethode versus andere sorteermethoden Algorithms
De onderstaande tabel vergelijkt Bubble Sorteer met behulp van de sorteertechnieken die beginners hierna tegenkomen, zodat je precies kunt zien waar elke techniek in uitblinkt.
| Algoritme | Beste geval | Gemiddeld geval | Het slechtste geval | Tussenruimte | Stal |
|---|---|---|---|---|---|
| Bubble Sorteren | O (n) | O(n²) | O(n²) | O (1) | Ja |
| Selectie sorteren | O(n²) | O(n²) | O(n²) | O (1) | Nee |
| Invoegsortering | O (n) | O(n²) | O(n²) | O (1) | Ja |
| Snel sorteren | O (n log n) | O (n log n) | O(n²) | O (log n) | Nee |
| Heap Sorteren | O (n log n) | O (n log n) | O (n log n) | O (1) | Nee |
BubblSelectiesortering en invoegsortering hebben hetzelfde lineaire beste geval, maar invoegsortering voert minder wisselingen uit op gedeeltelijk gesorteerde gegevens. Selectiesortering voert altijd precies n-1 wisselingen uit, waardoor het op een bepaald moment beter presteert.tracQuicksort is nuttig wanneer schrijfbewerkingen veel tijd kosten, hoewel dit ten koste gaat van de stabiliteit. Voor arrays met meer dan een paar honderd elementen zijn Quicksort of Heapsort de juiste keuze.
Als je eenmaal vertrouwd bent met de hier gebruikte array-traversalpatronen, zul je dezelfde lusstructuur terugvinden in veel klassieke oefeningen, zoals de Fibonacci-reeks in Java en Java palindroomprogramma. Revkijken Java arrays en de bredere Java zelfstudie Dit zal de fundamenten versterken waarop dit algoritme is gebaseerd.
