Blasensortierung in Java

Bubble Sort ist einer der am häufigsten verwendeten Algorithmen zum Sortieren von Daten in Java. Die Sortierung erfolgt rekursiv, indem benachbarte Zahlen verglichen und in aufsteigender oder absteigender Reihenfolge verschoben werden. Dieses Verschieben der Elemente erfolgt so lange, bis alle Ziffern vollständig in der erforderlichen Reihenfolge sortiert sind. „Bubble Sort“ ist der Name, weil die Elemente einer Array-Blase ihr Ausgangspunkt sind. Lassen Sie uns den Blasensortierungsalgorithmus anhand eines Beispiels verstehen.

Beispiel:Betrachten Sie eine Reihe von Zahlen [6 1 8 5 3], die in aufsteigender Reihenfolge angeordnet werden müssen.

Starten Sie Ihren kostenlosen Softwareentwicklungskurs

Webentwicklung, Programmiersprachen, Softwaretests und andere

Der Blasensortierungsalgorithmus arbeitet in mehreren Iterationen, bis er feststellt, dass alle Zahlen sortiert sind.

Iterationen

Unten sind die Iterationen aufgeführt, die in Bubble Sort in Java durchgeführt werden, und zwar wie folgt:

Erste Iteration

[6 1 8 5 3] – Es beginnt mit dem Vergleich der ersten beiden Zahlen und verschiebt die kleinere der beiden nach rechts. Unter 6 und 1 ist also 1 die kleinere Zahl, die nach links verschoben wird, und 6 nach rechts. [1 6 8 5 3] – Als nächstes vergleicht es die benachbarten zwei Zahlen, indem es eine Position nach rechts verschiebt. Hier ist die Zahl 6 kleiner als 8 und daher wird die gleiche Reihenfolge beibehalten. [1 6 8 5 3] – Auch hier findet durch die Verschiebung um eine Position nach rechts ein Vergleich zwischen 8 und 5 statt. Zahl 5 wird nach links verschoben, da sie kleiner ist als 8. [1 6 5 8 3] – Hier findet der Vergleich zwischen den Zahlen 8 und 3 statt. Die Zahl 3 wird nach links verschoben, da sie kleiner als 8 ist. [1 6 5 3 8] – Dies ist das Endergebnis der Bestellung nach der 1. Iteration.

Zweite Iteration

Da die Zahlen immer noch nicht vollständig steigen, geht das Programm in die zweite Iteration.

[1 6 5 3 8] – Auch hier beginnt der Vergleich wieder mit den ersten beiden Ziffern des ersten Iterationsergebnisses. Es vergleicht die Zahlen 1 und 6 und behält die gleiche Reihenfolge bei, da 1 kleiner als 6 ist. [1 6 5 3 8] – Hier werden die Zahlen 5 und 6 verglichen. Die gleiche Reihenfolge wird beibehalten, da sie bereits in der erforderlichen aufsteigenden Reihenfolge vorliegt. [1 5 6 3 8] – Es findet ein Vergleich zwischen den Zahlen 6 und 3 statt. Zahl 3 wird nach links verschoben, da sie kleiner als 6 ist. [1 5 3 6 8] – Als nächstes werden die Zahlen 6 und 8 miteinander verglichen. Die gleiche Reihenfolge wird wie in einer erwarteten Reihenfolge beibehalten. [1 5 3 6 8] – Dies ist das Endergebnis nach der zweiten Iteration. Dennoch können wir feststellen, dass die Ziffern nicht vollständig in ihrer aufsteigenden Reihenfolge angeordnet sind. Dennoch müssen wir die Zahlen 5 und 3 vertauschen, um das Endergebnis zu erhalten. Daher geht das Programm zur dritten Iteration über.

Dritte Iteration

[1 5 3 6 8] – die dritte Iteration beginnt mit dem Vergleich der ersten beiden Ziffern, 1 und 5. Da die Reihenfolge wie erwartet ist, wird sie beibehalten. [1 5 3 6 8]- Als nächstes werden die benachbarten Zahlen 3 und 5 verglichen. Da 5 größer als 3 ist, wird es nach rechts verschoben. [1 3 5 6 8] – Die Iteration vergleicht dann die Zahlen 5 und 6, 6 und 8. Da sie in der erforderlichen Reihenfolge vorliegen, wird die Reihenfolge beibehalten. [1 3 5 6 8] – Schließlich wird die Iteration gestoppt, während das Programm jedes benachbarte Element vergleicht und feststellt, dass alle Ziffern in aufsteigender Reihenfolge sind.

Da nur 5 Elemente eines Arrays sortiert werden mussten, waren nur 3 Iterationen erforderlich. Wenn die Elemente im Array zunehmen, erhöht sich auch die Anzahl der Iterationen.

Bubble Sort-Implementierung mit Java

Unten finden Sie den Java-Code, der den Bubble-Sortieralgorithmus implementiert. (Beachten Sie, dass die erste Position eines Arrays in Java bei 0 beginnt und in Schritten von 1 fortgesetzt wird, d. h. Array[0], Array[1], Array[2], und so weiter.)

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 < (n-i); 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
}
}
}

Ausgabe:

Vor- und Nachteile der Blasensortierung in Java

Im Folgenden sind die verschiedenen Vor- und Nachteile der Blasensortierung in Java aufgeführt:

Vorteile

1. Der Code ist sehr einfach zu schreiben und zu verstehen. Normalerweise dauert es nur ein paar Minuten.
2. Auch die Umsetzung ist sehr einfach.
3. Die Blasensortierung sortiert die Zahlen und speichert sie im Speicher, wodurch viel Speicherplatz gespart wird.

Nachteile

1. Dieser Algorithmus ist nicht für große Datensätze geeignet, da der Vergleich viel Zeit in Anspruch nimmt. Die Zeit, die zum Sortieren der Eingabenummern benötigt wird, nimmt exponentiell zu.
2. O(n^2) ist die durchschnittliche Komplexität der Blasensortierung und O(n) ist die Komplexität im besten Fall (im besten Fall werden die Elemente an erster Stelle sortiert), wobei n die Anzahl der Elemente ist.

Echtzeitanwendungen

Da die Blasensortierung in der Lage ist, kleinste Sortierfehler zu erkennen, wird sie in der Computergrafik verwendet. Es wird auch im Polygonfüllalgorithmus verwendet, bei dem die Eckpunkte des Polygons sortiert werden müssen.

Fazit

In diesem Artikel wurde erläutert, wie der Bubble-Sortieralgorithmus funktioniert und wie er mithilfe der Java-Programmierung implementiert werden kann. Bubble Sort ist ein sehr stabiler Algorithmus, der sich leicht für vergleichsweise kleine Datensätze implementieren lässt. Es handelt sich um einen Vergleichsalgorithmus, der aufgrund seiner Einfachheit auch von Anfängern verwendet wird.

Das obige ist der detaillierte Inhalt vonBlasensortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!