Veröffentlicht am Schreib einen Kommentar

Bubble Sort: Einen Algorithmus entwickeln

Algorithmus Enwicklen am Beispiel von Bubble Sort

Bubble Sort Algorithmus entwickeln

Wir entwickeln den Bubble Sort Algorithmus. Wir abstrahieren den intuitiven Ansatz mit Pseudocode und Aktivitätendiagram, implementieren in Python und Java und schließen ab mit der Laufzeitbetrachtung.

Dieses Schrittweise Vorgehen können wir für jede Art von Algorithmus anwenden. Oft liegt die Lösung ja nicht auf der Hand und wir tasten uns heran. Der Artikel zeigt, wie das geht.

Intuitiver Ansatz

Der intuitive Ansatz wird oft auch “naiv” ganannt. Das ist nicht abwertend gemeint, sondern bezeichnet den ersten Ansatz eines Algorithmus, der den meiste Leuten auf anhieb einfällt. Ausgehend von diesem naiven Ansatz wird der Algorithmus optimiert – oft ein langer Weg.

Hol dir auch das kostenlose E-Booklet über die Grundlagen der Algorithmen-Entwicklung. Dort werden die Elemente detailliert dargestellt und du findest noch mehr Übungsbeispiele.

Wir entwickeln den Bubble Sort. Dieser gilt als naiver Ansatz – also intuitiv fassbar – um beispielsweise Spielkarten zu sortieren. Am besten holst du ein paar Spielkarten oder etwas Vergleichbars, das du sortieren kannst.

Beobachte dich selbst:

  • Lege die Karten in einer beliebigen Reihenfolge auf den Tisch.
  • Sortiere sie, so wie du das immer machst.

Wie gehst du vor? Welches ist dein Verfahren? Beschreibe es mit einfachen Worten, so ähnlich wie wenn du eine Anleitung zum Karten sortieren schreiben würdest.

Bubble Sort zum Spielkarten sortieren

Wir haben ein kurzes Video gedreht, das zeigt, wie Spielkarten mit dem Bubbe Sort sortiert werden. Klick auf das +-Zeichen und schau dir das Video an.

Video Bubble Sort

Kannst du den Algorithmus des Bubble-Sort erkennen? Beschreibe ihn mit eigenen Worten.

Bubble Sort im Pseudocode

Pseudocode ist eine leicht formalisierte aber nicht standardisierte Art, um einen Algorithmus aufzuschreiben. Schreibe Pseudocode noch bevor du den Code in einer Programmiersprache aufschreibst. So gelingt es dir, Ordnung in die Gedanken zu schaffen und Strukturen zu erkennen. Mehr Beispiele in Pseudocode findest du im E-Booklet Grundlagen Algorithmen.

Klick aufs +-Zeichen und untersuche den Pseudocode zum Bubble Sort.

Beispiel Pseudocode für Bubble Sort

Der Einfachheit halber nummerieren wir die Schritte.

Die Einrückungen machen den Pseudocode übersichtlicher.

01 Wiederhole den folgenden Vorgang, bis du in einem Durchlauf von Schritt 02 bis 08 keine Vertauschung vornehmen musst:

02   Beginne links.

03   Wiederhole den folgenden Vorgang für die ganze Kartenreihe:

04     Vergleiche zwei nebeneinander liegende Karten.

05     Ist der Wert der Karte links größer als der Wert der Karte rechts?

06       dann vertausche die beiden Karten

07     betrachte die nächsten beiden Karten

08     fahre weiter bei Schritt 04

Erkennst du den Vorgang aus dem Video wieder?

Versuche mit Hilfe dieses Pseudocodes deine Spielkarten zu sortieren.

Bubble Sort als Aktivitätendiagramm

Das Aktivitätendiagramm ist eine Alternative zum Bubble-Sort. Beide Hilfsmittel dienen dazu, einen Algorithmus zu formulieren noch bevor wir diesen in einer Progammiersprache codieren.

Klicke erneut auf das +-Zeichen und untersuche das Aktivitätendiagramm zum Bubble Sort.

Beispiel Aktivitätendiagramm für Bubble Sort

Aktivitätendiagramme oder Flowcharts, sind eine weitere Möglichkeit, um eine Idee für einen Algorithmus zu skizzieren. Papier, Bleistift und Radiergummi sind völlig ausreichend.Bubblseort Aktivitätendiagramm

Versuche mit Hilfe des Aktivitätendiagramms deine Spielkarten zu sortieren.

Bubble Sort in Python

Haben wir den Algorithmus als Pseudocode oder Aktivitätendiagramm entwickelt, dann wollen wir diesen in einer Programmiersprache implementieren.

Wir nehmen hier Python – du kannst den Code auch gleich ausprobieren auf dem Python Playground.

Beispiel Python Code für Bubble Sort

Erinnere: Einrückungen sind in Python ein wichtiges Sprachelement. Wir haben auch im Pseudocode damit gearbeitet.

Wir können den Algorithmus schrittweise entwickeln. Das Vorgehen kannst du mit einer beliebigen Sprache nachvollziehen.

Zuerst benötigen wir eine geeignete Datenstruktur. Wir nehmen eine Python-Liste.

Und wir benötigen die Möglichkeit, auf ein einzelnes Element in der Liste mit Hilfe eines Indexes zuzugreifen.

Mit der Python-Funktion len() bestimmen wir die Länge der Liste. So können wir bestimmen, ob wir “ganz rechts” angelangt sind.

Das folgende Code-Snippet zeigt diese Python-Sprachelemente. Wir geben jedes Element der Liste auf einer Zeile aus.

liste = [6 ,5, 4, 3, 2, 1]
length = len(liste)
for i in range(length):
print(liste[i])

Die Liste im Beispiel ist absteigend sortiert – wir wollen sie jetzt aufsteigend sortieren. Du kannst auch mit einer völlig unsortierten Liste testen. Vergiss die negativen Zahlen nicht, auch diese sollten korrekt behandelt werden.

Als erstes implementieren wir einen Durchlauf: Wir durchlaufen die Liste einmal und nehmen die notwendigen Vertauschungen vor. Das Vertauschen von Variablen funktioniert in Python besonders einfach. Die Hintergründe dazu erfährst du im Blog Post über Variablen tauschen in Java und Python. Dort siehst du auch, wie in anderen Sprachen Elemente vertauscht werden.

Hier das Code-Snipped für einen Durchgang. Wir wollen ja immer benachbarte Elemente vergleichen. Die Variable i0 hilft dabei. Wir müssen darauf achten, sie rechtzeitig nachzuführen.

liste = [6 ,5, 4, 3, 2, 1]
i0 = 0
for i in range(1, length):
  print(liste)
  if (liste[i0] > liste[i]):
    (liste[i0], liste[i]) = (liste[i], liste[i0])
    i0 = i
print(liste)

Hast du den Code im Python Playground ausgeführt? Hast du bemerkt, wie die 6 von links nach rechts wandert und schon nach einem Durchlauf am Ende steht. Wie eine kleine Blase wandert die Vertauschung durch die Liste und von da kommt auch der Name des Algorithmus.

Jetzt wiederholen wir den Vorgang so lange, bis keine Variable mehr vertauscht wird. Dazu benötigen wir einen Merker. Wir nennen diese Variable swapped – immerhin bedeuted vertauschen im englischen ja swap. Wir merken uns also, ob in einem Durchlauf geswappt wurde.

Beachte im Code Snippet wo diese Variable verändert wird. Auch die Variable i0 muss korrekt nachgeführt werden.

 

liste = [6 ,5, 4, 3, 2, 1]
length = len(liste)
swapped = True
while swapped == True:
  i0 = 0
  swapped = False
  for i in range(1, length):
    print(liste)
    if (liste[i0] > liste[i]):
      (liste[i0], liste[i]) = (liste[i], liste[i0])
      swapped = True
    i0 = i
print(liste)

Sortieren ist so wichtig und so oft verwendet, dass die allermeisten Programmiersprachen bereits einen guten Sortieralgorithmus mitbringen.

Zwei Varianten in Python:

Sortieren in Python als Methode

liste = [6 ,5, 4, 3, 2, 1]
liste.sort()
print(liste)

Sortieren in Python als Funktion

liste2 = sorted(liste)
print(liste)
print(liste2)

Der Unterschied – die Funktion liefert eine neue Liste zurück – die unsortierte Liste bleibt erhalten. Die Methode sortiert die Liste in sich.

Bubble Sort in Java

Wir können den Algorithmus ja ein einer beliebigen Programmiersprache implementieren. Es folgt ein Beispiel in Java. Der Code ist Eins-zu-Eins aus Python übersetzt. Klicke aufs +-Zeichen und vergleiche mit dem Python-Code.

Beispiel Java Code für Bubble Sort

Java ist eine typsichere Sprache – wir müssen also immer den Datentyp definieren.

Eine einfache Möglichkeit, den Inhalt des Arrays anzuzeigen müssen wir uns ebenfalls selbst schaffen – hier mit Hilfe der Methode print().

Variablen vertauschen geht auch nicht so elegant wie in Python – wir könnten statt der drei Zeilen auch eine weitere Methode schreiben, z.B. swap()

class BubbleSort {
  public static void main(String[] args) {
    int[] liste = {6, 5, 4, 3, 2, 1} ;
    int length = liste.length;
    boolean swapped = true;
    while (swapped) {
    int i0 = 0;
    swapped = false;
    for (int i = 1; i < length; i++) {
      print(liste);
      if (liste[i0] > liste[i]) {
        int hilfsfeld = liste[i0];
        liste[i0] = liste[i];
        liste[i] = hilfsfeld;
        swapped = true;
      }
      i0 = i;
      }
      print(liste);
    } 
  }
  private static void print(int[] liste) {
    for (int i=0; i<liste.length; i++) {
      System.out.print(" "+liste[i]);
    }
    System.out.println();
  }
}

Laufzeitverhalten des Bubble Sort

Hast du bemerkt, wie oft ein Vergleich vorgenommen wird?

Wir haben 6 Elemente in der Liste und es wurden 36 Vergleiche vorgenommen. Wir haben ja pro Vergleich ein print() programmiert. Wir hätten auch einen Zähler mitführen können.

Man sagt, dass das Laufzeitverhalten des Bubble Sort O(n*n) ist – als quadratisch in Bezug auf die Anzahl Elemente in der Liste. Das ist ein denkbar schlechtes Laufzeitverhalten. Man bemerkt es, wenn große Listen sortiert werden.

Der Bubble Sort ist ja auch der naive Ansatz zum Sortieren. Es wurde viel geforscht und eine ganze Reihe optimierter Algorithmen wurden entwickelt.

Sie schnellsten Sorts haben ein Laufzeitverhalten von beispielsweise O(n log(n)).

Weitere Sortieralgorithmen

Es eine ganze Reihe von Sortier-Algorithmen. Diese haben unterschiedliche Eigenschaften und jeder hat einen Namen.

  • Bubble-Sort
  • Shaker Sort
  • Selection Sort
  • Insertion Sort
  • Heap Sort
  • Quick Sort
  • Merge Sort
  • Shell Sort
  • Radix Sort

Die Verfahren sind unterschiedlich schnell und verbrauchen unterschiedlich viel Speicherplatz. Einige davon sind ganz schön raffiniert, wie beispielsweise der Quick Sort.

Wir können viel über Algorithmen lernen, indem wir die verschiedenen Verfahren zum Sortieren studieren. Letztendlich erreichen sie alle dasselbe Ziel. Doch der Weg ist sehr unterschiedlich.

Programmieren lernen

Wer programmiert, entwirft zuerst einen Algorithmus. Erst danach wird der Algorithmus in einer Programmiersprache codiert und getestet.

Der Lernprozess geht Hand-in-Hand: Wer Programmieren lernen will, braucht viele kleine Beispiele, um gleich auch zu lernen, wie ein Algorithmus entsteht. Der Bubble-Sort ist ein klassischer Algorithmus, der zu jeder Ausbildung dazu gehört, und schon einige Grundkenntnisse voraussetzt.

Damit du diese Grundkenntnisse erlangen kannst, haben wir das E-Book Spiel mit Python geschrieben. Schau rein:

  • Python ist eine vielseitige Programmiersprache. Sie wird gerne genutzt, für Datenanalysen, Data Science und neu auch, um KI-gestützte, intelligente Apps zu entwickeln.

  • Generative KI, insbesondere Large Language Models (LLMs), haben die Welt im Sturm erobert.

    Abonniere meinen Newsletter und erhalte regelmäßig Tipps und Tricks zum produktiven Einsatz von LLMs und ich schenke dir den Zugang zu meinem Fachglossar: Von AI-Engineering bis Zero-Shot.

  • Distanzmetrik und semantische Suche
    Distanzmetrik und semantische Suche
  • Sentence Embeddings für Vektordatenbanken
  • LLMs in Enterprise Search
  • Prompt Engineering Personas und Wiederholungen
  • Chatbot als Lernassistent