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)