Bubblesort

Bubblesort ist ein primitiver Sortieralgorithmus, der nebeneinander liegende Elemente vergleicht und ggf. vertauscht, falls sie in der falschen Reihenfolge vorliegen. Je nachdem ob auf- oder absteigend sortiert wird, steigen die kleineren oder größeren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, d.h. an den Anfang der zu sortierenden Liste.

Der Algorithmus besitzt eine quadratische und daher im Vergleich zu anderen Sortieralgorithmen eher schlechte Worst-Case-Laufzeit, Informatiker notieren dies mittels Landau-Symbol durch $O(n^{2})$. Trotz der theoretisch schlechten Laufzeit findet er Anwendung in der Abbruchbedingung rekursiver Sortieralgorithmen wie QuickSort oder MergeSort, da er für eine sehr kleine Anzahl an zu sortierenden Elementen schneller ist als fortgesetzte rekursive Funktionsaufrufe.

Beispielimplementation in Java:

public static int[] bubblesort(int[] tosort) {

  if(tosort.length < 2) { // Bei weniger als 2 Elementen
    return tosort;        //  muss nicht sortiert werden
  }

  int switches = -1; //Anzahl der Vertauschungen
  int tmp;           //Temporaere Variable zum tauschen.

  while(switches != 0) {
    switches = 0;
    for(int i = 0; i<tosort.length-1; i++) {
      if(tosort[i] > tosort[i+1]) {
        tmp = tosort[i+1];
        tosort[i+1]=tosort[i];
        tosort[i]=tmp;
        switches++;
      }
    }
  }

  return tosort;
}

siehe auch: Liste von Algorithmen