282_sort_in_python.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sort in Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der in Python implementierte Sortieralgorithmus ist eine\n",
    "  Kombination von Insertionsort und Mergesort und wird nach\n",
    "  seinem Erfinder **Tim Peters**\n",
    "  <a href=\"https://de.wikipedia.org/wiki/Timsort\">Timsort</a>\n",
    "  genannt.\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Eine Liste sortieren"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 23, 28, 37, 45, 45, 66, 80, 97]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# a wird sortiert\n",
    "a = [45, 97, 80, 23, 28, 66, 45, 37, 3]\n",
    "a.sort()               \n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[97, 80, 66, 45, 45, 37, 28, 23, 3]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.sort(reverse=True)\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Eine neue sortierte Liste erstellen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([45, 97, 80, 23, 28, 66, 45, 37, 3],\n",
       " [3, 23, 28, 37, 45, 45, 66, 80, 97],\n",
       " [97, 80, 66, 45, 45, 37, 28, 23, 3])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# a bleibt unverändert\n",
    "a = [45, 97, 80, 23, 28, 66, 45, 37, 3]\n",
    "b = sorted(a)          \n",
    "c = sorted(a,reverse=True)\n",
    "a, b, c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Mit einer key-Funktion sortieren"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[45, 80, 45, 66, 97, 37, 23, 28, 3]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Werte nach Modulo 5 sortiern\n",
    "a = [45, 97, 80, 23, 28, 66, 45, 37, 3]\n",
    "def f(x):\n",
    "    return x % 5\n",
    "a.sort(key = f)\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Mit einer key-Funktion nach mehreren Kriterien sortieren"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[45, 45, 80, 66, 37, 97, 3, 23, 28]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Werte erst nach Modulo 5, dann nach Größe sortieren\n",
    "a = [45, 97, 80, 23, 28, 66, 45, 37, 3]\n",
    "def f(x):\n",
    "    return x % 5, x\n",
    "a.sort(key = f)\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Mit einer anonymen Funktion sortieren"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[45, 80, 45, 66, 97, 37, 23, 28, 3]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [45, 97, 80, 23, 28, 66, 45, 37, 3]\n",
    "a.sort(key = lambda x: x % 5)\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[45, 45, 80, 66, 37, 97, 3, 23, 28]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [45, 97, 80, 23, 28, 66, 45, 37, 3]\n",
    "a.sort(key = lambda x: (x % 5 , x))\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Erik', 'Lena', 'Maike', 'Malte', 'Sören', 'Thorben']"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Strings nach der Länge, dann alphabetisch sortieren\n",
    "a = ['Thorben','Lena','Maike','Sören','Erik','Malte']\n",
    "a.sort(key = lambda x: (len(x),x))\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Anwendungsbeispiel: Greedy-Algorithmus für Rucksack-Problem\n",
    "\n",
    "Vorbemerkung: die zip- und range-Funktion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 6), (2, 7), (3, 8), (4, 9)]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1,2,3,4]\n",
    "b = [6,7,8,9]\n",
    "list(zip(a,b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(range(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 6, 0), (2, 7, 1), (3, 8, 2), (4, 9, 3)]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(zip(a,b,range(4)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Rucksack-Problem: Fülle einen Rucksack so, dass der Wert der Dinge möglichst groß ist und die Gewichtsgrenze nicht überschritten wird."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Items =  0 1 2 6\n",
      "Wert = 10 Gewicht = 9\n"
     ]
    }
   ],
   "source": [
    "wert = [1,1,1,10,10,13,7]\n",
    "gewicht = [2,2,2,5,5,8,3]\n",
    "kapazitaet = 10\n",
    "\n",
    "anzahl = len(wert)\n",
    "taken = set()\n",
    "\n",
    "wg = list(zip(wert,gewicht,range(anzahl)))     # Liste aus Tupels (wert,gewicht,nr)\n",
    "\n",
    "wg.sort(key=lambda x: x[1])                    # die leichtesten zuerst\n",
    "#wg.sort(reverse = True)                        # die wertvollsten zuerst\n",
    "#wg.sort(key=lambda x: x[0]/x[1], reverse=True) # die wertdichtesten zuerst\n",
    "\n",
    "rucksack_gewicht = 0\n",
    "rucksack_wert = 0\n",
    "\n",
    "for item in wg:\n",
    "    if rucksack_gewicht + item[1] <= kapazitaet:\n",
    "        rucksack_gewicht+=item[1]\n",
    "        rucksack_wert+=item[0]\n",
    "        taken.add(item[2])\n",
    "\n",
    "print('Items = ',*taken)\n",
    "print('Wert =',rucksack_wert, 'Gewicht =',rucksack_gewicht)"
   ]
  },
  {
   "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}