Bubblesort

Bubblesort ist ein Sortieralgorithmus und arbeitet wie folgt:

Gegeben: Liste A der Länge n.

• Falls n < 2: A ist sortiert, brich ab. Ansonsten…
• Wiederhole n-1 Mal:
  • Gehe von A[0] bis A[n-2] durch
  • Betrachte jeweils ein Element und seinen rechten Nachbarn (also A[i] und A[i+1])
  • Falls A[i] > A[i+1], vertausche die beiden
• Danach ist die Liste sortiert, gib die sortierte Liste als Ergebnis zurück

Laufzeit

Eine Liste mit $n$ Elementen muss $n-1$ Mal durchgegangen werden und bei jedem Durchgang werden $n-1$ Vergleiche angestellt. Insgesamt sind das $(n-1)^{2}$ Vergleiche. Damit bewegt sich die Laufzeit in ${\mathcal {O}}(n^{2})$.

Weblinks

• Sortieralgorithmen auf VisuAlgo.net 🇬🇧 🇨🇳 🇮🇩
• Bubblesort getanzt 🇬🇧

Sortieralgorithmen

Bubblesort | Selectionsort | Insertionsort | Quicksort | Mergesort | Gnomesort