{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Merge Sort\n", "\n", "**Sortieren durch Zusammenfügen** arbeitet grundlegend anders als die Algorithmen, die Sie bisher gesehen haben und ist wesentlich schneller. Wie die Binäre Suche arbeitet Merge Sort nach dem Prinzip «Teile und Herrsche» («Divide & Conquer»). \n", "\n", "---\n", "**Ziele**\n", "\n", "Sie können\n", "\n", "* den Merge-Sort-Algorithmus in eigenen Worten beschreiben.\n", "* zwei geordnete Listen geordnet zusammenfügen.\n", "---\n", "\n", "## Funktionsweise\n", "\n", "**Aufgabe 1 – Funktionsweise von Merge Sort**\n", "\n", "Schauen Sie sich die folgende Animation an und beschreiben Sie den Merge-Sort-Algorithmus in eigenen Worten.\n", "\n", "\n", "\n", "Bei Interesse können Sie auch eine Visualisierung direkt auf [visualgo.net](https://visualgo.net/en/sorting?slide=11) anschauen.\n", "\n", "Beschreiben Sie den Merge-Sort-Algorithmus in eigenen Worten." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihre Beschreibung des Merge-Sort-Algorithmus in eigenen Worten." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Aufgabe 2 – Merge Sort mit Papier**\n", "\n", "Vor allem um das Teilen zu erfahren, sollten Sie Merge Sort auf Papier durchspielen.\n", "\n", "Nehmen Sie dazu einen feinen Papierstreifen und schreiben Sie Zahlen drauf, z. B.\n", "\n", "```Python\n", "7 4 6 3 9 2 5 1\n", "```\n", "\n", "*Zerreissen* Sie anschliessend den Papierstreifen Schritt für Schritt und setzen Sie die Teilstücke wieder geordnet zusammen. Das Zerreissen an der richtigen Stelle ist wichtig, damit Sie sich die Funktionsweise des Algorithmus besser vorstellen und einprägen können.\n", "\n", "\n", "## Aufteilen\n", "\n", "Sie haben in der Animation beobachten können, dass die Liste ziemlich schnell aufgeteilt ist. Die Aufteilung geschieht nach demselben Prinzip wie bei der binären Suche.\n", "\n", "Aber wie oft wird aufgeteilt? \n", "\n", "**Aufgabe 3 – Aufteilen**\n", "\n", "Versuchen Sie herauszufinden, wie oft aufgeteilt werden muss.\n", "\n", "
\n", " \n", " Hinweis \n", " \n", "\n", "Gehen Sie von kurzen Listen als, empfohlen sind die Längen 1, 2, 3, 4, 5, 8 und 16. \n", "Sehen Sie eine Gesetzmässigkeit?\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihre Ideen..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Zusammenfügen (Merge)\n", "\n", "Wenn Sie Merge Sort implementieren möchten, können Sie von den Einzelelementen ausgehen und diese sortiert zusammenfügen. Dazu müssen Sie sich überlegen, wie Sie zwei sortierte Listen zusammenfügen können.\n", "\n", "Schauen Sie sich dazu die folgende Animation an.\n", "\n", "\n", "\n", "**Aufgabe 4 – Zusammenfügen zweier aufsteigend sortierter Listen**\n", "\n", "Erstellen Sie zwei geordnete Listen, `ungerade` mit den ungeraden Zahlen von 1 bis 9 und eine Liste gerade mit den geraden Zahlen von 2 bis 10.\n", "\n", "Schreiben Sie anschliessend eine Funktion `merge(liste1, liste2)`, welche zwei Listen entgegennimmt und sie geordnet zusammenfügt." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Challenge – Implementation Merge Sort**\n", "\n", "Erstellen Sie nun eine Funktion `mergesort()`, welche eine Liste entgegennimmt und sortiert. Verwenden Sie zum Zusammenfügen die Funktion `merge()` von Aufgabe 4.\n", "\n", "Tipps\n", "\n", "* Den Teilprozess können Sie überspringen und gleich bei den Teillisten der Länge 1 beginnen. \n", "* Sie können eine neue Liste `teillisten` machen, welche die Teillisten enthält.\n", "* In der Liste `teillisten` können Sie schliesslich jeweils zwei Listen in eine zusammenfügen.\n", " *Dabei werden aus zwei Teillisten eine...*\n", "* An Anfang enthält `teillisten` soviele Elemente wie Elemente in der ursprünglichen Liste vorhanden sind.\n", "* Wieviele Elemente sollte `teillisten` am Ende noch enthalten?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Grafische Darstellung\n", "\n", "Es ist möglich, Ihre Liste in einem Säulendiagramm grafisch darzustellen. Um hier abzukürzen ist die entsprechende Funktion `show_diagram()` gegeben. Sie nimmt folgende Parameter:\n", "* `list`: Liste, die dargestellt werden soll\n", "* `title`: Diagrammtitel (optional; Defaultwert: \"Säulendiagramm\")\n", "* `sleep`: Wartezeit in Sekunden (optional, Defaultwert: 0.2)\n", "\n", "\n", "Sie ist mit Kommentaren versehen, falls Sie sie verstehen möchten.\n", "\n", "Führen Sie die folgenden beiden Zellen aus, um die Funktion verwenden zu können.\n", "Die erste Zelle kümmert sich um die Imports. Falls die Bibliotheken nicht installiert sind, steht im Kommentar, wie Sie sie installieren können." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt # PyPlot: Bibliothek für Visualisierungen (Plots)\n", "import numpy as np # NumPy: Bibliothek für numerische Berechnungen\n", "from IPython import display # <--- Jupyter-Notebook-spezifische Bibliothek (ausserhalb von Jupyter: löschen)\n", "\n", "# In der Anacondadistribution ist matplotlib bereits vorinstalliert. \n", "# Falls Ihnen matplotlib oder numpy fehlen, können Sie diese wie folgt installieren, \n", "# kommentieren Sie die folgende Zeile ein (numpy wird mit matplotlib mitinstalliert):\n", "# pip install matplotlib\n", "\n", "def show_diagram(list, title = \"Säulendiagramm\", sleep = 0.2):\n", "\n", " # Den Output der aktuellen Zelle (des Jupyter Notebooks) löschen\n", " # parameter wait=True: warten, bis der neue Output bereitsteht\n", " display.clear_output(wait=True)\n", " \n", " # Balkenindex (x-Koordinaten der Balken)\n", " anzahl_elemente=len(list)\n", " bar_index = np.arange(anzahl_elemente)\n", " # Balkenbreite (1 bedeutet bis zum nächsten Balken)\n", " bar_width = 0.5\n", "\n", " # Titel\n", " plt.title(title)\n", "\n", " # Keine besondere Beschriftung der x- und y-Achsen:\n", " # plt.xticks und plt.yticks nicht definieren\n", "\n", " # Balkendiagramm\n", " plt.bar(bar_index, height=list, width=bar_width, color='blue')\n", "\n", " # Plot anzeigen \n", " plt.show()\n", " \n", " # kurz warten, weil sonst nichts sichtbar\n", " plt.pause(sleep)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Challenge 2 – Visualisierung**\n", "\n", "Nun möchten Sie ihre Liste jedes Mal visualisieren, wenn ein Element neu einsortiert wurde.\n", "\n", "Kopieren Sie dazu Ihre Implementation des Merge-Sort-Algorithmus in die untenstehende Zelle und rufen Sie die Funktion `show_diagram()` so auf, dass jeweils die neue Liste dargestellt wird, sobald ein Element einsortiert wurde.\n", "\n", "Erstellen Sie noch einmal die drei Listen `aufsteigend`, `absteigend` und `zufaellig` und wenden Sie Ihre `mergesort()`-Funktion auf diese drei Listen an." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code...\n", "# Funktion mergesort() mit Aufruf der Funktion show_diagram()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code\n", "# aufsteigende Liste erstellen" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code\n", "# absteigende Liste erstellen" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code\n", "# zufällige Liste erstellen" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Quiz\n", "\n", "Alles klar?\n", "\n", "Sie sollten Merge Sort nun in eigenen Worten beschreiben und Ihre Implementation erklären können.\n", "\n", "Testen Sie Ihr Verständnis anhand der Fragen, die erstellt werden, wenn Sie die folgenden Zellen gemäss Ihrer Umgebung ausführen.\n", "\n", "### NUR FALLS SIE AUF GOOGLE COLAB ARBEITEN\n", "\n", "Führen Sie bitte die **beiden** folgenden Zellen aus, um die Bibliothek für das Quiz zu laden." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# NUR falls Sie AUF GOOGLE COLAB arbeiten:\n", "# Führen Sie diese Zelle aus, um das Quiz zu sehen.\n", "\n", "%%writefile quizclone.py\n", "import os\n", "from subprocess import getoutput\n", "getoutput(\"git clone -l -s https://github.com/donze-informatikunterricht/quiz.git cloned-repo\")\n", "os.chdir('cloned-repo')\n", "print('repo cloned successfully')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# NUR falls Sie AUF GOOGLE COLAB arbeiten:\n", "# Führen Sie diese Zelle aus, um das Quiz zu sehen.\n", "\n", "import quizclone" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Quiz erstellen (unabhängig von Ihrer Arbeitsumgebung)\n", "\n", "Nun können Sie das Quiz erstellen. Führen Sie dazu bitte die folgende Zelle aus.\n", "\n", "Fragen 3 und 4 des Quiz basieren auf der folgenden Liste:\n", "\n", "```python\n", "a = [2, 3, 7, 1, 6, 8, 4, 0, 5, 9]\n", "```\n", "\n", "Bitte führen Sie die folgende Zelle aus, um das Quiz zu erstellen." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from IPython.display import display\n", "import quiz\n", "\n", "display(quiz.Q1_merge)\n", "display(quiz.Q2_merge)\n", "display(quiz.Q3_merge)\n", "display(quiz.Q4_merge)\n", "display(quiz.Q5_merge)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Abschluss: Sortiertanz\n", "\n", "Nun haben Sie sich mit dem Merge-Sort-Algorithmus auseinandergesetzt. \n", "\n", "Sehr empfehlenswert für Such- und Sortieralgorithmen ist der [YouTube-Kanal AlgoRythmics](https://www.youtube.com/channel/UCIqiLefbVHsOAXDAxQJH7Xw), der Algorithmen in Form von Tänzen präsentiert.\n", "\n", "Führen Sie die folgende Zelle aus, um den Tanz zu Merge Sort sehen zu können." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Führen Sie diese Zelle aus, um den Videoclip sehen zu können.\n", "\n", "import IPython\n", "\n", "IPython.display.IFrame(src=\"https://www.youtube.com/embed/XaqR3G_NVoo\", width=560, height=315)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.8" } }, "nbformat": 4, "nbformat_minor": 4 }