Bubble Sort Algorithmus erklärt

Hier sind die aktualisierten Lernnotizen:

• Bubble Sort (Blasensortierung) ist ein einfacher, vergleichsbasierter Sortieralgorithmus.
• Er durchläuft die Liste wiederholt, vergleicht benachbarte Elemente und tauscht sie, wenn sie in der falschen Reihenfolge sind.
• Der Durchlauf durch die Liste wird so lange wiederholt, bis keine Vertauschungen mehr erforderlich sind, was bedeutet, dass die Liste sortiert ist.
• Es ist bekannt für seine Einfachheit, aber ineffizient für große Listen.
• Bubble Sort hat eine Zeitkomplexität von O(n^2) im durchschnittlichen und schlechtesten Fall und O(n) im besten Fall (wenn die Liste bereits sortiert ist).
• Es ist nach der Art und Weise benannt, wie kleinere Elemente an die Spitze der Liste "aufsteigen".
• Bubble Sort ist ein In-Place-Sortieralgorithmus, d. h. er benötigt keinen zusätzlichen Speicherplatz über den von der Eingabeliste belegten Speicherplatz hinaus.
• Es ist ein stabiler Sortieralgorithmus, d. h. Elemente mit dem gleichen Wert behalten ihre relative Reihenfolge in der sortierten Ausgabe bei.

Algorithmus

• Beginne am Anfang der Liste.
• Vergleiche die ersten beiden Elemente.
• Wenn das erste Element größer als das zweite Element ist, vertausche sie.
• Gehe zum nächsten Paar benachbarter Elemente und wiederhole den Vergleich und die Vertauschung, falls erforderlich.
• Setze diesen Prozess bis zum Ende der Liste fort.
• Nach dem ersten Durchgang befindet sich das größte Element an seiner korrekten Position am Ende der Liste.
• Wiederhole den Vorgang für den verbleibenden unsortierten Teil der Liste.
• Jeder Durchgang platziert das nächstgrößere Element an seiner korrekten Position.
• Fahre fort, bis keine Vertauschungen mehr erforderlich sind, was anzeigt, dass die Liste sortiert ist.

Pseudocode

• procedure bubbleSort(list : array of sortable items)
• n = length(list)
• repeat
  • swapped = false
  • for i = 1 to n-1 inclusive do
    • if list[i-1] > list[i] then
      • swap(list[i-1], list[i])
      • swapped = true
    • end if
  • end for
  • n = n - 1
• until not swapped
• end procedure

Optimierter Bubble Sort

• Eine Variante von Bubble Sort beinhaltet eine Prüfung, ob während eines Durchgangs Vertauschungen stattgefunden haben.
• Wenn keine Vertauschungen stattfinden, bedeutet dies, dass die Liste bereits sortiert ist und der Algorithmus vorzeitig beendet werden kann.
• Diese Optimierung verbessert die Best-Case-Zeitkomplexität auf O(n), wenn die Eingabeliste bereits sortiert ist.
• Es verfolgt den Index der letzten Vertauschung, die während eines Durchgangs vorgenommen wurde.
• Elemente jenseits dieses Index befinden sich bereits an ihren korrekten Positionen, wodurch die Anzahl der Vergleiche in nachfolgenden Durchgängen reduziert wird.

Optimierter Pseudocode

• procedure bubbleSort(list : array of sortable items)
• n = length(list)
• repeat
  • newn = 0
  • for i = 1 to n-1 inclusive do
    • if list[i-1] > list[i] then
      • swap(list[i-1], list[i])
      • newn = i
    • end if
  • end for
  • n = newn
• until n <= 1
• end procedure

Komplexität

• Zeitkomplexität:
  • Bester Fall: O(n), wenn die Liste bereits sortiert (oder fast sortiert) ist und die optimierte Version verwendet wird.
  • Durchschnittlicher Fall: O(n^2).
  • Schlechtester Fall: O(n^2), wenn die Liste in umgekehrter Reihenfolge ist.
• Speicherkomplexität: O(1), da Bubble Sort ein In-Place-Sortieralgorithmus ist, der nur eine konstante Menge an zusätzlichem Speicher für temporäre Variablen benötigt.

Anwendungsfälle

• Bubble Sort wird in der Praxis aufgrund seiner schlechten Leistung bei großen Datensätzen selten verwendet.
• Es wird hauptsächlich für Bildungszwecke verwendet, um die grundlegenden Prinzipien von Sortieralgorithmen zu veranschaulichen.
• Es kann für das Sortieren kleiner Datensätze oder wenn bekannt ist, dass die Eingabeliste fast sortiert ist, nützlich sein.
• Es kann in Situationen verwendet werden, in denen Einfachheit und einfache Implementierung wichtiger sind als Leistung.

Vorteile

• Einfach zu verstehen und zu implementieren.
• Einfach zu erkennen, ob die Liste bereits sortiert ist (optimierte Version).
• In-Place-Sortieralgorithmus, der minimalen zusätzlichen Speicherplatz benötigt.
• Stabiler Sortieralgorithmus, der die relative Reihenfolge gleicher Elemente beibehält.

Nachteile

• Ineffizient für große Listen.
• Quadratische Zeitkomplexität im durchschnittlichen und schlechtesten Fall macht es für große Datensätze unpraktisch.
• Andere Sortieralgorithmen, wie Merge Sort oder Quicksort, bieten eine deutlich bessere Leistung.

Vergleichssortierung

• Vergleichssortieralgorithmen sortieren eine Liste, indem sie Paare von Elementen vergleichen.
• Bubble Sort ist ein Vergleichssortieralgorithmus.
• Weitere Beispiele für Vergleichssortieralgorithmen sind:
  • Insertion Sort (Einfügesortierung)
  • Selection Sort (Auswahlsortierung)
  • Merge Sort (Mischsortierung)
  • Quicksort
  • Heap Sort (Heap-Sortierung)
• Die Zeitkomplexität jedes Vergleichssortieralgorithmus ist durch Ω(n log n) begrenzt.
• Nicht-Vergleichssortierungen, wie Counting Sort (Zählsortierung) und Radix Sort (Radixsortierung), können bessere Zeitkomplexitäten durch die Verwendung von Informationen über die zu sortierenden Elemente erreichen, anstatt sie nur zu vergleichen.