Was ist bubblesort?

Bubblesort

Bubblesort ist ein einfacher Sortieralgorithmus, der wiederholt durch eine Liste geht, benachbarte Elemente vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge sind. Dieser Prozess wird wiederholt, bis keine Vertauschungen mehr nötig sind, was bedeutet, dass die Liste sortiert ist.

Funktionsweise:

1. Der Algorithmus beginnt am Anfang der Liste.
2. Er vergleicht das erste und das zweite Element.
3. Wenn das erste Element größer als das zweite ist, werden sie vertauscht.
4. Dann wird das zweite und das dritte Element verglichen, und gegebenenfalls vertauscht.
5. Dieser Prozess wird für jedes Paar benachbarter Elemente bis zum Ende der Liste fortgesetzt.
6. Am Ende der ersten Durchlauf befindet sich das größte Element am Ende der Liste.
7. Der Algorithmus wiederholt dann den gesamten Prozess, beginnend am Anfang der Liste, aber dieses Mal bis zum vorletzten Element (da das letzte Element bereits an der richtigen Position ist).
8. Dieser Vorgang wird so lange wiederholt, bis keine Vertauschungen mehr vorgenommen werden.

Eigenschaften:

• Einfachheit: Bubblesort ist leicht zu verstehen und zu implementieren.
• Ineffizienz: Bubblesort ist ineffizient für große Datensätze. Seine https://de.wikiwhat.page/kavramlar/Zeitkomplexität%20von%20Bubblesort ist O(n^2) im durchschnittlichen und schlimmsten Fall, was bedeutet, dass die Laufzeit quadratisch mit der Anzahl der zu sortierenden Elemente steigt. Im besten Fall (wenn die Liste bereits sortiert ist) beträgt die Zeitkomplexität O(n).
• In-Place Sortierung: Bubblesort ist ein https://de.wikiwhat.page/kavramlar/In-Place%20Sortieralgorithmus, d.h. er benötigt keinen zusätzlichen Speicherplatz (außer für temporäre Variablen zum Vertauschen von Elementen).
• Stabil: Bubblesort ist ein https://de.wikiwhat.page/kavramlar/stabiler%20Sortieralgorithmus, d.h. die relative Reihenfolge gleicher Elemente bleibt erhalten.

Anwendungsbereiche:

Aufgrund seiner Ineffizienz wird Bubblesort in der Praxis selten für große Datensätze verwendet. Es eignet sich eher für kleine Datensätze oder zu Lehrzwecken, um die Grundlagen von Sortieralgorithmen zu vermitteln.

Pseudocode:

function bubblesort(array)
  n = Länge(array)
  repeat
    swapped = false
    for i = 1 to n-1 do
      if array[i] > array[i+1] then
        swap(array[i], array[i+1])
        swapped = true
      end if
    end for
    n = n - 1
  until not swapped
end function