Bubblesort
Erklärvideos
Fachbegriffe
Laufzeit, Bubblesort, Array, Index, Durchlauf, Tauschen, Nachfolger
Beschreibung des Verfahrens
Die Erläuterungen sind aus Wikipedia; vgl. [Wikipedia-Bubblesort]
In der Bubble-Phase wird die Eingabe-Liste von links nach rechts durchlaufen. Dabei werden in jedem Schritt das aktuelle Element mit dem rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie getauscht. Am Ende der Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.
Die Bubble-Phase wird solange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.
Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt, an das Ende der Liste. Auch werden immer zwei Zahlen miteinander in „Bubbles“ vertauscht.
Laufzeit
im average case und im worst case: O(n2)
Implementierung für Arrays
Bubblesort ist das Sortierverfahren, das für Arrays am leichtesten zu implementieren ist - noch leichter als Insertionsort oder Selectionsort. Bubblesort geht auf Arrays wie folgt vor:
- Das Array wird (n-1)mal durchlaufen.
- Bei jedem Durchlauf wird von vorne nach hinten durch das Array gegangen.
- Wenn dabei ein Element größer ist als sein Nachfolger, dann tauschen die beiden die Plätze.
Implementierung mit mehreren Methoden
In dieser Implementierung wird der Algorithmus in drei Methoden zerlegt. Es werden hier zwei verschiedene Szenarien dargestellt:
- Sortieren eines Arrays, das nur Zahlen enthält
- Sortieren eines Arrays, das Objekte enthält
Bubblesort für ein Array, das Zahlen enthält
private int[] zahlen = {3, 7, 2, 9, 1, 8};
private void tausche(int index1, int index2) {
int z1 = zahlen[index1];
int z2 = zahlen[index2];
zahlen[index1] = z2;
zahlen[index2] = z1;
}
private void durchlauf() {
for (int i = 0; i < zahlen.length-1; i++) {
//Nachbarn vergleichen
if(zahlen[i] > zahlen[i+1]) {
// ggf. tauschen
// als Parameter werden die INDICES uebergeben,
// d.h. die POSITIONEN der zu tauschenden Zahlen!
tausche(i, i+1);
}
}
}
public void bubblesort() {
for (int i = 0; i < zahlen.length-1; i++) {
durchlauf();
}
}
Bubblesort für ein Array, das Objekte enthält
Das Array enthält Objekte vom Typ Person.
Das Array wird gemäß der alphabetischen Reihenfolge des Namens der Person sortiert.
// Sorgt dafuer, dass die Personen bei Index i1 und bei Index i2
// die Plaetze tauschen.
private void tausche(Person[] personen, int i1, int i2){
Person p1 = personen[i1];
Person p2 = personen[i2];
personen[i1] = p2;
personen[i2] = p1;
}
private void durchlauf(Person[] personen) {
// durch das ganze Array gehen
for (int i = 0; i < personen.length-1; i++) {
// Element mit dem Nachfolger vergleichen
if(personen[i].istAlphabetischNach(personen[i+1])){
// Plaetze tauschen
tausche(personen, i, i+1);
}
}
}
public void bubblesort(Person[] personen){
// (n-1)mal durchlaufen!
for (int i = 0; i < personen.length-1; i++) {
durchlauf(personen);
}
}
Implementierung in einer Methode
Die Implementierung in einer Methode wird an einem Array mit int-Zahlen demonstriert.
public void bubblesort(int[] pArray) {
for(int i=0; i<pArray.length-1; i++) {
for(int j=0; j<pArray.length-1; j++) {
if(pArray[j] > pArray[j+1]){
int zahl0 = pArray[j];
int zahl1 = pArray[j+1];
pArray[j] = zahl1;
pArray[j+1] = zahl0;
}
}
}
}