Bubblesort

Der Bubblesort, oder auch Austauschsortieren, ist eines der einfacheren Sortierverfahren. Die Liste der zu sortierenden Elemente wird dabei mehrfach von links nach rechts durchlaufen und die einzelnen Elemente mit den Nachbarn verglichen.

Elemente, die größer als ihr Nachfolger sind, werden getauscht. Das Bubblesort-Verfahren wird so lange wiederholt, bis in einem Durchlauf keine Elemente mehr vertauscht werden und die Datenmenge damit fertig sortiert ist.

Damit ist Bubblesort zwar sehr einfach zu verstehen, dafür aber auch recht langsam: Im durchschnittlichen Fall liegt die Laufzeit in O(n^2). Im besten Fall hat Bubblesort allerdings eine Laufzeit von O(n). Damit zählt der Algorithmus zu den natürlichen Sortierverfahren. Zudem ist Bubblesort stabil und kann in-place durchgeführt werden.

Eigenschaften von Sortierverfahren in der Informatik

Sortierverfahren bzw. -algorithmen sind in der Informatik ein großes Thema. Insbesondere in Zeiten von Big Data ist es wichtig, Datenmengen schnell und effizient in eine Ordnung bringen zu können. Mittlerweile haben sich viele Algorithmen von unterschiedlicher Komplexität und Laufzeit etabliert. Bubblesort ist eines der einfacheren, aber dafür auch langsameren, Verfahren.

Es gibt verschiedene Eigenschaften nach denen Sortierverfahren eingeteilt werden können. Der erste und wahrscheinlich wichtigste Aspekt ist die Laufzeit. Die schnellste durchschnittliche Laufzeit liegt in O(n log n), wobei n die Anzahl der zu sortierenden Elemente bezeichnet. Daneben kann ein Verfahren stabil oder instabil, in-place oder out-of-place und natürlich oder unnatürlich sein.
Unter Stabilität versteht man die Eigenschaft, dass die relative Reihenfolge gleicher Elemente unter den Datenmengen nicht verändert wird. Befindet sich in einer Liste aus Zahlen beispielsweise mehrfach die Zahl 2, so ist die in den unsortierten Daten erste 2 auch nach dem Sortieren noch die erste. In-Place hingegen bedeutet, dass das Sortieren direkt auf den Daten stattfindet und somit kein weiterer Speicherplatz in Abhängigkeit der zu sortierenden Elemente benötigt wird.

Natürlich und unnatürlich schlussendlich unterscheidet, ob der Algorithmus besser auf bereits vorsortieren Listen arbeitet oder nicht.

Bubblesort in der Praxis

Durch seine suboptimale Laufzeit hat Bubblesort nur begrenzt praktische Anwendung.

Die konstanten Faktoren der Laufzeit, die in der Abschätzung meist entfallen, aber in der Praxis relevant sind, sind bei Bubblesort allerdings relativ klein.

Daher kann das Bubblesort-Verfahren für kleine oder bereits vorsortierte Datenmengen verwendet werden. Außerdem wird der Algorithmus aufgrund seiner Einfachheit gerne genutzt, um in der Ausbildung oder im Studium an Sortierverfahren heranzuführen.