Der Bubblesort-Algorithmus (Blasen-Sortierung) ist ein stabiler, einfacher und vor allem sehr langsamer und daher nicht zu empfehlender Sortieralgorithmus. Durch seine Einfachheit eignet er sich aber bestens für Programmieranfänger zum Nachprogrammieren und lernen.
Funktionsweise
Beim Bubblesort werden aufeinander folgende Elemente miteinander verglichen und ggf. gegeneinander ausgetauscht (falls die Reihenfolge der Werte nicht stimmt). Dabei werden alle Elemente so oft durchlaufen, bis es keine Vertauschungen mehr gibt.
Programmierung
Natürlich legen Sie wieder zuerst eine neue Klasse an. Diese Klasse enthält die öffentliche Methode bubbleSort mit keinem Rückgabewert und dem Parameter int[] (die zu sortierenden Elemente). Außerdem erstellen wir noch eine private Methode, die zwei Elemente eines int-Arrays vertauscht. Dazu benötigen wir keinen Rückgabetyp aber als Parameter das Array, in welchem getauscht werden soll, und die beiden Positionen der Elemente, die vertauscht werden sollen.
public class Sorter {
public void bubbleSort(int[] ar) {
}
private void swap(int[] ar, int pos1, int pos2) {
}
}
Der eigentliche Algorithmus – Sie haben es erraten – kommt in die bubbleSort-Methode. Zuerst kümmern wir uns aber um die swap-Methode.
Um zwei Elemente in einem Array zu vertauschen, muss das erste Element zwischengespeichert werden. Anschließend wird das erste Element durch das zweite ersetzt. Ersetzen Sie danach noch das zweite Element mit dem Zwischengespeicherten und Sie haben die Positionen getauscht.
private void swap(int[] ar, int pos1, int pos2) {
int temp = ar[pos1];
ar[pos1] = ar[pos2];
ar[pos2] = temp;
}
Sie müssen nun folgende Punkte für den Algorithmus umsetzen:
- Solange das komplette Array durchlaufen, bis keine Vertauschung mehr erfolgt, oder das Array “Array-Länge – 1″ mal durchlaufen wurde (maximal nötige Anzahl)
- Jedes Element im Array mit dessen Nachbarn vergleichen.
- Falls die Reihenfolge der Nachbarn nicht stimmt, diese vertauschen
Dies könnte z. B. so aussehen:
public void bubbleSort(int[] ar) {
int arLength = ar.length;
boolean match = false;
for (int i = 0; i < arLength - 1 && !match; i++) {
match = true;
for (int j = arLength - 1; j > i; j--) {
if (ar[j-1] > ar[j]) {
swap(ar, j-1, j);
match = false;
}
}
}
}
Mehr ist für einen Bubblesort nicht nötig. Testen können Sie Ihren Code bspw. mit folgender main-Methode:
public static void main(String[] args) {
int[] ar = {234,1,32,-14,6382,3,453,23,-423,0,43,1,2};
new Sorter().bubbleSort(ar);
for (int i = 0; i < ar.length; i++) {
System.out.println(ar[i]);
}
}
Zusammenfassung:
public class Sorter {
public void bubbleSort(int[] ar) {
int arLength = ar.length;
boolean match = false;
for (int i = 0; i < arLength - 1 && !match; i++) {
match = true;
for (int j = arLength - 1; j > i; j--) {
if (ar[j-1] > ar[j]) {
swap(ar, j-1, j);
match = false;
}
}
}
}
private void swap(int[] ar, int pos1, int pos2) {
int temp = ar[pos1];
ar[pos1] = ar[pos2];
ar[pos2] = temp;
}
}
Kommentar verfassen