BubbleSort

    Auf digitalen Geräten (Smartphone, Computer, etc.) sucht man ständig etwas: Eine App, einen Song, ein Video. Auch auf Webseiten und innerhalb von Apps ist man ständig auf der Suche. Denken Sie nur mal daran, was Sie als erstes tun, nachdem Sie die Amazon-Webseite geöffnet haben.

    So eine Suche kann aber nur dann schnell gehen, wenn die Daten, die man durchsucht, sortiert sind! Denken Sie nur an die Lottozahlen - wenn die Liste sortiert ist, finden Sie ihre Zahlen schneller.

    Scratch-Screenshot: Fee mit Lottozahlen-Array

    Nicht nur Menschen, sondern auch Computer finden das Gesuchte in sortierten Daten wesentlich schneller. Wir werden uns deshalb anschauen, wie man man das hinkriegt: Wir sortieren Daten!

    BubbleSort - Leicht zu verstehen!

    In der Praxis verbringen viele Computer einen Großteil ihrer Zeit damit, Daten zu sortieren. Weil das Sortieren so wichtig ist, hat man viele verschieden Algorithmen (also klar definierte Vorgehensweisen) erfunden, um dieses Ziel zu erreichen. Wir schauen uns jetzt einen Sortier-Algorithmus an, der ziemlich leicht zu verstehen ist: Bubble Sort.

    (Kleine Vorbemerkung zur Schreibung: BubbleSort und Bubble Sort, beides kommt vor, wobei man im Deutschen meistens Bubblesort schreibt.)

    Der Größte-Zahl-ans-Ende-Algorithmus

    • Wir fangen links an und vergleichen zwei benachbarte Elemente des Arrays.
    • Wenn das linke Element größer ist als das rechte, dann "wandert es nach rechts", es wird also getauscht.
    • Nachdem wir so alle benachbarten Elemente des Arrays verglichen haben, steht das größte Element am Ende des Arrays!

    Beispiel: Ein Array mit 4 Zahlen

    Bubblesort: Erster Durchgang

    Wie oft muss verglichen werden?

    Wir sehen, dass wir bei 4 Zahlen genau 3 Vergleiche benötigen. Daraus können wir diese Erkenntnis gewinnen:

    Anzahl Vergleiche = Länge des Arrays - 1

    Struktogramm: Größte-Zahl-ans-Ende-Algorithmus

    Struktogramm: Größte Zahl ans Ende-Algorithmus

    Aufgabe zum »Größte Zahl ans Ende«-Algorithmus

    (1) In Scratch die größte Zahl nach hinten bringen

    Öffnen Sie das Projekt 7200-GroesstesElementAnsEnde-AUFGABE

    Entwerfen Sie in Scratch den Programmcode, mit dem Sie das größte Element ans Ende des Arrays verschieben.

    Scratch: Größte Zahl ans Ende im Lottozahlen-Array

    BubbleSort: Mehrere Durchgänge

    Unser Ziel ist es, das komplette Array zu sortieren. Genau das kriegen wir hin, wenn wir den Größte-Zahl-ans-Ende-Algorithmus in mehreren Durchgängen auf das restliche Array anwenden. Schauen wir uns das im Beispiel an:

    Bubblesort: Zweiter Durchgang

    Damit haben wir es fast geschafft: Noch ein weiterer Durchgang mit dem Größte-Zahl-ans-Ende-Algorithmus:

    Bubblesort: Dritter Durchgang

    Bubble Sort: Wie viele Durchgänge brauchen wir?

    Sie sehen: Wenn wir unseren Größte-Zahl-ans-Ende-Algorithmus mehrmals anwenden, haben wir am Schluss ein komplett sortiertes Array!

    Die Frage ist jetzt: Wie viele Durchgänge brauchen wir, bis das Array sortiert ist?

    Fassen wir unsere Beobachtungen zusammen:

    • Unser Array hatte 4 Elemente!
    • Wir haben 3 Durchgänge gebraucht!

    ➡️ Vermutung: Die Anzahl der Durchgänge entspricht Länge des Arrays – 1

    Kann das sein? In jedem Durchgang verschieben wir die jeweils größte Zahl ans Ende des übrig gebliebenen Arrays. Dann müssten es doch genauso viele Durchgänge sein, wie Elemente im Array vorhanden sind!

    ABER:

    Im letzten Durchgang (im Beispiel: Durchgang 3) werden gleich 2 Elemente richtig einsortiert!

    ➡️ Unsere Vermutung stimmt!

    Wir müssen also das Folgende tun, um ein Array mit BubbleSort zu sortieren:

    Struktogramm: BubbleSort-Algorithmus (unfertig)

    Der Teil, der wiederholt werden soll, muss also ebenfalls in eine Schleife verschoben werden:

    Struktogramm: BubbleSort-Algorithmus (fast fertig)

    Eine Schleife in einer Schleife! Das sieht ja jetzt echt kompliziert aus. Bevor wir uns genauer anschauen, wie das funktioniert, müssen wir erst noch einen kleinen "Schönheitsfehler" beseitigen, der uns bisher noch nicht aufgefallen ist!

    Betrachten wir nochmal, welche Elemente wir in den einzelnen Durchgängen miteinander vergleichen:

    Tabelle: Durchgänge bei BubbleSort

    Sie müssten sehen, dass die Schleife zum Vertauschen der Elemente jedes Mal kürzer läuft. Wir verändern unser Struktogramm entsprechend, um das zu berücksichtigen:

    Struktogramm: BubbleSort-Algorithmus (komplett)

    Aufgaben zum Sortieren mit BubbleSort

    (2) Namensliste sortieren

    Sie haben eine Namensliste, die sortiert werden soll: Eva Anja Dragan Jasmin Alex

    Sortieren Sie diese Liste "von Hand", indem Sie den BubbleSort-Algorithmus verwenden. Verwenden Sie dafür diese Vorlage: 7200_Aufgabe2_NamenSortieren.docx

    Tabelle mit Namen zum Sortieren

    (Hinweis: Sie müssen nicht notieren, ob getauscht wird oder nicht!)

    (3) Lottozahlen mit BubbleSort sortieren

    Öffnen Sie das Projekt 7210_BubbleSort-AUFGABE

    Ihre Aufgabe ist es, Lottozahlen zu sortieren. Setzen Sie dazu das BubbleSort-Struktogramm um!

    Scratch: Lottozahlen sind im Unterprogramm zu sortieren

    (4) Verkaufsliste sortieren

    Öffnen Sie das Projekt 7215_Blumenladen-AUFGABE

    In diesem Projekt wurde bereits ein Array mit dem Namen verkaeufe erstellt und gefüllt.

    Ihre Aufgabe ist es, das Array verkaeufe zu sortieren. Setzen Sie dazu den BubbleSort-Algorithmus ein!

    Scratch: Verkäufe müssen sortiert werden mit BubbleSort

    Erklärvideo: BubbleSort

    Arbeitsblatt: BubbleSort (mit Aufgaben)

    Arbeitsblatt »BubbleSort« (PDF)

    Übungsblatt »BubbleSort - Vorlage zur Übung Namen sortieren« (docx)

    Copyright © 2020Powered by Bludit