merge_sort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mergesort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In diesem Notebook lernen wir Mergesort kennen und vergleichen das Laufzeitverhalten mit dem eines naiven Sortieralgorithmus, nämlich Selectionsort."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Merge-Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Kern des Mergsort-Algorithmus ist die Mergefunktion, die zwei benachbarte bereits sortierte Bereiche einer Sequenz zusammenführt.\n",
    "\n",
    "Der erste Bereich geht dabei von Position `lo` bis einschliesslich Position `mid`, der zweite Bereich von Position `mid+1` bis einschliesslich Position `hi`. Array `tmp` dient als \"Zwischenspeicher\" und muss die gleiche Länge wie `array` haben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(array, tmp, lo, mid, hi):\n",
    "    i = lo\n",
    "    j = mid + 1\n",
    "    for k in range(lo, hi + 1):  # k = lo,...,hi\n",
    "        if j > hi or (i <= mid and array[i] <= array[j]):\n",
    "            tmp[k] = array[i]\n",
    "            i += 1\n",
    "        else:\n",
    "            tmp[k] = array[j]\n",
    "            j += 1\n",
    "    for k in range(lo, hi + 1):  # k = lo,...,hi\n",
    "        array[k] = tmp[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "array = [8, 7, 3, 5, 7, 2, 5, 6, 2, 8]\n",
    "tmp = [0] * len(array)\n",
    "merge(array, tmp, 2, 4, 7)\n",
    "print(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Top-Down-Mergesort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Top-Down-Variante von Mergesort teilt den sortierenden Bereich in zwei etwa gleich grosse Teilbereiche auf, sortiert sie jeweils mit einem rekursiven Aufruf und führt die dann sortierten Teilbereiche wieder mit `merge` zusammen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergesort(array):\n",
    "    tmp = [0] * len(array)  # [0,...,0] with same size as array\n",
    "    sort_aux(array, tmp, 0, len(array) - 1)\n",
    "\n",
    "def sort_aux(array, tmp, lo, hi):\n",
    "    # print(\"start sorting positions\", lo, \"to\", hi)\n",
    "    if hi <= lo:\n",
    "        return\n",
    "    mid = lo + (hi - lo) // 2\n",
    "    # //: Division mit Abrunden\n",
    "    sort_aux(array, tmp, lo, mid)\n",
    "    sort_aux(array, tmp, mid + 1, hi)\n",
    "    merge(array, tmp, lo, mid, hi)\n",
    "    # print(\"merged\", lo, \"-\", mid, \"and\", mid+1, \"-\", hi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "array = [4, 2, 5, 7, 9, 6, 4, 1]\n",
    "mergesort(array)\n",
    "print(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Visualisierung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die folgende Visualisierung basiert auf einem Beitrag von Lukas Schaffner, einem früheren Teilnehmer vom GymInf. Damit diese funktioniert, müssen Sie das Graphviz-Paket installieren. Falls Sie die Anaconda-Distribution verwenden, können Sie dies mit folgenden Befehlen machen:\n",
    "```\n",
    "conda install -c conda-forge graphviz\n",
    "conda install -c conda-forge python-graphviz\n",
    "```\n",
    "\n",
    "Falls Sie google collab verwenden, installieren Sie das Paket mit folgendem Befehl:\n",
    "```\n",
    "!apt-get -qq install -y graphviz && pip install -q pydot\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from graphviz import Digraph\n",
    "from itertools import count\n",
    "\n",
    "node_counter = count() # used to track the number of nodes in the tree\n",
    "\n",
    "def sort_draw_tree(array):\n",
    "    graph = Digraph()\n",
    "    node_number = next(node_counter)\n",
    "    graph.node(str(node_number), \"sort\\n%s\" % array)\n",
    "   \n",
    "    tmp = [0] * len(array) # [0,...,0] with same size as array\n",
    "    sort_aux_draw_tree(array, tmp, 0, len(array) - 1, graph, node_number)\n",
    "    return graph\n",
    "\n",
    "def sort_aux_draw_tree(array, tmp, lo, hi, graph, parent_node):\n",
    "    current_node = next(node_counter)\n",
    "    unsorted_list = str(array[lo:hi+1])\n",
    "   \n",
    "    if hi <= lo:\n",
    "        graph.node(str(current_node), \"lo=%s hi=%s \\n%s\" % (lo, hi, array[lo:hi+1]))\n",
    "        graph.edge(str(parent_node),str(current_node), str(current_node))\n",
    "        return\n",
    "    \n",
    "    mid = lo + (hi - lo) // 2\n",
    "    sort_aux_draw_tree(array, tmp, lo, mid, graph, current_node)\n",
    "    sort_aux_draw_tree(array, tmp, mid + 1, hi, graph, current_node)\n",
    "    merge(array, tmp, lo, mid, hi)\n",
    "   \n",
    "    graph.node(str(current_node), \"lo=%s hi=%s \\n%s\\n%s\" % (lo, hi, unsorted_list, array[lo:hi+1]))\n",
    "    graph.edge(str(parent_node),str(current_node),str(current_node))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sort_draw_tree([4, 2, 5, 9, 4, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bottom-Up-Mergesort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Bottom-Up-Variante von Mergesort arbeitet iterativ und sortiert erst alle hintereinanderliegenden Teilbereiche der Grösse 2, dann der Grösse 4, dann 8, etc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bottom_up_mergesort(array):\n",
    "    n = len(array)\n",
    "    tmp = [0] * n\n",
    "    length = 1\n",
    "    while length < n:\n",
    "        lo = 0\n",
    "        while lo < n - length:\n",
    "            mid = lo + length - 1\n",
    "            hi = min(lo + 2 * length - 1, n - 1)\n",
    "            merge(array, tmp, lo, mid, hi)\n",
    "            # print(\"merged\", lo, \"-\", mid, \"and\", mid+1, \"-\", hi)\n",
    "            lo += 2 * length\n",
    "        length *= 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "array = [4, 2, 5, 7, 9, 6, 4, 1, 5]\n",
    "bottom_up_mergesort(array)\n",
    "print(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Laufzeitvergleich Selectionsort vs. Mergesort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir wollen nun das Laufzeitverhalten von Selectionsort und Mergesort vergleichen. Hier ist hierfür nochmal die bereits bekannte Implementierung von Selectionsort:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(array):\n",
    "    n = len(array)\n",
    "    for i in range(n - 1):\n",
    "        min_index = i\n",
    "        for j in range(i + 1, n):\n",
    "            if array[j] < array[min_index]:\n",
    "                min_index = j\n",
    "        array[i], array[min_index] = array[min_index], array[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Im Folgenden messen wir die Laufzeit von Selectionsort für zufällige Arrays der Grösse 10, 100, 1000 und 10000. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_random_array(n):\n",
    "    a = list(range(n))\n",
    "    random.shuffle(a)\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range (1, 5):\n",
    "    a = create_random_array(10**i)\n",
    "    t = timeit.timeit(lambda: selection_sort(a), number=1)\n",
    "    print(\"Selectionsort auf %i Elementen benötigt Zeit %s.\" % (10**i, t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir sehen hier die typische quadratische Laufzeit. Wenn wir 10 mal mehr Elemente sortieren brauchen wir ca. 100 mal länger. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wiederholen wir nur das gleiche Experiment mit Mergesort:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range (1, 7):\n",
    "    a = create_random_array(10**i)\n",
    "    t = timeit.timeit(lambda: mergesort(a), number=1)\n",
    "    print(\"Mergesort auf %i Elementen benötigt Zeit %s.\" % (10**i, t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Im Gegensatz zu Selectionsort sehen wir nun ein sehr viel besseres Laufzeitverhalten. Die Laufzeit steigt nur leicht überlinear. Im Gegensatz zu Selectionsort können wir somit auch sehr grosse Sequenzen effizient sortieren. "
   ]
  }
 ],
 "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.10"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}