Introductie van Bubble Sort in Java
Bubbelsortering is een van de meest gebruikte algoritmen voor het sorteren van gegevens in Java. Hier sorteren wordt gedaan door de aangrenzende getallen recursief te vergelijken en ze naar behoefte in oplopende of aflopende volgorde te verschuiven. Dit verschuiven van elementen wordt gedaan totdat alle cijfers volledig in de gewenste volgorde zijn gesorteerd.
De naam "Bubble-type" van dit algoritme komt omdat de elementen van een array zich een weg baantje naar het begin. Laten we het algoritme voor het sorteren van bellen begrijpen door een voorbeeld te nemen.
Voorbeeld: overweeg een reeks getallen (6 1 8 5 3) die in oplopende volgorde moeten worden gerangschikt.
Bellen sorteeralgoritme werkt in meerdere iteraties totdat wordt vastgesteld dat alle nummers zijn gesorteerd.
herhalingen
Hieronder zijn de iteraties uitgevoerd in Bubble Sort in Java die als volgt zijn:
Eerste herhaling
(6 1 8 5 3) - Het begint met het vergelijken van de eerste twee nummers en verschuift het kleinere aantal van de twee naar rechts. Daarom is onder 6 en 1, 1 het kleinere getal naar links en 6 naar rechts verschoven. (1 6 8 5 3) - Vervolgens vergelijkt het de aangrenzende twee nummers door een positie naar rechts te schuiven. Hier is nummer 6 kleiner dan 8 en daarom blijft dezelfde volgorde behouden. (1 6 8 5 3) - Door opnieuw een positie naar rechts te schuiven, vindt vergelijking plaats tussen 8 en 5. Nummer 5 wordt naar links verschoven omdat het kleiner is dan 8. (1 6 5 8 3) - Hier vindt de vergelijking plaats tussen nummer 8 en 3. Nummer 3 is naar links verschoven omdat het kleiner is dan 8. (1 6 5 3 8) - Dit is het eindresultaat van de bestelling na de 1e iteratie.Tweede herhaling
Omdat de nummers nog steeds niet helemaal in hun stijgende volgorde staan, gaat het programma voor de tweede iteratie.
(1 6 5 3 8) - Hier begint de vergelijking opnieuw vanaf de eerste twee cijfers van het resultaat vanaf de eerste iteratie. Het vergelijkt de cijfers 1 en 6 en behoudt dezelfde volgorde omdat 1 kleiner is dan 6. (1 6 5 3 8) - Hier worden nummers 5 en 6 vergeleken. Dezelfde volgorde blijft behouden omdat deze al in de vereiste toenemende volgorde staat. (1 5 6 3 8) - Hier vindt vergelijking plaats tussen nummers 6 en 3. Nummer 3 is naar links verschoven omdat het kleiner is dan 6. (1 5 3 6 8) - Volgende nummers 6 en 8 worden met elkaar vergeleken. Dezelfde bestelling blijft behouden als in een verwachte volgorde. (1 5 3 6 8) - Dit is het eindresultaat na de tweede iteratie. Toch kunnen we opmerken dat de cijfers niet volledig in hun toenemende volgorde staan. Toch moeten we nummers 5 en 3 uitwisselen om het eindresultaat te krijgen. Daarom gaat het programma voor de derde iteratie.Derde herhaling
(1 5 3 6 8) - de derde iteratie begint met het vergelijken van de eerste twee cijfers 1 en 5. Aangezien de volgorde is zoals verwacht, wordt deze hetzelfde behouden. (1 5 3 6 8) - Vervolgens worden de aangrenzende nummers 3 en 5 vergeleken. Omdat 5 groter is dan 3, wordt deze naar rechts verschoven. (1 3 5 6 8) - De iteratie gaat verder om de nummers 5 en 6, 6 en 8 te vergelijken. Omdat het in de gewenste volgorde staat, behoudt het de volgorde. (1 3 5 6 8) - Eindelijk wordt de iteratie gestopt terwijl het programma doorloopt en elk aangrenzend element vergelijkt en constateert dat alle cijfers in de toenemende volgorde staan.Omdat hier slechts 5 elementen van een array moesten worden gesorteerd, waren er in totaal slechts 3 iteraties nodig. Naarmate de elementen in de array toenemen, neemt ook het aantal iteraties toe.
Bubble Sort Implementatie met behulp van Java
Hieronder staat de Java-code die de implementatie is van het Bubble sort-algoritme. (Merk op dat de eerste positie van een array in Java begint bij 0 en doorgaat in stappen van 1, dwz array (0), array (1), array (2) en het verder gaat.)
Code:
import java.util.Scanner;
public class BubbleSort (
static void bubbleSort(int() arraytest) (
int n = arraytest.length; //length of the array is initialized to the integer n
int temp = 0; //A temporary variable called temp is declared as an integer and initialized to 0
for(int i=0; i < n; i++)( // first for loop performs multiple iterations
for(int j=1; j < (ni); j++)(
if(arraytest(j-1) > arraytest(j))( // if loop compares the adjacent numbers
// swaps the numbers
temp = arraytest(j-1); // assigns the greater number to temp variable
arraytest(j-1) = arraytest(j); // shifts the lesser number to the previous position
arraytest(j) = temp; // bigger number is then assigned to the right hand side
)
)
)
)
public static void main(String() args) (
int arraytest() =(23, 16, 3, 42, 75, 536, 61); // defining the values of array
System.out.println("Array Before Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++)( // for loop used to print the values of array
System.out.print(arraytest(i) + " ");
)
System.out.println();
bubbleSort(arraytest); // array elements are sorted using bubble sort function
System.out.println("Array After Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++)(
System.out.print(arraytest(i) + " "); // for loop to print output values from array
)
)
)
Output:
Voor- en nadelen van Bubble Sort in Java
Hieronder staan de verschillende voor- en nadelen van bubbelsoort in Java:
voordelen
- De code is heel gemakkelijk te schrijven en te begrijpen. Meestal duurt slechts een paar minuten.
- Implementatie is ook heel eenvoudig.
- Bellen sorteren sorteert de nummers en bewaart ze in het geheugen, dus bespaart veel geheugen.
nadelen
- Dit algoritme is niet geschikt voor grote datasets omdat de vergelijking veel tijd kost. De tijd die nodig is om invoernummers te sorteren neemt exponentieel toe.
- O (n 2) is de gemiddelde complexiteit van Bubble-sortering en O (n) is de complexiteit van het beste geval (het beste geval is wanneer de elementen in de eerste plaats worden gesorteerd) waarbij n het aantal elementen is.
Realtime toepassingen
Omdat Bubble sort minieme fouten bij het sorteren kan detecteren, wordt het gebruikt in computergraphics. Het wordt ook gebruikt in het polygoonvulalgoritme waarbij de hoekpunten van de polygoon moeten worden gesorteerd.
Conclusie
In dit artikel hebben we gezien hoe het Bubble sort-algoritme werkt en hoe het kan worden geïmplementeerd met behulp van Java-programmering. Bubbelsoort is een zeer stabiel algoritme dat eenvoudig kan worden geïmplementeerd voor relatief kleine datasets. Het is een geval van vergelijkingsalgoritme en wordt door beginners gebruikt vanwege zijn eenvoud.
Aanbevolen artikelen
Dit is een gids voor Bubble Sort op Java. Hier bespreken we meerdere iteraties om bellen te sorteren in Java en de code-implementatie ervan, samen met voor- en nadelen. U kunt ook de volgende artikelen bekijken voor meer informatie -
- Bubble Sort in JavaScript
- Sorteren in R
- 3D-arrays in Java
- Arrays in C #
- Bubble Sort in Python