Wenn Sie jemals von Sortiermethoden in der Programmierung gehört haben, war es höchstwahrscheinlich der Blasensortierungsalgorithmus. Es ist berühmt. Jeder Programmierer kennt die Blasensortierung (oder hat zumindest beim Lernen davon gehört), nicht weil es der beste Sortieralgorithmus der Welt ist, sondern weil er der einfachste ist. Dieser Algorithmus wird normalerweise zu Lernzwecken verwendet oder Sie erhalten ihn als Aufgabe in Ihrem Java Junior-Interview. Der Java-Bubble-Sortieralgorithmus ist sehr einfach zu verstehen, jedoch nicht effizient. Wie auch immer, lass es uns herausfinden.
Schritt 1: Wir gehen das Array durch. Der Algorithmus beginnt mit den ersten beiden Elementen (mit den Indizes 0 und 1), 8 und 7, und prüft, ob sie in der richtigen Reihenfolge sind. Offensichtlich ist 8 > 7, also tauschen wir sie aus. Als nächstes schauen wir uns das zweite und dritte Element (Indizes 1 und 2) an, nun sind das 8 und 1. Aus den gleichen Gründen vertauschen wir sie. Zum dritten Mal vergleichen wir 8 und 2 und mindestens 8 und 5. Wir haben insgesamt vier Austausche vorgenommen: (8, 7), (8, 1), (8, 2) und (8, 5). Der Wert 8, der größte in diesem Array, wurde am Ende der Liste an der richtigen Position angezeigt.
Das Ergebnis des ersten Arbeitsschritts des Bubble-Sort-Algorithmus ist das nächste Array:
Schritt 2. Machen Sie dasselbe mit (7,1), (7,2) und (7,5). 7 befindet sich jetzt an vorletzter Stelle und wir müssen sie nicht mit dem „Ende“ der Liste vergleichen, sie ist bereits sortiert.
Das Ergebnis des zweiten Schritts des Bubble-Sort-Algorithmus ist das nächste Array:
Wie Sie vielleicht sehen, ist dieses Array bereits sortiert. Auf jeden Fall sollte der Bubble-Sort-Algorithmus noch mindestens einmal in Gang kommen. Schritt 3. Wir gehen das Array noch einmal durch. Hier gibt es nichts zu tauschen. Wenn wir also den „verbesserten“ Bubble-Sort-Algorithmus verwenden (mit Prüfung, ob im vorherigen Schritt mindestens ein Austausch durchgeführt wurde), ist dieser Schritt der letzte.
Was ist Sortieren?
Zunächst müssen Sie verstehen, was Sortieren im Allgemeinen ist und was wir in Java-Programmen sortieren können. Wenn wir zwei oder mehr Elemente oder Objekte anhand eines ihrer Attribute vergleichen können, bedeutet dies, dass sie nach diesem Attribut sortiert werden können. Zum Beispiel Zahlen in aufsteigender oder absteigender Reihenfolge oder Wörter alphabetisch. Daher müssen die Elemente miteinander vergleichbar sein. Übrigens, die Elemente von was? In Java können wir die Elemente von Sammlungen vergleichen. Zum Beispiel können wir Array oder ArrayList von Ganzzahlen, Strings usw. sortieren.Wie funktioniert die Blasensortierung?
Nehmen wir an, wir müssen ein Array von ganzen Zahlen in aufsteigender Reihenfolge sortieren, also von der kleinsten zur größten Zahl. Zuerst gehen wir das gesamte Array durch und vergleichen alle zwei benachbarten Elemente. Wenn sie in der falschen Reihenfolge sind (der linke Nachbar ist größer als der rechte), vertauschen wir sie. Beim ersten Durchgang erscheint am Ende das größte Element (wenn wir in aufsteigender Reihenfolge sortieren). Man könnte sagen, das größte Element „springt auf“. Das ist der Grund für den Namen des Bubble-Sortieralgorithmus. Wir wiederholen den ersten Schritt vom ersten bis zum vorletzten Element. Das zweitgrößte Element haben wir auf dem vorletzten Platz. Usw. Wir können einen Algorithmus ein wenig verbessern, indem wir prüfen, ob im vorherigen Schritt mindestens ein Austausch durchgeführt wurde. Ist dies nicht der Fall, hören wir auf, entlang des Arrays zu laufen.Beispiel für eine Blasensortierung
Lassen Sie uns das Array von Ganzzahlen sortieren, das Sie unten auf einem Bild sehen können.




Java-Code mit Blasensortierung
Blasensortierung in Java
Lassen Sie uns zwei Methoden für die Blasensortierung erstellen. Die erste, bubbleSort(int[] myArray) ist eine ebene. Es durchläuft jedes Mal das Array. Der zweite, optimierteBubbleSort(int myArray[]) wird optimiert, indem der Algorithmus angehalten wird, wenn die innere Schleife keinen Austausch verursacht hat. Der Zähler zeigt Ihnen, wie viele Schritte Sie beim Sortieren gemacht haben. Hier haben wir die Java-Realisierung von Bubble Sort:
import java.util.Arrays;
public class BubbleSortExample {
// Plane Bubble sort example
public static int[] bubbleSort(int[] myArray) {
int temp = 0; // temporary element for swapping
int counter = 0; // element to count quantity of steps
for (int i = 0; i < myArray.length; i++) {
counter = i + 1;
for (int j = 1; j < (myArray.length - i); j++) {
if (myArray[j - 1] > myArray[j]) {
// swap array’s elements using temporary element
temp = myArray[j - 1];
myArray[j - 1] = myArray[j];
myArray[j] = temp;
}
}
}
System.out.println("Steps quantity, non optimized = " + counter);
return myArray;
}
// An optimized version of Java Bubble Sorting
static int[] optimizedBubbleSort(int myArray[]) {
int temp;
boolean swapped;
int counter = 0; // element to count quantity of steps
for (int i = 0; i < myArray.length - 1; i++) {
counter = i + 1;
swapped = false;
for (int j = 0; j < myArray.length - i - 1; j++) {
// counter++;
if (myArray[j] > myArray[j + 1]) {
// swap arr[j] and arr[j+1]
temp = myArray[j];
myArray[j] = myArray[j + 1];
myArray[j + 1] = temp;
swapped = true;
}
} // counter = i;
// If there weren't elements to swap in inner loop, then break
if (swapped == false) {
break;
}
}
System.out.println("steps quantity, optimized = " + counter);
return myArray;
}
public static void main(String[] args) {
int arr[] = {8, 7, 1, 2, 5};
int arr1[] = {8, 7, 1, 2, 5};
System.out.println("Array arr Before Bubble Sort");
// we use java.util.Arrays toString method to print the array
System.out.println(Arrays.toString(arr));
System.out.println("Array arr After Bubble Sort");
System.out.println(Arrays.toString(bubbleSort(arr)));
System.out.println("Array arr1 Before Bubble Sort");
System.out.println(Arrays.toString(arr1));
System.out.println("Array arr1 After Optimized Bubble Sort");
System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
}
}
Das Ergebnis der Arbeit des Java-Algorithmus „Bubble Sort“:
Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]
GO TO FULL VERSION