{ "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": [ "# Machen Sie aus dieser Zelle eine Markdownzelle und \n", "# beschreiben Sie den Merge-Sort-Algorithmus in eigenen Worten." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Lösung: \n", "Beim Merge Sort wird die zu sortierende Liste so oft in zwei Hälften geteilt, bis nur noch einzelne Elemente (in Form von Listen mit einem Element) übrig bleiben. Listen mit einem Element sind immer sortiert. \n", "\n", "Anschliessend werden je zwei Listen zusammengesetzt, indem jeweils die vordersten Elemente verglichen und – falls nach aufsteigender Grösse sortiert werden soll – das kleinere (ansonsten das grössere) in eine neue Liste eingefügt. Dieser Vorgang wird so oft wiederholt, bis alle Teillisten wieder zu einer sortierten Liste zusammengesetzt sind." ] }, { "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 aus, 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": 1, "metadata": {}, "outputs": [], "source": [ "# Ihre Ideen..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Lösung: \n", "Schauen Sie sich die folgende Animation an.\n", "\n", "" ] }, { "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": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "\n", "# Die beiden Listen liste1 und liste2 bleiben unverändert, das Resultat wird in eine neue Liste geschrieben.\n", "gerade = [2*x for x in range(1,6)]\n", "print(gerade)\n", "ungerade = [2*x-1 for x in range(1,6)]\n", "print(ungerade)\n", "\n", "def merge(liste1, liste2):\n", " sortierte_liste = [] # neue Liste, am Anfang noch leer\n", " index1 = 0 # zeigt auf das erste Element der Liste\n", " index2 = 0 # zeigt auf das erste Element der Liste\n", " # Solange index1 bzw. index2 noch in die Liste zeigt\n", " # werden die entsprechenden Elemente verglichen und \n", " # das kleinere an die sortierte_liste angehängt,\n", " # danach muss der enstsprechende Index angepasst werden\n", " while index1