TP8.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "17dcd98b",
   "metadata": {},
   "source": [
    "# ITC - MPSI\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58c9bd1f",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "54a4e5c80ee83ccc13a5c745c61ae7d9",
     "grade": false,
     "grade_id": "cell-ae5993f5fef5ce05",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# TP8 : Tris"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63301835",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "cc24b8465ace1a45fd6568b4adda7164",
     "grade": false,
     "grade_id": "cell-7b1fd7724691b1e9",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "La question du tri de données apparaît naturellement dans beaucoup de problèmes de traitement de données:\n",
    "\n",
    "* tenir à jour un répertoire de personnes\n",
    "* retrouver (de façon répétitive) une données dans un grand ensemble de données (et donc en particulier dans tout contexte de bases de données, big data)\n",
    "* faire l'intersection entre deux ensemble\n",
    "* trouver l'enveloppe convexe d'un ensemble de points"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08dcf8e6",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "58d975afc935629d2bd48aafd44b97e1",
     "grade": false,
     "grade_id": "cell-a711b1ad29b5bce5",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "De nombreux algorithmes de tri ont été développés, plus ou moins efficaces selon les situations.\n",
    "Nous avons déjà vu un algorithme de tri: le [tri bulle](../tp4/TP4.ipynb).\n",
    "    \n",
    "Si on donne $n$ entrées à trier au tri bulle, il fait au plus :\n",
    "* une boucle où il parcourt toute la liste (donc $n-1$ comparaisons), puis\n",
    "* une boucle où il effectue $n-2$ comparaisons, \n",
    "* et cela diminue petit à petit, jusqu'à atteindre une boucle avec une unique comparaison.\n",
    "Ainsi le nombre de comparaisons effectuées est au plus de \n",
    "$$(n-1) + (n-2) + \\dots + 1 = \\frac{n(n-1)}{2}.$$\n",
    "\n",
    "Nous allons voir d'autres algorithmes de tri et comparer leur vitesse d'exécution. Pour chacun de ces algorithmes, on supposera qu'on dispose d'une liste d'objets comparables à ordonner (dans l'ordre croissant).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1afa4b10",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "c34aaedffe64fb3864b9def9c06ae1fb",
     "grade": false,
     "grade_id": "cell-9b43dba77962b202",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Une des propriétés du tri bulle est qu'il est _en place_ : on ne crée pas de nouvelle liste, on se sert de l'emplacement de la liste fournie en argument pour trier.\n",
    "\n",
    "Voici une correction pour le tri bulle, suivie d'un test de temps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "79fa755a",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "007b387bf13a748ee1eaff42f09e619a",
     "grade": false,
     "grade_id": "cell-b203c7950a5088d6",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def tri_bulle(liste) :\n",
    "    \"\"\"liste : liste d'entiers\n",
    "    sortie : les cases de liste contenant initialement des nombres impairs contiennent maintenant 0\"\"\"\n",
    "    permutation = True\n",
    "    n = len(liste)\n",
    "    while permutation :\n",
    "        permutation = False\n",
    "        for i in range(n-1):\n",
    "            if liste[i] > liste[i+1] : # si ce n'est pas dans le bon ordre, on permute\n",
    "                liste[i], liste[i+1] = liste[i+1], liste[i]\n",
    "                permutation = True\n",
    "        n = n - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9d4d5fb",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "a7bbe3597788434327273a0a7b1d490d",
     "grade": false,
     "grade_id": "cell-bba882dad5887a7e",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Et un test de temps (on admet que prendre la liste suivante n'est pas un biais):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fc6b696c",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "eec4325be58868d042f31e4b7cbe28b7",
     "grade": false,
     "grade_id": "cell-318216564aed8a67",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = list(range(1000, 0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "88bfe8ee",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "6b48fe5496e3383ab868fd7e5122aaeb",
     "grade": false,
     "grade_id": "cell-b25d19ba678a06dc",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "%%timeit\n",
    "tri_bulle(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd45fbcf",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "fe15b51306685b6ef2f0b451e39ca652",
     "grade": false,
     "grade_id": "cell-6d03cd0b8aefd177",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exo 1 : Tri par sélection\n",
    "\n",
    "Le principe du tri par sélection est le suivant :\n",
    "\n",
    "* chercher l'élément le plus petit et l'inverser avec le premier élément de la liste\n",
    "* chercher le second élément le plus petit et l'inverser avec le deuxième élément de la liste\n",
    "* etc.\n",
    "\n",
    "Ce principe est illustré par l'animation : \n",
    "<a title=\"Joestape89, CC BY-SA 3.0 &lt;http://creativecommons.org/licenses/by-sa/3.0/&gt;, via Wikimedia Commons\" href=\"https://commons.wikimedia.org/wiki/File:Selection-Sort-Animation.gif\"><img width=\"64\" alt=\"Selection-Sort-Animation\" src=\"https://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ef1f495",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "59a2980c327c3cd13f82f2e3f931de94",
     "grade": false,
     "grade_id": "cell-23169b4ed6889b1d",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Le tri par insertion comprend, comme le tri bulle, deux boucles imbriquées: à chaque étape il faut parcourir ce qui reste à trier dans le tableau et on fait des comparaisons pour trouver le plus petit élément dans ce qui reste. On fait donc autant de comparaisons que dans le tri bulle, mais a priori moins d'inversions (une seule à chaque étape pour le tri par insertion)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1376450",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "3c2c16dfc787185c327731b44ed8f47e",
     "grade": false,
     "grade_id": "cell-4397c169251aa095",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "1. Écrire et documenter une fonction `indice_min` qui prend en argument une liste supposée non vide et un entier `k` supposé strictement inférieur à la longueur de la liste, et renvoie l'indice de la première occurence de l'élément minimal dans la liste à partir de l'indice `k`.\n",
    "\n",
    "Par exemple `indice_min([1, 2, 3, 1, 2, 3], 1)` renvoie `3`.\n",
    "\n",
    "Utiliser `assert` pour vérifier les pré-conditions (liste non vide et entier strictement inférieur à la longueur de la liste). En `python`, l'opérateur \"et\" entre booléens est `and`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "38dd63d1",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a99783a380998bc57951ad8f66083c1d",
     "grade": false,
     "grade_id": "cell-35f598dfb42c3360",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "68030a2d",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "20f2434811a9007ca3937d695472a691",
     "grade": true,
     "grade_id": "cell-6e9a98f6d4594426",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "assert(indice_min([1], 0) == 0)\n",
    "assert(indice_min([1, 1, 2, 3, 1], 0) == 0)\n",
    "assert(indice_min([3, 2, 1, 2, 3, 1, 2, 3], 0) == 2)\n",
    "assert(indice_min([3, 2, 3, 2, 1, 1], 0) == 4)\n",
    "assert(indice_min([3, 2, 3, 2, 1], 0) == 4)\n",
    "assert(indice_min([1, 2, 3, 1, 2, 3], 1) == 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8545fbbd",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "beacf266defe71daa3e0259819bedcfe",
     "grade": false,
     "grade_id": "cell-8d01888f4b38ebc4",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "2. Écrire et documenter une fonction _itérative_ (c'est-à-dire non récursive, mais avec une boucle) `selection_iter` qui prend en argument une liste de nombres (sans avoir à le vérifier) et la trie en place sur le principe du tri par sélection.\n",
    "\n",
    "Si `a` et `b` sont des variables, on peut inverser leurs valeurs en écrivant `a, b = b, a`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b6e19af",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "6ece88b6c2ffe561fd5085ce4da68235",
     "grade": false,
     "grade_id": "cell-9a669e06dc35089f",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d18cdbd7",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "05401a6a81457bc3aed12a5bc4fea98c",
     "grade": true,
     "grade_id": "cell-b10681bc5bc6422e",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = []\n",
    "selection_iter(L)\n",
    "assert(L == [])\n",
    "\n",
    "L = [3]\n",
    "selection_iter(L)\n",
    "assert(L == [3])\n",
    "\n",
    "L = [5, 4, 3, 2, 1]\n",
    "selection_iter(L)\n",
    "assert(L == [1, 2, 3, 4, 5])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "699e9578",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "eebde3044f0d51acd9b52847652e6dbf",
     "grade": false,
     "grade_id": "cell-4a1d7b91cc95d6aa",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "3. Écrire et documenter une fonction _récursive_ (rappel : cela signifie qu'elle s'appelle elle-même) `selection_rec` qui prend en argument une liste de nombres (sans avoir à le vérifier) et un entier positif ou nul `k` et trie en place la liste à partir de l'élément d'indice `k` sur le principe du tri par sélection. La pré-condition sera testée avec `assert`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "036bd7a0",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "3c6b8faf05b005c5c3e45c4d75c8831c",
     "grade": false,
     "grade_id": "cell-68853861a7925932",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e4d26a7e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "f53ae083348d4f118b6dffd72b37c8b3",
     "grade": true,
     "grade_id": "cell-45fdf452114aa687",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = []\n",
    "selection_rec(L, 0)\n",
    "assert(L == [])\n",
    "\n",
    "L = [3]\n",
    "selection_rec(L, 0)\n",
    "assert(L == [3])\n",
    "\n",
    "L = [5, 4, 3, 2, 1]\n",
    "selection_rec(L, 0)\n",
    "assert(L == [1, 2, 3, 4, 5])\n",
    "\n",
    "L = [3, 2, 4, 1, 2, 0]\n",
    "selection_rec(L, 1)\n",
    "assert(L == [3, 0, 1, 2, 2, 4])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1d3464c",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "dc54ce19f3c77f5c3ad0795eb62cf6a7",
     "grade": false,
     "grade_id": "cell-cb165590fe7d52c1",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Vous pouvez comparer les temps d'exécution des fonctions ainsi écrites :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b23589eb",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "e7e8989f03d7a5bdde3c024c7635f3eb",
     "grade": false,
     "grade_id": "cell-67cd50334e2a38f1",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = list(range(1000, 0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "33077a2f",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "310a488a534027aca34fa22e9069b8c9",
     "grade": false,
     "grade_id": "cell-ba2369348ea09739",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "%%timeit\n",
    "selection_iter(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "418cf85e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ca2ad38459b333fa4851e4adbd526722",
     "grade": false,
     "grade_id": "cell-c8dedbd74b0b809a",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = list(range(1000, 0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "16fdff1b",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "14014ef68d6cb378d564fe3f53f06133",
     "grade": false,
     "grade_id": "cell-34c851caa2f77e99",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "%%timeit\n",
    "selection_rec(L, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6c2ef00",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "afd4c12a5341265c8b5b4ee3d83d22f0",
     "grade": false,
     "grade_id": "cell-1da8010c5fbc16e2",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exo 2 : Tri par fusion\n",
    "\n",
    "Le tri par fusion est un tri qui repose sur le principe de la dichotomie :\n",
    "* si la liste d'éléments à trier contient un élément, il n'y a plus rien à faire\n",
    "* sinon, on partage la liste en deux sous-listes\n",
    "    * on trie récursivement chacune des sous-listes\n",
    "    * on fusionne les listes ainsi obtenues\n",
    "    \n",
    "Ce tri n'est pas en place, car on a besoin de recopier toutes les données pour l'étape de fusion.\n",
    "\n",
    "Une illustration du principe du tri fusion :\n",
    "<a title=\"Swfung8, CC BY-SA 3.0 &lt;https://creativecommons.org/licenses/by-sa/3.0&gt;, via Wikimedia Commons\" href=\"https://commons.wikimedia.org/wiki/File:Merge-sort-example-300px.gif\"><img width=\"256\" alt=\"Merge-sort-example-300px\" src=\"https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0aca54d4",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "c361826c1e31f90ab36cdc95bcb56240",
     "grade": false,
     "grade_id": "cell-b27ce1cbe705320f",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "1. Écrire et documenter une fonction `copie_partielle` qui prend en argument une liste `L` et deux entiers positifs `i` et `j` tels que `i` $\\leq$ `j` $\\leq$ `len(L)` et produit une nouvelle liste qui est une copie des cases `i` à `j-1` de `L`. Les pré-conditions seront vérifiées avec `assert`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2bf0c5f7",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "f93fc923f025763f7f03660c4d3e19a4",
     "grade": false,
     "grade_id": "cell-6e7c81736ae46aeb",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9153b307",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "b5ca9316351e0b94c243b39f12721dc8",
     "grade": false,
     "grade_id": "cell-3d778854a71691bb",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "2.[difficile] Écrire et documenter une fonction `fusion` qui prend en argument :\n",
    "* une liste `L` d'entiers (sans avoir à le vérifier)\n",
    "* un entier positif ou nul `d`\n",
    "* deux entiers positifs ou nuls `l1` et `l2` tels que `d1+l1+l2` soit inférieur ou égal à la longueur de `L`\n",
    "\n",
    "On suppose de plus (sans avoir à le vérifier) que les éléments de `L` qui se situent entre les indices `d` et `d+l1-1` (compris) sont dans l'ordre croissant, et de même (toujours sans avoir à le vérifier) que les éléments de `L` qui se situent entre les indices `d+l1` et `d+l1+l2-1` (compris) sont dans l'ordre croissant.\n",
    "\n",
    "La fonction `fusion` doit fusionner les deux tranches entre les indices `d` et `d+l1-1` d'une part et entre les indices `d+l1` et `d+l1+l2` d'autre part, c'est-à-dire qu'après l'appel à `fusion`:\n",
    "* les contenus des cases de `L` d'indice strictement inférieur à `d` et supérieur ou égal à `d+l1+l2` n'ont pas été modifiés\n",
    "* les cases de `L` d'indices compris entre `d` et `d+l1+l2-1` ont globalement les mêmes valeurs, mais rangées dans l'ordre croissant.\n",
    "\n",
    "\n",
    "exemple:\n",
    "* avant l'appel à `fusion`, on a une liste `L` de la forme\n",
    "$$\\begin{array}{|c|c|c|c|c|c|c|c|}\\hline 3 & 5 & {\\color{magenta}1} & {\\color{magenta}6} & {\\color{magenta}8} & {\\color{royalblue}2} & {\\color{royalblue}7} & 4 \\\\\\hline\\end{array}$$\n",
    "Si `d`=2, `l1`=3 et `l2`=2, la case d'indice `d` est celle qui contient 1, celle d'indice `d+l1-1`, celle qui contient 8, et celle d'indice `d+l1+l2-1` celle qui contient 7.\n",
    "* après l'appel à `fusion(L, 2, 3, 2)`, on a :\n",
    "$$\\begin{array}{|c|c|c|c|c|c|c|c|}\\hline 3 & 5 & {\\color{magenta}1} & {\\color{royalblue}2} & {\\color{magenta}6} & {\\color{royalblue}7} & {\\color{magenta}8} & 4 \\\\\\hline\\end{array}$$\n",
    "\n",
    "Pour écrire cette fusion, il faut commencer par recopier les deux tranches de listes dans de nouvelles listes.\n",
    "\n",
    "Pensez bien à séparer les cas suivants:\n",
    "* s'il reste des éléments non recopiés dans les deux listes, alors il faut recopier le plus petit de tous les éléments (qui est le plus petit entre les premiers éléments non recopiés de chaque liste),\n",
    "* s'il ne reste des éléments non recopiés que dans une liste, alors il faut recopier tous ces éléments dans le même ordre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6c6d813e",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "e5a89a508fb8bed3a39a65fa844d2180",
     "grade": false,
     "grade_id": "cell-2951bee08afd6e11",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fb1da475",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "5281c255133319d4d47c5e9d62096ed5",
     "grade": true,
     "grade_id": "cell-e53a8764badee602",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = [3, 5, 1, 6, 8, 2, 7, 4]\n",
    "fusion(L, 2, 3, 2)\n",
    "assert(L == [3, 5, 1, 2, 6, 7, 8, 4])\n",
    "\n",
    "L = [1, 3, 5, 7, 2, 4, 7, 8]\n",
    "fusion(L, 0, 4, 4)\n",
    "assert(L == [1, 2, 3, 4, 5, 7, 7, 8])\n",
    "\n",
    "L = []\n",
    "fusion([], 0, 0, 0)\n",
    "assert(L == [])\n",
    "\n",
    "L = [1, 2, 3]\n",
    "fusion(L, 0, 0, 3)\n",
    "assert(L == [1, 2, 3])\n",
    "\n",
    "L = [1]\n",
    "fusion(L, 0, 1, 0)\n",
    "assert(L == [1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e336b8e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "b712707ecae81356fe0695a91ef12472",
     "grade": false,
     "grade_id": "cell-2c72d76a51d1e385",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "3. Écrire et documenter une fonction `tri_fusion` qui prend en argument une liste `L` de nombres (sans avoir à le vérifier), et deux entiers `i` et `j` positifs ou nuls tels que `i` $\\leq$ `j` $\\leq$ `len(L)` et trie les éléments de `L` entre les indices `i` et `j-1`, en suivant l'algorithme de tri fusion. Les pré-conditions seront vérifiées avec `assert`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dc5a4975",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a59b59bd3b4c811784666b9d4d9d980e",
     "grade": false,
     "grade_id": "cell-e5d08a895473d334",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dcfefb86",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9b381aa19cf5f4bba4d7f65af09a6d41",
     "grade": false,
     "grade_id": "cell-c8dedbd74b0b809b",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = list(range(1000, 0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed43ecc2",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d8f0508696d21c8d08e1844ee97de201",
     "grade": false,
     "grade_id": "cell-34c851caa2f77e98",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "%%timeit\n",
    "tri_fusion(L, 0, len(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cbe155fc",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "2fffd1c416c99390378565a4a65f0854",
     "grade": false,
     "grade_id": "cell-702ae0807c4d726e",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<div class=\"alert alert-success\">\n",
    "    <h2>Les points à retenir</h2>\n",
    "    \n",
    "* opérateur \"et\" entre booléens : `and`\n",
    "* principe du tri par insertion\n",
    "* principe du tri fusion\n",
    "* le tri fusion est plus rapide dans le pire des cas\n",
    "</div>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}