radix_sort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Radixsort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Radixsort sortiert Sequenzen von Zahlen, indem es sie sukzessive von der letzten bis zur vordersten Ziffer immer wieder auf eine bestimmte Weise in \"Fächer\" für die jeweiligen Ziffern aufteilt.\n",
    "\n",
    "Der Knackpunkt ist dabei, wie man die Ziffer an einer bestimmten Position bestimmt. \n",
    "\n",
    "Betrachten wir das erstmal im Dezimalsystem. Teilt man die eine Zahl durch $10^i$ verschiebt man das Dezimalzeichen um $i$ Stellen nach links:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "z = 948\n",
    "\n",
    "for i in range(4):\n",
    "    print(i, \":\", z / 10**i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Verwenden wir die Division mit Abrunden (`//`), werden die Nachkommastellen weggeworfen und wir schneiden gewissermassen einfach die letzten $i$ Positionen ab:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(4):\n",
    "    print(i, \":\", z // 10**i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Umgekehrt kann man mit der Modulo-Operation alle bis auf die letzten $i$ Stellen \"loswerden\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(1,4):\n",
    "    print(i, \":\", z % (10**i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zusammen können wir das nutzen, um die $i$-te Stelle aus einer Zahl zu extrahieren:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(z)\n",
    "for i in range(4):\n",
    "    print(i, \":\", (z // 10**i) % 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mit dieser Technik, sieht Radixsort (für Dezimalzahlen) dann folgendermassen aus.\n",
    "\n",
    "Es ist wichtig, die Zahlen immer der aktuellen Reihefolge nach auf die Fächer zu verteilen und sie dann von Fach 0 bis Fach 9 für die nächste Iteration aufzusammeln, wobei ihre Reihenfolge im Fach beibehalten wird."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sort(array):\n",
    "    print(\"Eingabe:\", array, \"\\n\")\n",
    "    if not array:  # array is empty\n",
    "        return\n",
    "    iteration = 0\n",
    "    max_val = max(array) # identify largest element\n",
    "    while 10 ** iteration <= max_val:\n",
    "        buckets = [[] for _ in range(10)] \n",
    "        for elem in array:\n",
    "            digit = (elem // (10 ** iteration)) % 10\n",
    "            buckets[digit].append(elem)\n",
    "        pos = 0\n",
    "        print(buckets)\n",
    "        for bucket in buckets:\n",
    "            for elem in bucket:\n",
    "                array[pos] = elem\n",
    "                pos += 1\n",
    "        print(\"sequence after extraction from buckets:\")\n",
    "        print(array, \"\\n\")\n",
    "        iteration += 1\n",
    "        \n",
    "array = [234, 855, 849, 454]\n",
    "sort(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Möchte man nicht Dezimalzahlen, sondern Zahlen in einer anderen Repräsentation sortieren, verwendet man einfach die entsprechende Basis (also z.B. 2 bei einer Binärrepräsentation) anstelle der 10. Das allgemeine Verfahren findet sich auf den Vorlesungsfolien."
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}