Bubblesort

Du verwendest Computer zur Informationsverarbeitung. Die Basiselemente sind seit langer Zeit noch immer die gleichen: Eingabe, Ausgabe und Verarbeitung (das EAV Modell). Besonders häufiger Anwendungsfall: Daten sortieren. Ganz unabhängig von der jeweiligen Programmiersprache gibt es dafür verschiedene Lösungen. Du lernst heute die einfachste Methode kennen: den Bubblesort Sortieralgorithmus.

Was ist ein Algorithmus?

Das Wort Algorithmus ist Dir vielleicht schon einmal begegnet? Die gibt es in ganz unterschiedlicher Ausprägung. Sehr prominent sind die Bereiche Verschlüsselung, Komprimierung (z.B. ZIP) und eben die Sortierung. Auch für die Lösung von einem sehr bekannten Kinderspielzeug, dem Rubikscube, gibt es Algorithmen.

Und um was genau handelt es sich? Ein Algorithmus ist einfach eine festgelegte Abfolge von Schritten. Sie lösen ein bestimmtes Problem oder eine konkrete Aufgabe. Ganz wichtig: Ein Algorithmus ist nicht an eine bestimmte Sprache gebunden. Du kannst z.B. Bubblesort in ganz vielen unterschiedlichen Programmiersprachen implementieren. In diesem Artikel findest Du weiter unten eine Beispiel. Das habe ich mit Swift umgesetzt.

Darstellung von Bubblesort

Um Algorithmen zu dokumentieren gibt es zwei Wege. Grafisch werden dazu Programmablaufpläne verwendet. Dort werden Bedingungen, Aktionen, Start/Stop und so weiter grafisch dargestellt. Von oben nach unten gelesen ergibt sich der Programmablauf. Daher der Name. Mehr Informationen zu dem Thema findest Du in dem Artikel zu Programmablaufplänen von Wikipedia.

Hier eine grafische Aufbereitung des Bubblesort Algorithmus:

bubblesort

Das sieht zunächst mal ziemlich abgefahren aus. Zugegeben. Im Kern ist es aber einfach.

Die Arbeitsweise von Bubblesort

Hier die Arbeitsweise von Bubblesort, geschrieben als Fließtext. Ich beschreibe Schritt für Schritt das gezeigte Diagramm. Im wesentlichen sind es jeweils 3 Bereiche die unterschiedlich oft ausgeführt werden. Los geht’s:

Bei dem oben gezeigten Algorithmus handelt es sich um eine Funktion. Die trägt den Namen „Bubble Sort“. Als Parameter übergibst Du ein Array mit ungeordneten Integerwerten. Genau dies willst Du in aufsteigender Reihenfolge sortieren. Genau das stellen die ersten beiden Elemente dar.

Äußere Schleife

Den Anfang der eigentlichen Logik macht der hellgraue Kasten. Das ist der Funktionskörper. Zuerst wird der Startwert für den Schleifenzähler (i) gesetzt. Der Wert ergibt sich aus Anzahl der Elemente im Array minus eins (n ist die Anzahl der Elemente), da Arrays nicht bei 1 sondern 0 beginnen.

Die äußere Schleife nutzt „i“ als Zähler. Sie läuft bis der Wert 0 ist. Dann wird die Bedingung „i > 0“ nicht erfüllt. Die Bedingung ergibt „false“. Das führt zum Programmende.

Merke: Das übergebene Array wird von hinten nach vorne durchgearbeitet. Der Startwert ist das letzte Element im Array. Nach jedem Schleifendurchlauf wird der Zähler mittels „i–“ um den Wert 1 verringert.

Innere Schleife

Der etwas dunklere graue Kasten rückt in den Fokus. Innerhalb der äußeren Schleife gibt es eine weitere Schleife – die innere Schleife. Sie wird bei jedem Schleifendurchlauf der äußeren Schleife ausgeführt und nutzt den Zähler „k“. Der Wert wird am Anfang auf 0 gesetzt. Sie läuft durchläuft alle Elemente vom Anfang des Arrays bis zur aktuellen Position der äußeren Schleife.

In jedem Durchlauf der inneren Schleife führst Du schließlich den entscheidenden Vergleich aus. Nur wenn Du die Werte miteinander vergleichst, kannst Du sie auch sortieren. Über „array[k]“ greifst Du auf das aktuelle Element zu, über „array[k+1]“ auf das nächste. Du vergleichst also die Zahl an der jeweiligen Position mit der rechts daneben. Wenn die aktuelle Zahl größer ist als der Nachbar, wird getauscht.

Der Tausch

Die Sortierung erfolgt Element für Element. Fall1: die Bedingung in der inneren Schleife zutrifft. Das Element weiter vorn ist größer als der Nachbar weiter hinten in der Liste. Wir möchten aber eine aufsteigende Sortierung: kleinste Zahl zuerst, größte zuletzt. Also: Die Elemente müssen vertauscht werden.

Das funktioniert über eine Hilfsvariable temp. Du „merkst“ Dir den alten Wert darin. Dann kannst Du das Nachbarlement (aktuelle Position + 1) im jetzigen Element speichern. Den Wert aus „temp“ legst Du dann im benachbarten Element ab.

Sortieralgorithmus mit Swift umsetzen

Die Implementierung ist mit nahezu jeder Sprache möglich. Ich habe mich einfach an dieser Stelle für Swift entschieden. So kannst Du es sogar in einem Playground direkt selbst nachvollziehen.

Hinweis: Die Schleifenzähler werden nicht – wie in der Grafik – gesondert deklariert. Das geschieht direkt im Schleifenkopf. Auch inkrementieren und dekrementieren der Schleifenzähler übernimmt die for-Schleife.

Laufzeit der Sortierung

Bei Sortieralgorithmen kann die Anzahl der benötigten Ausführungen berechnet werden. Je mehr Durchläufe, desto langsamer der Algorithmus. Ich will hier gar nicht näher auf die notwendige Berechnung eingehen. Dazu empfehle ich bspw. den Wikipedia-Artikel zu Bubblesort. Viel wichtiger:

Bubblesort ist langsam. Die Anzahl der maximal notwendigen Ausführung ist die Menge der Elemente zum Quadrat, also n2. Je mehr Elemente, desto mehr Ausführungen. Das wächst linear mit:

  • 4 Elemente, max. 16 Durchläufe
  • 400 Elemente, max. 160000 Durchläufe
  • 4000 Elemente, max. 16000000 Durchläufe

Vorsichtig ausgedrückt: Es kommt schnell einiges zusammen.

Vorteile von Bubblesort

Warum solltest Du Dich überhaupt dafür interessieren? Scheinbar ist es ja ziemlich langsam. Stimmt. Aber: Bei kleinen Datenmengen ist der Sortieraufwand gering. Somit ist der Algorithmus nicht vollkommen nutzlos. Außerdem kannst Du ihn vergleichsweise einfach umsetzen. Noch wichtiger: Es ist eine ganz tolle Übung für Einsteiger. Es ist durchaus etwas Brainpower nötig, um komplett durchzusteigen. Aber genau solche Übungen bringen Dich in Deiner Entwicklung vorwärts. Und genau deshalb gibt es auch diesen Artikel.

Alternative Ansätze

Es gibt in der Tat deutlich effizientere Sortieralgorithmen. Den einen oder anderen Stelle ich separat noch einmal vor. Mögliche Alternativen sind bspw. Binary Tree Sort, Heapsort, Mergesort oder auch Quicksort. Eine etwas umfangreichere Liste mit Sortierverfahren findest Du bei Wikipedia.

Fazit

Bubblesort ist ein gelungener Einstieg in die gesamte Thematik.  Du kannst auch praktischen Nutzen daraus ziehen: In der Praxis ist er mindestens für kleinere Datenmengen perfekt. Noch wichtiger: Die Arbeit mit solchen Logiken führt Dich näher an die Programmierung. Experimentier einfach damit, versuch Schritt für Schritt zu verstehen was passiert. Eine mögliche Übungsaufgabe. Ändere die Sortierung in absteigende Reihenfolge. Die größte Zahl wird zuerst, die kleinste zuletzt ausgegeben.

Kommentare (2)

  • Nero689

    3 Jahren ago

    Ich muss schon sagen, deine Themen sind wirklich super erklärt, ich als Einsteiger verstehe sehr vieles davon und das motivert mich weiterzumachen.

    Bitte mach weiter so!

    • Jan Brinkmann

      3 Jahren ago

      Hey, vielen Dank für den lieben Kommentar! Schön wenn es verständlich ist! Wenn das allgemein interessant ist, mixe ich gern auch einfach mal solche Themen als Inspiration für die weitere Beschäftigung mit ein 🙂

Leave a Comment to Jan Brinkmann Cancel reply

Your email address will not be published.