P2_01_sortieren_A.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Übung 2.1: Sortieren\n",
    "\n",
    "Eines der klassischen Probleme der Informatik ist das Sortieren von Daten. Es existierende\n",
    "dutzende Sortieralgorithmen mit unterschiedlichen Eigenschaften. Ein recht einfaches Sortierverfahren\n",
    "ist *Selection Sort*, ein in der Praxis (und bei größeren Datenmengen) sehr schnelles Verfahren ist *Quicksort*\n",
    "\n",
    "In diesem Aufgabenblatt wollen wir die beiden genannten Sortierverfahren mit Python implementieren.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vorbereitung\n",
    "\n",
    "Um zu Sortieren benötigt man natürlich einen Datensatz, den es zu sortieren gilt.\n",
    "Häufig verwendet man dazu Arrays (oder Listen) die mit zufälligen Werten gefüllt sind.\n",
    "\n",
    "Um Zufallszahlen mit Python zu generieren, kann man das Paket `random` verwenden.\n",
    "Die folgende Zelle erzeugt zunächst ein Array mit 1.000 zufälligen Zahlen und stellt diese mit Hilfe von `matplotlib` dar.\n",
    "(Diese Bibliothek haben wir schon kurz beim letzten Termin gesehen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Wir benötigen Zufallszahlen und eine Bibliothek zum plotten\n",
    "%matplotlib inline\n",
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "N = 1000\n",
    "\n",
    "# Eintausend Zufallszahlen zwischen 0 und 1\n",
    "unsorted = [ random.random() for i in range(N)]\n",
    "\n",
    "# Die folgenden Zeilen zeigen die Zahlen als Scatter-Plot an\n",
    "plt.scatter(range(N), unsorted)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Selectionsort\n",
    "\n",
    "\n",
    "*Selectionsort* funktioniert so, dass es eine Liste in zwei nebeneinanderliegende Teillisten aufteilt.\n",
    "Die linke Teilliste ist sortiert und hat am Anfang die Größe 0.\n",
    "Die rechte Teilliste ist unsortiert und hat am Anfang die Länge $N$, wobei $N$ die Anzahl der Elemente in der Liste ist.\n",
    "In jedem Schritt sucht *Selectionsort* das kleinste Element und dessen Position in der noch unsortierten Liste.\n",
    "Dazu müssen alle Elemente in der rechten Liste einmal angeschaut werden.\n",
    "Hat man das kleinste Element der unsortierten Liste gefunden, so vertauscht man es mit dem ersten Element in der unsortierten Liste.\n",
    "Danach ist die sortierte Liste um ein Element größer geworden und die unsortierten Liste um ein Element kleiner.\n",
    "Im nächsten Schritt sucht man dann das kleinste Element in der verblieben unsortierten Liste.\n",
    "Diese Abfolge wird solange wiederholt, bis die unsortierte Liste nur noch ein Element groß ist.\n",
    "Danach ist die Liste vollständig sortiert.\n",
    "\n",
    "Schreiben Sie eine Funktion `selectionsort(l)` zum Sortieren der liste `l`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selectionsort(l):\n",
    "    \"\"\" Sortiert die Liste l mit Selectionsort \"\"\"\n",
    "    \n",
    "    # Hier sollte Ihre Implementierung stehen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = [9,1,4,8,5,7,2,6,3,0]\n",
    "print(\"Vorher: \", l)\n",
    "selectionsort_(l)\n",
    "print(\"Nachher:\", l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quicksort\n",
    "\n",
    "Der *Quicksort* Algorithmus deutlich aufwendiger zu implementieren.\n",
    "Dafür ist sein durchschnittliches asymptotisches Laufzeitverhalten mit ${\\mathcal {O}}(N\\cdot \\log(N))$ deutlich besser als das einfacher Sortieralgorithmen, wie etwa *Selcetion Sort* (${\\mathcal {O}}(N^2)$).\n",
    "\n",
    "Schreiben Sie eine Funktion `quicksort(lst)`, die eine übergebene Liste sortiert.\n",
    "VErwenden Sie **nicht** die eingebauten Sortierfunktionen von Python, sondern implementieren Sie den Algorithmus selbst."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als Hilfestellung kann Ihnen vielleicht die folgende *IDEA-Bauanleitung* dienen.\n",
    "Diese unkonventionelle Beschreibung des Algorithmus stammt von [Sándor P. Fekete](https://www.ibr.cs.tu-bs.de/users/fekete/) von der TU Braunschweig.\n",
    "Auch wenn die Abbildung auf den ersten Blich amüsant wirkt, beschreibt sie doch recht gut, wie Quicksort funktioniert.\n",
    "\n",
    "Für eine textuelle Beschreibung (mit Pseudocode) können Sie auch [Wikipedia](https://de.wikipedia.org/wiki/Quicksort) zurate ziehen.\n",
    "\n",
    "![Kvick Sört](quick-sort.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quicksort(l, links, rechts):\n",
    "    \"\"\"Diese Funktion sortiert die übergebene Liste ('in-place sort')\n",
    "    \n",
    "    Argumente:\n",
    "    l      -- zu sortierende Liste\n",
    "    links  -- Startindex des zu sortierenden Bereich (inklusiv)\n",
    "    rechts -- Endindex des zu sortierenden Bereichs (exklusiv)\n",
    "    \"\"\"\n",
    "    \n",
    "    # Hier sollte Ihre Implementierung stehen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 1000\n",
    "unsorted = [ random.random() for i in range(N)]\n",
    "quicksort(unsorted)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ergebnis überprüfen\n",
    "Der folgende Code plotted das Ergebnis und testet, ob die Liste tatsächlich sortiert ist."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Prüfe, ob die Liste sortiert ist\n",
    "for i in range(N-1):\n",
    "    if unsorted[i] > unsorted[i+1]:\n",
    "        print(\"Fehler an Stelle {:d}: {:f} > {:f} !\".format(i, unsorted[i], unsorted[i+1]))\n",
    "        break;\n",
    "else:\n",
    "    print(\"OK, die Liste ist sortiert!\")\n",
    "\n",
    "# Die folgenden Zeilen zeigen die Zahlen als Scatter-Plot an\n",
    "plt.scatter(range(N), unsorted)\n",
    "plt.show()"
   ]
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}