Bubblesort ist das wohl am einfachsten zu implementierende Sortierverfahren. Es ist jedoch zu ineffektiv um es praktisch einzusetzen und hat daher nur einen geringen Stellenwert.
Der Bubblesort-Algorithmus geht Element für Element einzeln durch und prüft ob das aktuelle Element kleiner ist als dessen Vorgänger. Ist dies der Fall, dann werden beide Elemente miteinander vertauscht und es wird zum nächsten Element gesprungen. Ist das Feld dabei einmal durchlaufen worden beginnt der Algorithmus von neuem. Dies geschieht so lange, bis bei einem Durchlauf kein Element mehr vertauscht worden ist. Maximal jedoch n-1 mal, da praktisch gesehen bei jedem Durchlauf das nächst großere Element seine Endposition erreicht. Dies ist auch der Grund warum nach jedem Durchlauf das letzte Element nicht mehr überprüft werden muss.
public class BubbleSort {
public static <T extends Comparable<T>> void sort(T[] source) {
for (int j = 0; j < source.length - 1; j++) {
boolean change = false;
for (int i = 1; i < source.length - j; i++) {
if (source[i-1].compareTo(source[i]) > 0) {
T temp = source[i];
source[i] = source[i-1];
source[i-1] = temp;
change = true;
}
}
if (!change) return;
}
}
}
Komplexität
| Best | Average | Worst |
| O(n) | O(n²) | O(n²) |