{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Selection Sort (Lösungen)\n", "\n", "**Sortieren durch Suchen** ist ein sehr einfacher Algorithmus. \n", "\n", "---\n", "**Ziele**\n", "\n", "Sie können\n", "* den Selection-Sort-Algorithmus in eigenen Worten beschreiben.\n", "* das Minimum (oder Maximum) in einer Liste suchen.\n", "* zwei Elemente einer Liste tauschen.\n", "* Selection Sort implementieren und Ihre Implementation erklären. \n", "---\n", "\n", "## Funktionsweise\n", "\n", "**Aufgabe 1 – Funktionsweise von Selection Sort**\n", "\n", "Schauen Sie sich die folgende Animation von [visualgo.net](https://visualgo.net/en/sorting?slide=8) an und beschreiben Sie den Selection-Sort-Algorithmus in eigenen Worten.\n", "\n", "*Um den Videoclip sehen zu können, müssen Sie allenfalls die folgende Zelle ausführen.*" ] }, { "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/cBDejTyxyh8?rel=0&controls=0&showinfo=0\", width=560, height=315)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Machen Sie aus dieser Zelle eine Markdownzelle und \n", "# beschreiben Sie den Selection-Sort-Algorithmus in eigenen Worten." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Lösung: \n", "Beim Selection Sort wird die zu sortierende Liste in zwei Bereiche aufgeteilt, von denen der vordere Teil sortiert ist und der hintere Teil unsortiert, wobei am Anfang die ganze Liste als unsortiert angesehen wird.\n", "\n", "Für jedes einzusortierende Element wird im unsortierten Bereich das kleinste (bzw. grösste) Element gesucht. Wenn es gefunden ist, wird es mit dem vordersten Element des unsortierten Bereichs getauscht, wobei der sortierte Bereich um das neu eingefügte Element wächst, während der unsortierte Bereich um ein Element kleiner wird." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Implementation\n", "\n", "Nun möchten Sie Selection Sort implementieren. Dazu müssen Sie sich zwei Dinge überlegen:\n", "\n", "* Tausch zweier Listenelemente\n", "* Suchen des Minimums/Maximums einer Liste\n", "\n", "### Stellentausch\n", "\n", "\n", "Da beim Einsortieren der Elemente jeweils zwei Elemente der Liste getauscht werden, müssen Sie sich vorher Gedanken dazu machen, wie Sie die Plätze tauschen können.\n", "\n", "Der Tausch zweier Listenplätze geschieht analog zum Tausch zweier Variablen.\n", "\n", "#### Variablentausch\n", "\n", "Stellen Sie sich vor, Sie haben zwei Variablen `a` und `b`. \n", "\n", "Wenn Sie nun der Variable `a` den Wert der Variable `b` zuweisen, haben beide Variablen denselben Wert und Sie haben den ursprünglichen Wert der Variable `a` verloren.\n", "\n", "Sie müssen also eine Lösung finden, wie Sie den Wert der Variable `a` nicht verlieren, wenn Sie den Wert der Variable `b` in die Variable `a` schreiben.\n", "\n", "Sie haben jederzeit die Möglichkeit, neue Variablen zu erstellen und können den Wert der Variable `a` problemlos in einer neuen Variable zwischenspeichern. Diese neue Variable nennt man **Hilfsvariable**. Da sie nur vorübergehend, also *temporär* genutzt wird, nennt man sie in der Regel `temp`. Sie können Sie aber auch `c` nennen oder `luisa` oder `adrian`.\n", "\n", "Der Variablentausch wird folgendermassen implementiert:\n", "\n", "```Python\n", "a = 3\n", "b = 5\n", "\n", "temp = a # Hilfsvariable\n", "# nun ist der Wert der Variable a nicht verloren (sondern in temp gespeichert) und Sie können a einen neuen Wert zuweisen:\n", "a = b\n", "b = a\n", "```\n", "\n", "#### Platztausch in der Liste\n", "\n", "Wenn Sie in einer Liste zwei Plätze tauschen wollen, gehen sie genauso vor wie wenn Sie zwei Variablen tauschen möchten, mit dem einzigen Unterschied, dass Sie nun keine Variablen haben, sondern Listenelemente, auf die Sie, über die Indizes zugreifen.\n", "\n", "**Aufgabe 2 – Tausch zweier Variablen**\n", "\n", "Stellen Sie sich vor, Sie haben zwei Variablen, deren Werte Sie vertauschen möchten.\n", "\n", "```Python\n", "a = 4\n", "b = 2\n", "```\n", "\n", "Wenn Sie nun folgenden Code ausführen, haben beide Variablen denselben Wert (2), denn mit der ersten Zeile überschreiben Sie den Wert der Variable a mit dem Wert der Variable b und verlieren ihn.\n", "\n", "```Python\n", "a = b\n", "b = a\n", "```\n", "\n", "Überlegen Sie sich, wie Sie vorgehen können, um keinen Wert zu verlieren und implementieren Sie den Variablentausch." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "\n", "a = 2\n", "b = 4\n", "print(a,b)\n", "# Sie können jederzeit eine neue Variable machen. \n", "# In dieser Hilfsvariable, oft nennt man sie temp für temorär \n", "# oder aux für auxiliary (\"Hilfs...\") können Sie einen Wert \n", "# sichern. Danach können Sie den Wert überschreiben.\n", "temp = a\n", "a = b\n", "b = temp\n", "print(a,b)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Aufgabe 3 – Platztausch in einer Liste**\n", "\n", "Implementieren Sie nun eine Funktion `swap()` analog zum Variablentausch für den \"Platztausch\", oft auch \"Swap\" genannt. Sie soll eine Liste und zwei Indizes entgegennehmen.\n", "\n", "Erstellen Sie anschliessend eine Liste und testen Sie Ihre Funktion `swap()`, indem Sie das erste und das letzte Element Ihrer Liste vertauschen und die Liste anschliessend mit `print()` ausgeben." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "\n", "def swap(liste, index1, index2):\n", " temp = liste[index1]\n", " liste[index1] = liste[index2]\n", " liste[index2] = temp\n", " return liste\n", "\n", "# Liste a erstellen\n", "a = [x for x in range(5)]\n", "print(\"a vorher:\", a)\n", "# swap anwenden\n", "swap(a, 0, len(a)-1)\n", "# Liste a ausgeben\n", "print(\"a nachher:\", a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Das Minimum/Maximum einer Liste finden\n", "\n", "Um es vorwegzunehmen, es gibt in Python die Möglichkeit, das kleinste bzw. grösste Element einer Liste zu finden (Funktionen `min()` bzw. `max()`) und es gibt auch die Möglichkeit, den Index eines Elementes in einer Liste auszugeben (Funktion `index()`). Es geht hier aber darum, dass Sie den Umgang mit Listen üben. Deshalb werden Sie die Suche nach dem kleinsten Element nun selbst schreiben.\n", "\n", "Schauen Sie sich weiter oben noch einmal die Animation von Visualgo.net an. Bei jedem Durchlaufen des unsortierten Bereichs wird das erste Element rot markiert. Es ist das Minimum (oder je nachdem das Maximum). Dieses Element wird mit jedem Element des unsortierten Bereichs vergleichen. Dabei wird jeweils überprüft, ob das aktuelle Element noch kleiner (oder grösser) als das bereits als Minimum (oder Maximum) markierte Element ist und wenn nötig wird das neue Element zum neuen Minimum (oder Maximum). Das Element, das am Ende des Durchgangs immer noch markiert ist, ist das Element, das beim Sortieren als nächstes an den sortierten Bereich angehängt wird.\n", "\n", "**Aufgabe 4 – Minimum in einer Liste finden**\n", "\n", "a) Schreiben Sie eine Funktion `suche_min()`, die eine Liste durchläuft und den Index des Minimums (also des kleinsten Werts in der Liste) herausgibt.\n", "\n", "Ihre Funktion `suche_min()` soll eine Liste entgegennehmen und den Index des kleinsten Elements ausgeben.\n", "\n", "Testen Sie anschliessend Ihre Funktion an einer Liste von Zufallswerten.\n", "\n", "
\n", " \n", " Hinweis\n", " \n", "\n", "Falls Sie nicht mehr wissen, wie Sie eine Liste von Zufallswerten erstellen können:\n", "```Python\n", "import random\n", " \n", "list = [random.randint(1,100) for x in range(10)]\n", "```\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung, welche die Funktionen min, max, index *nicht* nutzt:\n", " \n", "import random\n", "\n", "zufaellig = [random.randint(1,100) for x in range(10)]\n", "\n", "def suche_min(liste):\n", " min_index = 0\n", " minimum = liste[min_index]\n", " for i in range(len(liste)):\n", " if liste[i] < minimum:\n", " minimum = liste[i]\n", " min_index=i\n", " return min_index # Index des Minimums\n", " \n", "def suche_max(liste):\n", " max_index = 0\n", " maximum = liste[max_index]\n", " for i in range(len(liste)):\n", " if liste[i] > maximum:\n", " maximum = liste[i]\n", " max_index = i\n", " return max_index # Index des Minimums\n", "\n", "print(zufaellig)\n", "print(\"min:\", suche_min(zufaellig))\n", "print(\"max:\", suche_max(zufaellig))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "b) Da die Funktionen `min()`, `max()` und `index()` allerdings bereits vordefiniert sind, ist es besser, diese auch zu nutzen. \n", "\n", "Implementieren Sie noch einmal die Funktionen `suche_min(liste)` und `suche_max(liste)` mit Verwendung der vordefinierten Funktionen." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung, welche die Funktionen min, max, index nutzt:\n", " \n", "import random\n", "\n", "zufaellig = [random.randint(1,100) for x in range(10)]\n", "\n", "def suche_min(liste):\n", " minimum = min(liste)\n", " return liste.index(minimum) # Index des Minimums\n", " \n", "def suche_max(liste):\n", " maximum = max(liste) # Falls Sie sich fragen, wie Sie das Maximum finden\n", " return liste.index(maximum) # Index des Maximums\n", "\n", "print(zufaellig)\n", "print(\"min:\", suche_min(zufaellig))\n", "print(\"max:\", suche_max(zufaellig))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Sie haben soeben die wichtigsten Listenoperationen kennengelernt, die Sie für die Implementation von Selection Sort benötigen.\n", "\n", "**Aufgabe 5 – Pseudocode**\n", "\n", "Nun müssen Sie sich noch einmal genau überlegen, wie der Selection-Sort-Algorithmus genau funktioniert. Schauen Sie sich wenn nötig noch einmal die Animation der Einführung an. Schreiben Sie Selection Sort in Pseudocode.\n", "\n", "
\n", " \n", " Hinweis 1\n", " \n", "\n", "Überlegen Sie sich, welche Elemente verglichen werden müssen, damit die Stelle (der Index) gefunden wird, an der ein Element eingefügt werden muss.\n", "
\n", "\n", "
\n", " \n", " Hinweis 2\n", " \n", "\n", "Da Sie von einer Liste ausgehen und die sortierten Elemente in derselben Liste haben möchten, müssen Sie sich überlegen, welcher Bereich der Liste bereits sortiert ist.\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Machen Sie aus dieser Zelle eine Markdownzelle und \n", "# beschreiben Sie den Selection-Sort-Algorithmus in Pseudocode." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Lösung* \n", "\n", "```\n", "Gegeben ist die zu sortierende Liste `liste`\n", "für i = 0 bis vorletztes Element der Liste:\n", " suche das Minimum und tausche es mit liste[i]\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Aufgabe 6 – Implementation**\n", "\n", "Schreiben Sie nun eine Funktion `selectionsort`, die eine Liste entgegennimmt, sie nach dem Selection-Sort-Algorithmus sortiert und anschliessend wieder ausgibt.\n", "\n", "Nutzen Sie dazu die bereits definierten Funktionen `swap()` und `suche_min()`.\n", "\n", "Versuchen Sie die Anzahl Vergleiche zu zählen und diese am Ende auszugeben." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "\n", "zufaellig = [random.randint(1,100) for x in range(10)]\n", "\n", "print(zufaellig)\n", "\n", "def selectionsort(liste):\n", " for i in range(0, len(liste)):\n", " minimum = i + suche_min(liste[i:])\n", " swap(liste, i, minimum)\n", " return liste\n", " \n", "print(selectionsort(zufaellig))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Aufgabe 7 – Vergleiche zählen**\n", "\n", "Zählen Sie die Vergleiche.\n", "\n", "Hinweis: \n", "Um die Vergleiche zu zählen, müssen Sie die Suche nach dem Minimum selbst umsetzen wie in Aufgabe 3.a)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "\n", "def selectionsort(liste):\n", " anzahl_vergleiche = 0\n", " for i in range(0, len(liste)):\n", " # Minimum suchen\n", " min_index = i\n", " minimum = liste[min_index]\n", " for j in range(i+1,len(liste)):\n", " anzahl_vergleiche +=1\n", " if liste[j] < minimum:\n", " minimum = liste[j]\n", " min_index=j\n", " swap(liste, i , min_index)\n", " \n", " print(\"Anzahl Vergleiche:\", anzahl_vergleiche)\n", " return liste\n", " \n", "zufaellig = [random.randint(1,100) for x in range(10)]\n", "print(zufaellig)\n", "selectionsort(zufaellig)\n", "print(zufaellig)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Aufgabe 8 – Anwendung auf verschiedene Ausgangslagen**\n", "\n", "Erstellen Sie nun drei Listen `aufsteigend`, `absteigend` und `zufaellig` der Länge 10, 100 oder 1000 und wenden Sie Ihre Funktion `selectionsort()` darauf an.\n", "\n", "* Sind Sie von der Anzahl Vergleiche überrascht? \n", "* Wie können Sie die Anzahl Vergleiche in Abhängigkeit von der Länge der Liste $n$ formal beschreiben?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "laenge = 10\n", "aufsteigend = [x for x in range(laenge)]\n", "absteigend = [laenge-1-x for x in range(laenge)]\n", "zufaellig = [random.randint(1, 100) for x in range(laenge)]\n", "\n", "print(\"Aufsteigende Liste von Länge\", laenge, aufsteigend)\n", "selectionsort(aufsteigend)\n", "print(aufsteigend, \"\\n\")\n", "\n", "print(\"Absteigende Liste von Länge\", laenge, absteigend)\n", "selectionsort(absteigend)\n", "print(absteigend, \"\\n\")\n", "\n", "print(\"Zufällige Liste von Länge\", laenge, zufaellig)\n", "selectionsort(zufaellig)\n", "print(zufaellig)" ] }, { "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": [ "**Aufgabe 9 – 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 Selection-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 `selectionsort()`-Funktion auf diese drei Listen an." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "\n", "def selectionsort(liste, visualisierung=False):\n", " anzahl_vergleiche = 0\n", " for i in range(0, len(liste)):\n", " # Minimum suchen\n", " min_index = i\n", " minimum = liste[min_index]\n", " for j in range(i+1,len(liste)):\n", " anzahl_vergleiche +=1\n", " if liste[j] < minimum:\n", " minimum = liste[j]\n", " min_index=j\n", " swap(liste, i , min_index)\n", " if visualisierung:\n", " show_diagram(liste, \"Selectionsort (Durchgang \" + str(i) + \", Total Vergleiche \" + str(anzahl_vergleiche) + \")\", sleep = 0.2)\n", " print(\"Anzahl Vergleiche:\", anzahl_vergleiche)\n", " #return liste" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# aufsteigende Liste erstellen\n", "laenge = 20\n", "aufsteigend = [x for x in range(laenge)]\n", "\n", "selectionsort(aufsteigend, True)\n", "print(aufsteigend)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# absteigende Liste erstellen\n", "absteigend = [laenge-1-x for x in range(laenge)]\n", "\n", "selectionsort(absteigend, True)\n", "print(absteigend)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# zufällige Liste erstellen\n", "zufaellig = [random.randint(1, 100) for x in range(laenge)]\n", "\n", "selectionsort(zufaellig, True)\n", "print(zufaellig)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Quiz\n", "\n", "Alles klar?\n", "\n", "Sie sollten Selection 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_selection)\n", "display(quiz.Q2_selection)\n", "display(quiz.Q3_selection)\n", "display(quiz.Q4_selection)\n", "display(quiz.Q5_selection)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Abschluss: Sortiertanz\n", "\n", "Nun haben Sie sich mit dem Selection-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 Selection 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/Ns4TPTC8whw\", 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 }