Wie funktioniert der bubble sort Algorithmus?
Kann jemand mal erklären wie bubble sort funktioniert? Warum gibt es ihn wenn er doch uneffektiv ist?
2 Antworten
Bubblesort ist ein einfacher Sortieralgorithmus, der durch Vergleiche und Vertauschen benachbarter Elemente eine Liste sortiert. Der Algorithmus arbeitet, indem er die Liste mehrmals durchläuft, in jeder Iteration benachbarte Elemente vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge sind. Dieser Prozess wird so lange wiederholt, bis die gesamte Liste sortiert ist.
Hier ist eine einfache Beschreibung des Bubblesort-Algorithmus:
- Beginne mit dem ersten Element der Liste.
- Vergleiche das aktuelle Element mit seinem Nachbarn.
- Wenn das aktuelle Element größer ist als sein Nachbar, vertausche sie.
- Fahre mit dem nächsten Element fort und wiederhole die Schritte 2-3 bis zum Ende der Liste.
- Die obigen Schritte werden so lange wiederholt, bis keine Vertauschungen mehr notwendig sind.
Vorteile sind die Einfachheit und der geringe Speicherbedarf.
Eine Zahlenreihe sei gegen. Der Einfachheit halber schreiben wir die Zahlenreihe nebeneinander. Dabei wird in jederm Sortierschritt das aktuell betrachtete Element mit dem rechten Nachbarn verglichen. Falls bei diesem Vergleich die beiden Elemente das Sortierkriterium verletzen (Zahl links ist kleiner, als...), werden sie getauscht. Das tut man in mehreren Durchläufen, bis kein Tausch mehr ausgeführt werden muss. Am Ende steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.
Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser immer weiter nach oben, das heißt, an das Ende der Liste. Es werden stets zwei Zahlen miteinander in „Bubbles“ vertauscht.
Die Ineffizienz liegt darin, dass im Durchschnitt die Dauer einer einzigen Sortiersequenz linear steigt mit der Anzahl der Elemente, um am Ende ein Vergleichsdurchgang nur zur Kontrolle gefahren werden muss. Defacto eignet er sich im besten Fall für Listen/Reihen, die schon stark in der gewünschten Reihenfolge sortiert sind.