Java Entwickler Experte
Bubble sort – Blasen-Sortierung in Java
Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung von Daten ist sehr wichtig für die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten benötigen. Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus hängt von Faktoren wie der Größe und den Eigenschaften der Eingabedaten, dem verfügbaren Speicher und den Zeit- und Platzanforderungen ab. Um Ihnen die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erklären und sie in Java programmieren. Heute befassen wir uns mit Bubble Sort.
Algorithmus für Bubble sort
Bubble Sort ist ein Sortieralgorithmus, der nacheinander jeweils zwei benachbarte Elemente vergleicht und sie verwirft, bis sie in der gewünschten Reihenfolge sortiert sind. Der Algorithmus erfordert mehrere Iterationen. Der Name des Algorithmus ist von den Luftblasen abgeleitet, die im Wasser an die Oberfläche steigen. Analog dazu steigen bei diesem Algorithmus die Elemente des Arrays bei jeder Iteration bis zum Ende des unsortierten Teils des Arrays auf.
Bubble Sort Algorithmus – Funktionsprinzip
Angenommen, wir möchten die Elemente in aufsteigender Reihenfolge sortieren. Wenn ein Array nur ein Element hat, gilt es als sortiert, andernfalls müssen die Elemente sortiert werden.
Erste Iteration:
Alle zwei benachbarten Array-Elemente werden der Reihe nach vom Anfang des Arrays an verglichen. Wenn das erste Element größer ist als das zweite, tauschen sie die Reihenfolge. Dann wird das zweite Element mit dem dritten verglichen, das dritte mit dem vierten, und so weiter. Die erste Iteration endet mit dem Vergleich der letzten benachbarten Elemente. Während der ersten Iteration wird durch das Vertauschen der Elemente garantiert, dass das größte Element des Arrays an das Ende des Arrays gebracht wird.
Andere Iterationen:
Der letzte Index des Arrays wird als sortiert betrachtet, der Rest des Arrays ist noch nicht sortiert. Für den unsortierten Teil des Arrays wird das Verfahren aus der ersten Iteration wiederholt. Bei jeder Iteration wird das größte Element an das Ende des unsortierten Arrays vorgeblasen. Dies wird so lange wiederholt, bis das Array sortiert ist.
Anzahl der Iterationen: n-1
Anzahl der Vergleiche: n*(n-1)/2
Beispiel
Wir haben das folgende Array mit den Elementen [3][1][2]. Aus den Formeln berechnen wir, dass die Anzahl der benötigten Iterationen 2 und die Anzahl der Vergleiche 6 beträgt.> In der ersten Iteration finden die folgenden Operationen statt: [1][3][2] – [1][2][3]. Das größte Element 3 wird auf den letzten Index des Arrays abgebildet. Obwohl das Array bereits sortiert ist, wird eine zweite Iteration durchgeführt, bei der die ersten beiden Elemente des Arrays verglichen werden. Da das erste und das zweite Element die richtige Reihenfolge haben, wird ihre Reihenfolge nicht vertauscht.
Optimierung des Bubble Sort Algorithmus
Im obigen Beispiel haben wir gesehen, dass, wenn wir das Array bereits sortiert haben, dennoch unnötigerweise zusätzliche Iterationen und Vergleiche durchgeführt werden. Das erhöht natürlich die Laufzeit des Algorithmus. Die Lösung besteht darin, dass wir bei jeder Iteration feststellen, ob es eine Neuordnung zweier Elemente gibt. Wenn nicht, betrachten wir das Array als sortiert und führen keine weiteren Iterationen durch. Diese Optimierung reduziert die Zeitkomplexität für ein bereits sortiertes Array und gewährleistet die Anpassungsfähigkeit des Algorithmus.
Vorteile des Bubble-Sortieralgorithmus
- Es ist leicht zu verstehen und umzusetzen
- Benötigt beim Sortieren keinen zusätzlichen Speicherplatz
- Es ist stabil, d.h. zwei identische Elemente aus der Eingabe behalten ihre relative Reihenfolge im Ergebnis bei
Nachteil des Bubble-Sortieralgorithmus
- Die Zeitkomplexität ist O(n²), was ihn zu einem langsamen Algorithmus für einen großen Datensatz macht.
Zeitaufwand für Bubble sort
| Algorithmus | Methode | Zeitliche Komplexität | Speicher | Stabil | ||
| schlechteste | durchschnittlich | beste | ||||
| Bubble sort | Austausch | O(n²) | O(n²) | O(n) | O(1) | Ja |
Bubble sort Animation, Visualisierung, gif
Die Visualisierung des Bubble-Sortieralgorithmus sieht folgendermaßen aus:
In diesem Artikel erfährst du:
Quelle: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms
Eine Animation des Algorithmus finden Sie zum Beispiel unter Toptal. Es gibt 8 Arten von Algorithmen, Sie können die Animation auch rückwärts abspielen. Auf dieser Seite können Sie die einzelnen Schritte des Algorithmus durchlaufen, so dass Sie den Zeitverbrauch des Algorithmus überprüfen können.
Bubble Sort Implementierung – Beispiel in Java
Lassen Sie uns eine optimierte Version von Bubble Sort in Java programmieren.
BubbleSort.java
package sorting;
// An optimized version of Bubble Sort
public class BubbleSort {
private boolean change;
private int temp;
public void sort(int data[])
{
for (int i = 0; i < data.length - 1; i++) {
System.out.println(i + 1 + ". iteration");
change = false;
for (int j = 0; j < data.length - i - 1; j++) {
if (data[j] > data[j + 1]) {
// Swap arr[j] and arr[j+1]
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
change = true;
printArray(data);
}
}
// If no two elements swapped, then end the sort method
if (!change)
return;
}
}
// Function to print an array
public void printArray(int data[])
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
System.out.println();
}
}Main.java
import sorting.BubbleSort;
public class Main {
public static void main(String[] args) {
int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
BubbleSort bubbleSort = new BubbleSort();
System.out.print("Input: ");
bubbleSort.printArray(dataToSort);
bubbleSort.sort(dataToSort);
System.out.print("Sorted: ");
bubbleSort.printArray(dataToSort);
}
}Die Ausgabe dieses Beispiels ist:
Wir haben die Dateien mit dem oben genannten Beispiel in Form von Code vorbereitet, den Sie direkt in Java ausführen können. Lade den Bubble Sort-Code in Java hier herunter.
Wenn du ein Java Programmierer bist und nach Arbeit suchst, schau dir unsere Mitareiterbenefits an und reagiere auf die neuesten Stellenangebote.
