Sortieralgorithmen/ Bubblesort
Bei dem Sortierverfahren Bubblesort nehmen wir eine Zahlenreihe als Beispiel. In diesem Sortierverfahren nimmt man zuerst die erste Zahl und vergleicht diese mit der zweiten. Ist diese erste Zahl größer, als die zweite, tauscht sie mit der zweiten Zahl den Platz. Ist sie jedoch kleiner, bleibt sie stehen.
Wenn sie den Platz tauscht, wird nun verglichen, ob die Zahl auch größer, als die an dritter Stelle stehende Zahl ist.
Wenn ja, dann tauscht sie auch mit dieser den Platz. So geht es weiter, bis entweder die erste Zahl an letzter Stelle steht, oder sie kleiner als eine mit ihr verglichene Zahl ist.
Ist sie kleiner, beginnt das Verfahren von vorne, nur diesmal mit der Zahl die größer, als unsere erste Zahl ist. Ist eine Zahl größer, als alle anderen und steht an letzter Stelle, wird diese als sortiert eingestuft und das Verfahren beginnt auch wieder neu, dieses mal nur mit der jetzt am Anfang stehenden Zahl.
Die Elemente werden so häufig durchsortiert, wie es Elemente in der zu sortierenden Liste gibt. Der Name Bubblesort kommt daher, dass die großen Elemente wie Luftblasen im Wasser, also bubbles, sozusagen nach oben steigen bzw. an den rechten Rand der Reihe rücken. Man nennt es deshalb auch sortieren durch Aufsteigen. (5) Bubblesort arbeitet in-place. Es ist ein Sortierverfahren, welches stabil ist. Das bedeutet, dass zwei gleiche Elemente ihre Plätze in der Reihe nicht vertauschen. Dieses Sortierverfahren werde ich jetzt an einem Beispiel bildhaft darstellen. In einer Bibliothek werden die Bücher nach der Seitenanzahl sortiert. Es sollen fünf Bücher sortiert werden.
Das erste (A) Buch hat 203 Seiten, das zweite (B) 194, das dritte (C) 1001 Seiten, das vierte (D) Buch hat nur 80 Seiten und das fünfte (E) Buch hat 160 Seiten.
Die Bücher sollen nach Seitenzahlen aufsteigend sortiert werden. Die Bibliothekarin nimmt das erste Buch und vergleicht es mit dem zweiten. Da das zweite Buch weniger Seiten als das erste hat, vertauscht sie die beiden. Nun nimmt sie das zweite Buch und vergleicht es mit dem dritten. Da das dritte mehr Seiten, als das jetzige zweite (A) hat, bleibt alles wie es war und sie vergleicht als nächstes das dritte mit dem vierten Buch und vertauscht beide miteinander, da das dritte mit 1001 mehr Seiten als das vierte hat. Im nächsten Schritt vergleicht sie das vierte (C) mit dem fünften Buch da das vierte mehr Seite hat und es kein sechstes Buch gibt, stellt die Bibliothekarin es ganz hinten in den Schrank, da es nun fertig sortiert ist. Die Bücher sind nun in der Reihenfolge B, A, D, E. Jetzt nimmt die Bibliothekarin wieder das erste Buch und vergleicht es mit dem zweiten. Da die Reihenfolge stimmt, nimmt sie das zweite Buch (A) und vergleicht es mit dem dritten (D). Da das zweite mehr Seiten als das dritte hat, vertauscht sie beide. Im nächsten Schritt vergleicht sie das nun dritte (A) mit dem vierten Buch (E). Da das dritte mehr Seiten hat und das fünfte Buch schon fertig sortiert ist stellt sie das vierte Buch (A) auch in den Schrank, so dass es nun vor dem fünften an vorletzter Position steht. Jetzt gibt es nur noch drei zu sortierende Bücher in dieser Reihenfolge B, D, E. Die Bibliothekarin nimmt wieder das erste Buch (B) und vergleicht es mit dem zweiten. Da es mehr Seiten hat vertauscht sie beide und vergleicht nun das zweite (B) mit dem dritten Buch. Da das zweite auch hier mehr Seiten hat, tauschen beide die Plätze und da es kein viertes Buch, gibt kann die Bibliothekarin auch dieses Buch in das Regal stellen. Zum Schluss vergleicht sie die beiden letzten Bücher und stellt auch diese ins Regal. Nun haben wir im Regal folgende Reihenfolge: D, E, B, A, C.
In der Praxis wird Bubblesort leider fast nicht verwendet, da es eine nicht so gute Laufzeit hat. Auch das kann man an meinem Beispiel gut sehen, da keine Bibliothekarin ihre Bücher auf diese Weise sortieren würde. Aber in der Lehre wird Bubblesort trotzdem gerne benutzt weil es sich leicht und beispielhaft erklären lässt.