Bubblesort
Geht die Liste immer wieder durch und tauscht Nachbarn, die falsch herum stehen. Nach jedem Durchgang steht der größte übrige Wert am Ende.
- bester Fall Ω(n)
- Durchschnitt Θ(n²)
- schlechtester Fall O(n²)
- Speicher O(1)
- stabil
- ohne Zusatzspeicher
Was bedeutet das?
- Bester Fall: wie die Zeit mit der Listengröße n wächst, wenn die Eingabe für diesen Algorithmus am einfachsten ist.
- Durchschnitt: das übliche Wachstum der Zeit mit n. Bei n² dauern doppelt so viele Werte etwa viermal so lang. n log n wächst viel langsamer.
- Schlechtester Fall: das Wachstum bei der schwierigsten Eingabe. Wichtig, wenn das Tempo nie einbrechen darf.
- Speicher: wie viel Zusatzspeicher neben der Liste nötig ist. 1 heißt ein paar Variablen, n heißt eine Kopie der Liste.
- Stabil: Zwei gleiche Werte behalten ihre ursprüngliche Reihenfolge. Wichtig, wenn man Datensätze nach einem Feld sortiert.
- Ohne Zusatzspeicher: sortiert direkt in der Liste, ohne zweite Liste.
- wird verglichen
- wird verschoben
- am endgültigen Platz
Auf Abspielen drücken: Die Linien zeigen, wie die Kosten wachsen
Auf Abspielen drücken oder Schritt für Schritt durchgehen.
Leertaste: abspielen oder pausieren. Pfeiltasten links/rechts: Schritt. Pos1 und Ende: springen.
Probieren Sie es aus: Wählen Sie eine fast sortierte Liste. Nach einem Durchgang ohne Tausch hört der Algorithmus früh auf.
So funktioniert es
Es vergleicht immer zwei Nachbarn und tauscht sie, wenn der linke größer ist. So wandert in jedem Durchgang der größte Wert ganz nach rechts, wie eine aufsteigende Blase. Gibt es in einem Durchgang keinen Tausch, ist die Liste schon sortiert.
Wann es sich eignet
In echten Programmen fast nie, denn bei langen Listen ist es langsam. Zum Lernen ist es aber ideal: Es zeigt die Grundidee, durch Vergleichen und Tauschen zu sortieren. Schnell ist es nur bei einer schon sortierten Liste.