QuickSort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "rXD94vak2afD"
   },
   "source": [
    "# QuickSort\n",
    "\n",
    "Grundlegendes Ziel der Sortieralgorithmen ist das Sortieren einer Liste von Elementen, z.B. Zahlen (integer) oder Wörter (strings) gemäß einer zuvor definierten Kriteriums. Im Falle von Zahlen könnte dies zum Beispiel in aufsteigender Reihenfolge, oder im Falle von Wörter in alphabetischer Reihenfolge sein. \n",
    "\n",
    "Beim QuickSort-Algorithmus wird dieses Ziel erreicht, indem die zu sortierende Liste in immer kleinere Teilprobleme aufgeteilt wird, die einfacher zu lösen sind. Schließlich werden die gelösten Teilprobleme wieder zusammengefügt.\n",
    "\n",
    "Lasst uns nun gemeinsam den Sortieralgorithmus QuickSort in Python programmieren. Hier folgen ein paar Tipps mit Code-Schnipseln, die euch beim Programmieren helfen können. \n",
    "\n",
    "Ziel ist es, eine Liste aus Zahlen oder Wörtern in aufsteigender Reihenfolge bzw. alphabetisch zu sortieren. \n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python-Tipps zum Umgang mit Listen:\n",
    "\n",
    "\n",
    "*   **Liste erstellen**\n",
    "    ```Python\n",
    "    liste = [1, 2, 5, 3]\n",
    "    ```\n",
    "*  **Länge einer Liste**\n",
    "    ```Python\n",
    "    print(len(liste)) \n",
    "    ```\n",
    "    liefert `4`\n",
    "\n",
    "*   **Listenelement bearbeiten**\n",
    "    * Das erste Listenelement ansprechen:\n",
    "        ```Python\n",
    "        print(liste[0])\n",
    "        ```\n",
    "        liefert `1`\n",
    "\n",
    "    * Das letzte Listenlement:\n",
    "        ```Python\n",
    "        print(liste[len(liste)-1])\n",
    "        ```\n",
    "        liefert `3`\n",
    "\n",
    "    * Ein Listenelement überschreiben:\n",
    "        ```Python\n",
    "        liste[1] = 10\n",
    "        print(liste)\n",
    "        ```\n",
    "        liefert `[1, 10, 5, 3]`\n",
    "\n",
    "\n",
    "*   **Vergleich zweier (benachbarter) Elemente** \n",
    "    ```Python\n",
    "    vergleich = liste[1] > liste[2]\n",
    "    print(vergleich)\n",
    "    ```\n",
    "    liefert `True`, denn `10` is größer als `5`\n",
    "\n",
    "*   **Listenelement tauschen** \n",
    "    ```Python\n",
    "    hilfs_variable = liste[2]\n",
    "    liste[2] = liste[1]\n",
    "    liste[1] = hilfs_variable\n",
    "    print(liste)\n",
    "    ```\n",
    "    liefert `[1, 5, 10, 3]`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "xWlO-w8W7kdO"
   },
   "source": [
    "## Pseudocode\n",
    "\n",
    "Ein Pseudocode beschreibt in natürlicher Sprache einen Algorithmus oder ein System. Dadurch kann ein und der selbe Pseudocode genutzt werden, um einen Algorithmus in verschiedene Programmiersprachen zu übersetzen. Hier der Pseudocode von Quick Sort.\n",
    "\n",
    "\n",
    "1) Schau dir das bereits vorhandene Funktionsgerüst an. Was wird übergeben, was sind Rückgabewerte?\n",
    "\n",
    "2) Definiere den `Index_von_links` , der den Anfang der Liste beschreibt\n",
    "\n",
    "3) Definiere den `Index_von_rechts` am Ende der Liste\n",
    "\n",
    "4) Definiere das Vergleichselement, beispielsweise ein zufälliges Element der Liste\n",
    "\n",
    "5) Sortiere die Liste so lange, bis sich `Index_von_links` und `Index_von_rechts` treffen (Tipp: while-schleife):\n",
    "  \n",
    "* a) Solange das Listenelement am `Index_von_links` kleiner als das Vergleichselement ist (Tipp: while-Schleife):\n",
    "    - Erhöhe den `Index_von_links` um 1\n",
    "\n",
    "* b) Solange das Listenelement am `Index_von_rechts` größer als das Vergleichselement ist (Tipp: while-Schleife):\n",
    "     - Verringere den `Index_von_rechts` um 1\n",
    "\n",
    "* c)  WENN der `Index_von_links` kleiner gleich dem `Index_von_rechts` ist (Tipp: if-Bedingung)\n",
    "      DANN:\n",
    "    - Tausche die Listenelemente an den Stellen `Index_von_links` und `Index_von_rechts`\n",
    "    - Erhöhe den `Index_von_links` um 1\n",
    "    - Verringere den `Index_von_rechts` um 1\n",
    "\n",
    "         \n",
    "* Und durchlaufe die Liste nun weiterhin bis die sich die Indizes treffen/überholen:\n",
    "\n",
    "6) Rufe die QuickSort-Funktion für die zwei sich ergebenden Teilprobleme auf\n",
    "   - Teilproblem 1: Liste vom Anfang bis zum `Index_von_rechts` sortieren\n",
    "   - Teilproblem 2: Liste vom `Index_von_links` bis zum Ende sortieren"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quicksort(liste, anfang, ende):\n",
    "    \"\"\"\n",
    "    Diese Funktion implementiert Quick Sort\n",
    "    \n",
    "    parameter liste: unsortierte Liste (list)\n",
    "    parameter anfang: Anfangsindex (int)\n",
    "    parameter ende: Endindex (int)\n",
    "    return: sortierte_liste\n",
    "    \"\"\"\n",
    "    sortierte_liste = None\n",
    "    \n",
    "    # CODE HIER!\n",
    "    \n",
    "    \n",
    "    return sortierte_liste"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Testen\n",
    "Code zum Testen des Sortier-Programms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "R0tNZ32i2rXD",
    "outputId": "d8b7cdc6-d7dc-49b4-b83b-7af0d1c01169"
   },
   "outputs": [],
   "source": [
    "arr = [10, 7, 8, 9, 1, 5] \n",
    "n = len(arr) \n",
    "quicksort(arr, 0, n-1) \n",
    "print(\"Die sortierte Liste ist:\") \n",
    "print(arr)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "QuickSort.ipynb",
   "provenance": []
  },
  "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": 1
}