MEEF_NSI_Tris.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "MEEF-NSI-Tris.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "authorship_tag": "ABX9TyP4G1JLsuxyXVuL1lDgSQsr",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/othoni-hub/ECG1/blob/main/MEEF_NSI_Tris.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tCKsdK8mQwc9"
      },
      "source": [
        "# **UCO M1-MEEF NSI**\n",
        "\n",
        "**TP Algorithmes de tris - Approches de la complexité**\n",
        "\n",
        "**Olivier THÖNI** - UCO-IFUCOME (groupes \"Mathématiques\" et \"NSI\")\n",
        "\n",
        "<img src=\"https://drive.google.com/uc?id=12Wo3LubGGT4qOvYFAuLP4CyCuwjKNVuk\" width=\"230\" height=\"150\" align = \"right\"/>\n",
        "\n",
        "*document à l'usage exclusif des personnes un jour actrices (enseignant·es, étudiant·es) du master MEEF NSI de l'UCO*\n",
        "\n",
        "\n",
        "---\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qvgfXzU2roSE"
      },
      "source": [
        "Ce Notebook est à rapprocher de la leçon d'oral L08."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CdWfx4Hp-PeB"
      },
      "source": [
        "## **0. Outils généraux**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E8fvL-lTR-IJ"
      },
      "source": [
        "\n",
        "### **0.a/ Générer une liste d'entiers classée aléatoirement**\n",
        "\n",
        "Soit N un entier on cherche à générer une liste des entiers de 1 à N, classés aléatoirement.\n",
        "\n",
        "* **Idée algorithmique :**\n",
        "\n",
        "On génère une liste aléatoire de flottants tous entre 0 et 1, et pour chacun, on détermine le nombre d'éléments de la liste qui lui sont supérieurs."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9hu4BAlrSQpG"
      },
      "source": [
        "def liste_aleatoire(N) :\n",
        "    ''' Cette fonction reçoit en entrée un entier N\n",
        "    et renvoie une liste L des entiers de 1 à N, dans un ordre aléatoire'''\n",
        "\n",
        "    import numpy.random as rd\n",
        "    U = rd.random(N)\n",
        "    #print(U)\n",
        "    L = [sum(U >= U[i]) for i in range(N)]\n",
        "    return L\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aUVh2Te9S-2e",
        "outputId": "96a7ee2b-4964-4213-b530-2e69fc4142cc"
      },
      "source": [
        "liste_aleatoire(5)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[3, 2, 1, 5, 4]"
            ]
          },
          "metadata": {},
          "execution_count": 455
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FFFsSQwmUoTO"
      },
      "source": [
        "### **0.b/ Tester si une liste est classée**\n",
        "\n",
        "* **Idée algorithmique**\n",
        "\n",
        "Pour vérifier si une liste est classée en ordre croissant, on teste, si chaque terme est inférieur (ou égal si la liste à classer peut comporter des doublons) au suivant."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SeG4eBi5Uhay"
      },
      "source": [
        "def classee(Liste):\n",
        "    '''Cette fonction reçoit une liste \n",
        "    et retourne vrai si la liste est rangée dans l'ordre croissant'''\n",
        "\n",
        "    test = True\n",
        "    k = 0\n",
        "    while test == True and k < len(Liste) - 1:\n",
        "        if Liste[k] > Liste[k+1]:\n",
        "            test = False\n",
        "        k = k+1\n",
        "    return test\n",
        "\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PgW6AohVJ_e_"
      },
      "source": [
        "**tests :**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wjztiMYeWUL6",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "019c2096-cd7a-447e-bb6d-e6f03dabaa9b"
      },
      "source": [
        "L = [1,2,3,4,5]\n",
        "classee(L)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 457
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "UEjPg57CeDlT",
        "outputId": "f13de640-145e-4b3b-c442-87b4bd04fb28"
      },
      "source": [
        "L = [1,3,2,4,5]\n",
        "classee(L)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "False"
            ]
          },
          "metadata": {},
          "execution_count": 458
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HM8brj2F-TP1"
      },
      "source": [
        "## **1. Le tri du singe (\"*Bogo Sort*\")**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Z6H5SJYTRZD6"
      },
      "source": [
        "\n",
        "\n",
        "### **1.a/ Idée algorithmique**\n",
        "\n",
        "L'idée algorithmique est simple \n",
        "* on donne un ordre au hasard à la liste jusqu'à obtenir une liste classée...\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Dbnsx7Vdgxng"
      },
      "source": [
        "### **1.b/ Programmation**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KEz_JipdQvB-"
      },
      "source": [
        "def bogo_sort(N):\n",
        "    '''Cette fonction reçoit l'entier N, longueur d'une liste d'entiers,\n",
        "    exécute la fonction \"liste_aleatoire\" jusqu'à ce que le résultat soit une liste rangée dans l'ordre croissant\n",
        "    et renvoie le nombre d'itérations'''\n",
        "\n",
        "    L = liste_aleatoire(N)\n",
        "    #print(L)\n",
        "    k = 1\n",
        "    while not(classee(L)):\n",
        "        L = liste_aleatoire(N)\n",
        "        #print(L)\n",
        "        k = k+1\n",
        "    return k"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6faFDFoWlEjT"
      },
      "source": [
        "**test**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "s22Ekm_ievK5",
        "outputId": "cee2ab60-e6f7-431d-c5fe-bf4862b98c58"
      },
      "source": [
        "N = 5\n",
        "print('Bogo Sort sur une liste de ' + str(N) +' valeurs :')\n",
        "print(\"Nombre d'itérations nécessaires : \" + str(bogo_sort(N)))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Bogo Sort sur une liste de 5 valeurs :\n",
            "Nombre d'itérations nécessaires : 206\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NCcV--8m-aYr"
      },
      "source": [
        "### **1.c/ Terminaison et complexité**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KkUQQrqx-g6f"
      },
      "source": [
        "#### **1.c/*(i)* Terminaison**\n",
        "\n",
        "La 1<sup>ère</sup> vertu que l'on attend de l'exécution d'un algorithme est qu'il se termine un jour... Car l'éternité, c'est long, surtout vers la fin !!!\n",
        "\n",
        "On étudie alors les structures répétitives, et on observe ce qui assure qu'elles vont se terminer :\n",
        "* s'il s'agit d'une **boucle bornée**, aucun souci, on n'y passe qu'un nombre fini de fois.\n",
        "\n",
        "* s'il s'agit d'une **boucle non bornée**, on cherche le **\"variant de boucle\"** : la quantité qui intervient dans le test de sortie de la boucle, et qui doit, à chaque étape, progresser vers la sortie.\n",
        "\n",
        "**exemple :** \"*Tant que k > 1...*\" : si k ne diminue pas à chaque étape, il y a un risque que la boucle ne s'arrête jamais...\n",
        "\n",
        "* s'il s'agit d'une **fonction récursive**, il en est de même : elle contient ce qu'il faut exécuter pour faire cesser les appels récursifs, et ce qui permettra que cette condition soit atteinte, c'est le même principe que le variant de boucle."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0-THens4AQp6"
      },
      "source": [
        "Dans le cas du **bogo-sort**, on ne pourra pas prouver la terminaison de ce programme autrement que par des arguments probabilistes : le risque que le hasard ne sorte jamais la liste classée tend vers 0.\n",
        "\n",
        "Les mathématiciens disent qu'ils sont \"*presque sûrs*\" que cela arrivera, ce qui signifie qu'ils sont sûrs que cela arrivera, mais qu'ils ne savent pas dire quand (on ne peut pas \"*majorer*\" le nombre d'itérations nécessaires).\n",
        "Mais comme la probabilité dont il est question plus haut est décroissante et est une valeur positive, elle forme une suite de valeurs convergente (en maths, cela s'appelle le \"*théorème de la limite monotone*\")\n",
        "\n",
        "*Prenons un exemple : si l'on joue à \"Pile\" ou \"Face\", la probabilité pour que le 1<sup>er</sup> \"Pile\" sorte au bout de 5 lancers de la pièce est de : $p_5 = \\frac{1}{2} \\times\\frac{1}{2} \\times\\frac{1}{2} \\times\\frac{1}{2} \\times\\frac{1}{2} = \\left ( \\frac{1}{2} \\right )^5 = 0.03125$.*\n",
        "\n",
        "*La probabilité que cela demande 6 lancers est encore deux fois plus petite : $p_6 =  \\left ( \\frac{1}{2} \\right )^6 $.*\n",
        "\n",
        "*On ne sait pas dire quand le premier \"Pile\" arrivera, on ne peut même pas assurer qu'il faudra moins de 10000 coups, mais on est sûr que ça arrivera...*\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-6ib2XRdgue4"
      },
      "source": [
        "#### **1.c/*(ii)* 1<sup>ère</sup> mesure de la complexité**\n",
        "\n",
        "La complexité est l'instrument de mesure du temps d'exécution du programme, et de la place en mémoire qu'il occupera.\n",
        "\n",
        "Le nombre d'itérations est un bon indicateur de la complexité en temps.\n",
        "Ici, on peut aussi ajouter un compteur dans la fonction \"classee()\", qui s'incrémente après chaque comparaison. Il faut alors le passer en paramètre et le retourner en fin de fonction.\n",
        "\n",
        "**On exprime la complexité en donnant un ordre de grandeur, qui dépend, pour un tri, du nombre de données N à trier.**\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ILXvRLvQ6RVT"
      },
      "source": [
        "**Résultat théorique :** \n",
        "\n",
        "Il y a 5! (5x4x3x2x1) = 120 façons de ranger 5 nombres. En moyenne, il faudra donc 120 itérations pour que le hasard sorte une liste classée, mais cette moyenne est très instable !\n",
        "Et à chaque liste proposée, il faudra un parcours contenant 5 (+ ou - 1) comparaisons.\n",
        "Le résultats comprendra alors 5x5! = 240 actions significatives (dépendant du nombre N d'éléments dans la liste initiale.\n",
        "\n",
        "Plus généralement, s'il y a N valeurs à classer, il faudra en moyenne $N!$ essais avant que le hasard ne sorte une liste déjà rangée, et il faudra (N-1) comparaisons pour tester une liste.\n",
        "\n",
        "N-1 et N, quand N est grand, sont du même ordre de grandeur.\n",
        "\n",
        "Ainsi, en tout, **l'algorithme \"*Bogo-Sort*\" aura une complexité en ${N \\times N!}$.**\n",
        "\n",
        "**On écrira que la complexité est en $\\mathcal{O} (N\\times N!)$, ce que l'on lit en \"La complexité est un \"Grand-O\" de ${N \\times N!}$\".**\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YVPNMpGvGKwz"
      },
      "source": [
        "**Régles de calcul sur les $\\mathcal{O} (...)$ :**\n",
        "\n",
        "Ces notations sont appelées **\"Notation de Landau\"**, voici quelques règles de calcules avec les $\\mathcal{O} (...)$.\n",
        "\n",
        "Plutôt que de compter exhaustivement le nombre d'itérations nécessaires, on fait, grâce aux **\"Grand-O\"** des arrondis à chaque étape.\n",
        "\n",
        "Ainsi , si $\\alpha$ et $\\beta$ sont des nombres réels non nul, \n",
        "* un $\\mathcal{O} (N^\\alpha)$ + un $\\mathcal{O} (N^\\alpha)$ reste un $\\mathcal{O} (N^\\alpha)$.\n",
        "* un $\\mathcal{O} (N^\\alpha)$ + un $\\mathcal{O} (N^\\beta)$ donne un $\\mathcal{O} (N^\\alpha)$ dès lors que $\\alpha > \\beta$.\n",
        "* un $\\mathcal{O} (N^\\alpha)$ multiplié par un réel reste un $\\mathcal{O} (N^\\alpha)$.\n",
        "* un $\\mathcal{O} (N^\\alpha)$ multiplié par un $\\mathcal{O} (N^\\beta)$ donne un $\\mathcal{O} (N^{\\alpha + \\beta})$.\n",
        "* le logarithme d'un $\\mathcal{O} (N^\\alpha)$ (comprendre \"le logarithme d'une quantité dont l'ordre de grandeur est $N^\\alpha$\") donne un $\\mathcal{O} (ln(N^\\alpha))$, c'est-à-dire un $\\alpha \\mathcal{O} (ln(N))$, en vertu des propriétés de la fonction logarithme, c'est-à-dire en définitive un $\\mathcal{O} (ln(N))$.\n",
        "* l'exponentielle d'un $\\mathcal{O} (N^\\alpha)$ donne un $\\mathcal{O} (e^{(N^\\alpha)})$, c'est-à-dire un $ \\mathcal{O} (e^{\\alpha \\times N})$, ou encore $\\mathcal{O} (e^\\alpha \\times e^{N})$, en vertu des propriétés de la fonction exponentielle, c'est-à-dire finalement un $\\mathcal{O} (e^{N})$.\n",
        "* etc.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Nws1mbmEST-H"
      },
      "source": [
        "**Croissances comparées des ordres de grandeurs**\n",
        "\n",
        "<img src=\"https://drive.google.com/uc?id=11cyRPEoJe34la4sOCua6EfwjKw3cLnC4\" width=\"600\" height=\"420\" />\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5ljUngE9iJ4X"
      },
      "source": [
        "### **1.d/ Relevé du nombre d'itérations pour un nombre variable N de valeurs**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_EBvnBYUiiIF"
      },
      "source": [
        "Nous allons effectuer un relevé du nombre d'itérations pour le Bogo Sort, selon le nombre N de valeurs à trier.\n",
        "\n",
        "Nous générerons un fichier csv, que nous irons traiter dans un tableur, pour récupérer l'équation d'une courbe de tendance."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "olhRQ3_Rgk41",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "3372c33b-231e-4b92-d8f6-0060f4113d13"
      },
      "source": [
        "liste_N = list(range(3,9))*4\n",
        "liste_nb_iter = [bogo_sort(N) for N in liste_N]\n",
        "liste_nb_iter"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1,\n",
              " 80,\n",
              " 85,\n",
              " 1992,\n",
              " 9311,\n",
              " 59975,\n",
              " 2,\n",
              " 10,\n",
              " 41,\n",
              " 697,\n",
              " 7169,\n",
              " 39964,\n",
              " 11,\n",
              " 23,\n",
              " 134,\n",
              " 487,\n",
              " 3626,\n",
              " 50904,\n",
              " 8,\n",
              " 26,\n",
              " 90,\n",
              " 1235,\n",
              " 8292,\n",
              " 157703]"
            ]
          },
          "metadata": {},
          "execution_count": 461
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GgIyzzq8xLRl"
      },
      "source": [
        "* **écriture des résultats dans un fichier *.csv***"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KVfsJYoBexzj",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 17
        },
        "outputId": "0c155456-6395-4f1e-d371-8448789dd752"
      },
      "source": [
        "import csv\n",
        "\n",
        "with open('SauvegardeTable1.csv', 'w', newline='') as csvfile:\n",
        "    writer = csv.writer(csvfile, delimiter=';')\n",
        "    writer.writerow(liste_N)\n",
        "    writer.writerow(liste_nb_iter)\n",
        "\n",
        "from google.colab import files\n",
        "files.download(\"SauvegardeTable1.csv\")"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "application/javascript": [
              "\n",
              "    async function download(id, filename, size) {\n",
              "      if (!google.colab.kernel.accessAllowed) {\n",
              "        return;\n",
              "      }\n",
              "      const div = document.createElement('div');\n",
              "      const label = document.createElement('label');\n",
              "      label.textContent = `Downloading \"${filename}\": `;\n",
              "      div.appendChild(label);\n",
              "      const progress = document.createElement('progress');\n",
              "      progress.max = size;\n",
              "      div.appendChild(progress);\n",
              "      document.body.appendChild(div);\n",
              "\n",
              "      const buffers = [];\n",
              "      let downloaded = 0;\n",
              "\n",
              "      const channel = await google.colab.kernel.comms.open(id);\n",
              "      // Send a message to notify the kernel that we're ready.\n",
              "      channel.send({})\n",
              "\n",
              "      for await (const message of channel.messages) {\n",
              "        // Send a message to notify the kernel that we're ready.\n",
              "        channel.send({})\n",
              "        if (message.buffers) {\n",
              "          for (const buffer of message.buffers) {\n",
              "            buffers.push(buffer);\n",
              "            downloaded += buffer.byteLength;\n",
              "            progress.value = downloaded;\n",
              "          }\n",
              "        }\n",
              "      }\n",
              "      const blob = new Blob(buffers, {type: 'application/binary'});\n",
              "      const a = document.createElement('a');\n",
              "      a.href = window.URL.createObjectURL(blob);\n",
              "      a.download = filename;\n",
              "      div.appendChild(a);\n",
              "      a.click();\n",
              "      div.remove();\n",
              "    }\n",
              "  "
            ],
            "text/plain": [
              "<IPython.core.display.Javascript object>"
            ]
          },
          "metadata": {}
        },
        {
          "output_type": "display_data",
          "data": {
            "application/javascript": [
              "download(\"download_fe8f45bc-2d93-4475-a019-7a44cb2239f7\", \"SauvegardeTable1.csv\", 147)"
            ],
            "text/plain": [
              "<IPython.core.display.Javascript object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZvwUMUt8GHe"
      },
      "source": [
        "* **affichage de la courbe de tendance dans le tableur**\n",
        "\n",
        "Le bloc de commmande ci-dessus télécharge le fichier csv obtenu.\n",
        "On l'ouvre dans un tableur, on génère un nuage de points avec les deux lignes du tableau, puis on demande une **\"courbe de tendances\"** dont on fait affficher l'équation.\n",
        "\n",
        "\n",
        "\n",
        "<img src=\"https://drive.google.com/uc?id=188jpwbDg-phZsf9Z4qNmKWDssjB1oAVh\" width=\"800\" height=\"300\" />\n",
        "\n",
        "On voit qu'une complexité exponentielle est dépassée ($N!$ est du même ordre de grandeur que l'exponentielle)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lcKb2B2INIxQ"
      },
      "source": [
        "**La pareille dans Google Sheet**\n",
        "\n",
        "* Ouvrir le fichier téléchargé dans Excel et l'enregistrer en **.xlsx**.\n",
        "\n",
        "* L'importer dans **Google Drive**, et l'ouvrir ave **Google Sheet**.\n",
        "* **Insérer** le **nuage de  points**, double-cliquer sur un des points du nuage pour faire afficher l'**éditeur de graphiques**, puis dans le choix **\"Série\"**, demander la **courbe de tendance**.\n",
        "\n",
        "<img src=\"https://drive.google.com/uc?id=15EKXLe9X4b62IgG4WPoo5BSxy18Ep3E0\" width=\"800\" height=\"300\" />\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZG_1LZjNeoft"
      },
      "source": [
        "## **2. Le tri par sélection**\n",
        "\n",
        "### **2.a/ Principe algorithmique**\n",
        "* On parcourt la liste non triée à la recherche du plus grand élément, \n",
        "* on le permute avec le dernier,\n",
        "* on recommence avec la liste privée du dernier élément, qui devient la nouvelle liste non triée, \n",
        "* jusqu'à ce que la liste non triée ne contienne plus qu'un élément.\n",
        "\n",
        "On dit que ce type de tri se déroule \"en place\" car on n'a pas besoin de recopier la liste."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7qY8NNE_qaR3"
      },
      "source": [
        "### **2.b/ Correction de l'algorithme : notion d'invariant de boucle**\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "e8WNvksHgVPf"
      },
      "source": [
        "\n",
        "\n",
        "#### **2.b/*(i)* : De quoi s'agit-il ?**\n",
        "\n",
        "Après la terminaison, la 2<sup>nde</sup> vertu que l'on attend d'une fonction ou d'un algorithme est qu'ils founissent le résultat pour lequel ils ont été spécifiés, c'est ce que l'on appelle la **correction**.\n",
        "\n",
        "Établir la correction d'un algorithme, c'est s'assurer que, quelles que soient les données qu'on lui fournira en entrée, il produira bien le résultat qu'on attend de lui.\n",
        "\n",
        "Pour un algorithme de tri, il faut qu'on s'assure... qu'il trie...\n",
        "\n",
        "L'outil utilisé pour prouver la correction est l'**invariant de boucle**. On désigne sous cette appellation une **propriété qui, si elle était vraie avant la boucle, reste vraie à la sortie**.\n",
        "\n",
        "C'est le principe mathématique de **récurrence**.\n",
        "\n",
        "Pour établir selon le **principe de récurrence** une propriété que nous nommerons  $(\\mathcal{P}_n)$ quel que soit l'entier n, \n",
        "* 1. **initialisation :**\n",
        "On vérifie que la propriété $(\\mathcal{P}_0)$ est vraie, c'est-à-dire dans l'état initial $n=0$,\n",
        "* 2. **hérédité :**\n",
        "puis on établit que, si cette propriété est vraie après $k$ itérations, c'est-à-dire que $(\\mathcal{P}_k)$ est vraie, alors, elle est vraie aussi après $k+1$ itérations, c'est-à-dire que $(\\mathcal{P}_{k+1})$ est vraie."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "84lER-i8rNLx"
      },
      "source": [
        "#### **2.c/*(ii)* Démonstration de la correction de l'algorithme de tri par sélection**\n",
        "\n",
        "Il s'agit de démontrer que, quel que soit la liste fournie en entrée $L$, de longueur $N$, on a bien en sortie la même liste, mais triée.\n",
        "\n",
        "Considérons la propriété : $(\\mathcal{P}_n)$ : **\"*Quel que soit l'entier $n$ compris entre 0 et $N$, après $n$ itérations, la sous-liste de $n$ éléments placés à droite de la liste :  $L[N - n - 1,N-1]$ est triée.*\"**\n",
        "\n",
        "* La propriété est initialisée : en effet, après 0 itération, la liste L contient *a priori* 0 élément trié en fin de liste. $(\\mathcal{P}_0)$ est donc vraie.\n",
        "* Supposons maintenant que $k$ itérations aient été effectuées, et que la liste contienne aux $k$ dernières places, les $k$ plus grandes valeurs de la liste, bien triées, c'est-à-dire que la propriété $(\\mathcal{P}_k)$ est supposée vraie, \n",
        " \n",
        " alors, on va ensuite chercher le plus grand élément de l'autre sous-liste, qui est lui-même plus petit que le plus petit élément de la sous-liste triée à droite, et on va le mettre à gauche de la sous-liste triée. La sous-liste de droite contiendra bien alors les $k+1$ plus grandes valeurs de la liste $L$, triées dans l'ordre coissant. Ainsi, $(\\mathcal{P}_{k+1})$ est vraie.\n",
        "  \n",
        "  Ceci établit l'hérédité et permet de conclure, selon le principe de récurrence, que, quel que soit l'entier $n$ compris entre 0 et $N$, après l'itération n°$n$, la liste $L$ contient à sa droite ses $n$ plus grands éléments, bien triés dans l'ordre croissant.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UbKaT8TEgKWf"
      },
      "source": [
        "### **2.c/ Programmation**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FRjHQeZ22vIU"
      },
      "source": [
        "On s'interdit d'utiliser les boîtes noires telles la fonction \"max\" permettant de déterminer la valeur maximale d'une liste, car cela masquerait toute problématique de complexité..."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DUzCY-w82qqj"
      },
      "source": [
        "def cherche_max(L) :\n",
        "    '''Cette fonction reçoit en entrée une liste et retourne sa valeur maximale et son rang'''\n",
        "    maxi = L[0]\n",
        "    rang_maxi = 0\n",
        "    for k in range(1,len(L)) :\n",
        "        if L[k] > maxi :\n",
        "            maxi = L[k]\n",
        "            rang_maxi = k\n",
        "    return maxi,rang_maxi"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xahJorsa4Clv",
        "outputId": "8d660fff-8833-4813-ec62-c119ec654cd2"
      },
      "source": [
        "#test\n",
        "L = liste_aleatoire(5)\n",
        "maxi, rang_maxi = cherche_max(L)\n",
        "print(L)\n",
        "print('rang de la valeur maximale : ' + str(rang_maxi))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[5, 3, 1, 2, 4]\n",
            "rang de la valeur maximale : 0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dGNiTGGA45Z3"
      },
      "source": [
        "def tri_selection(L) :\n",
        "    '''Cette fonction reçoit une liste et retourne le nombre d'itérations pour que cette liste soit rangée dans l'ordre croissant'''\n",
        "    longueur = len(L)\n",
        "    k = 1\n",
        "    while longueur > 1:\n",
        "        maxi, rang_maxi = cherche_max(L[0:longueur])\n",
        "        L[rang_maxi], L[longueur-1] = L[longueur-1], L[rang_maxi] # permutation\n",
        "        print(L)\n",
        "        longueur = longueur - 1\n",
        "        k = k+1\n",
        "    return k"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8-mglazd7yf-",
        "outputId": "bfc88903-39a2-4c08-cb0a-3236dc4ca704"
      },
      "source": [
        "L = liste_aleatoire(5)\n",
        "print(L)\n",
        "k = tri_selection(L)\n",
        "k"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[4, 3, 1, 2, 5]\n",
            "[4, 3, 1, 2, 5]\n",
            "[2, 3, 1, 4, 5]\n",
            "[2, 1, 3, 4, 5]\n",
            "[1, 2, 3, 4, 5]\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5"
            ]
          },
          "metadata": {},
          "execution_count": 466
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rOXE8ajmgQsq"
      },
      "source": [
        "### **2.d/ Terminaison et complexité**\n",
        "\n",
        "La longueur de la liste restant à trier (**variant de la boucle**) va en décroissant, jusqu'à valoir 1 (où la sous-liste à trier ne contiendra plus alors qu'un élément, et sera donc, de fait, triée). Donc l'algorithme se termine.\n",
        "\n",
        "* La fonction de recherche du maximum d'une liste de longueur $n$, demande $n$ itérations.\n",
        "* Cette fonction va être parcourue d'abord sur la liste de longueur $N$, puis sur une liste de longueur $N-1$, puis $N-2$, etc. jusqu'à une liste de longueur 1.\n",
        "Elle sera donc parcourue $1+2+...+(N-1)+N$ fois, ce que l'on note en mathématiques :  \n",
        "$$\\sum_{n=0}^{N}n$$\n",
        "et qui vaut, selon Gauss, $\\frac{n (n+1)}{2} = \\frac{1}{2}  ( n^2 + n) = \\mathcal{O}(n^2)$\n",
        "\n",
        "La complexité en temps de l'algorithme de tri par sélection est donc de l'ordre $\\mathcal{O}(n^2)$.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "32bj80L0fhc4"
      },
      "source": [
        "## **3. Tri par insertion**\n",
        "\n",
        "### **3.a/ Principe algorithmique**\n",
        "* On prend le premier élément de la partie liste non triée,  \n",
        "* on cherche sa place dans la partie de liste triée,\n",
        "* on l'insère à cet endroit en décalant ceux d'après d'un cran vers la droite,\n",
        "* jusqu'à ce que la liste non triée soit vide.\n",
        "\n",
        "Il s'agit, à l'instar du tri par sélection, d'un tri \"en place\" également, mais on pourrait, pour plus de lisibilité peut-être, séparer la liste triée du restant non trié."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BsFSIwgLhEgd"
      },
      "source": [
        "### **3.b/ Correction**\n",
        "\n",
        "Quel est l'invariant de boucle ?\n",
        "\n",
        "Prouver alors la correction de l'algorithme de tri par insertion."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ccFe8LOahMLy"
      },
      "source": [
        "### **3.c/ Programme**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5GPCkqUIVQx5"
      },
      "source": [
        "def cherche_place(L,valeur) :\n",
        "    '''cette fonction reçoit une sous-liste triée, et une valeur\n",
        "    Elle renvoie la place d'insertion de la valeur dans la liste'''\n",
        "    place = 0\n",
        "    for k in range(len(L)) :\n",
        "        if L[k] < valeur :\n",
        "            place = k+1\n",
        "    return place"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iFfo7M4D4YUq"
      },
      "source": [
        "**test**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "bAko47DRO1VV",
        "outputId": "22286739-95e4-493a-9684-47b06557770c"
      },
      "source": [
        "sous_liste_triee = [1]\n",
        "valeur = 2\n",
        "place = cherche_place(sous_liste_triee,valeur)\n",
        "place"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1"
            ]
          },
          "metadata": {},
          "execution_count": 468
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WlGE68bi4Xzr",
        "outputId": "a5a5f706-e63c-4c03-970a-b3b3fed703cc"
      },
      "source": [
        "L = [1,2,5,4,7,3,6]\n",
        "sous_liste_triee = [1,2,5] \n",
        "valeur = 4\n",
        "place = cherche_place(sous_liste_triee,valeur)\n",
        "place"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "metadata": {},
          "execution_count": 469
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MKrFHuf22qgZ"
      },
      "source": [
        "def insere(L, valeur):\n",
        "    '''Cette fonction reçoit une liste triée, une valeur à insérer, cherche la place d'insertion\n",
        "    et retourne la liste triée avec la valeur à sa place.'''\n",
        "    place = cherche_place(L,valeur)\n",
        "    print('rang : ' + str(place))\n",
        "    debut = L[:place]\n",
        "    debut.append(valeur)\n",
        "    fin = L[place:]\n",
        "    L = debut+fin\n",
        "    return L\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-h9kb69p57Gk"
      },
      "source": [
        "**test**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hhQU6S2gHb_m",
        "outputId": "c7ec689a-de72-4b51-8af1-892b6a50986a"
      },
      "source": [
        "sous_liste_triee = insere(sous_liste_triee , valeur)\n",
        "sous_liste_triee"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "rang : 2\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2, 4, 5]"
            ]
          },
          "metadata": {},
          "execution_count": 471
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0j_fL-1x59d0",
        "outputId": "98071660-cd01-44e9-dc48-0a4138e63981"
      },
      "source": [
        "lon = len(sous_liste_triee)\n",
        "sous_liste_non_triee = L[lon :]\n",
        "sous_liste_non_triee\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[7, 3, 6]"
            ]
          },
          "metadata": {},
          "execution_count": 472
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "AHDe3xt8HkpR",
        "outputId": "e45eac01-36e8-4798-9659-ef23999e54db"
      },
      "source": [
        "L = sous_liste_triee + sous_liste_non_triee\n",
        "L"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2, 4, 5, 7, 3, 6]"
            ]
          },
          "metadata": {},
          "execution_count": 473
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7bGE1urY3MG8"
      },
      "source": [
        "def tri_insertion(L):\n",
        "    '''Cette fonction reçoit une liste L en désordre et renvoie la liste triée en ordre croissant'''\n",
        "    longueur = len(L)\n",
        "    \n",
        "    sous_liste_triee = [L[0]]\n",
        "    sous_liste_non_triee = L[1:] #recopie superficielle\n",
        "    for k in range(1,longueur) :\n",
        "        valeur = L[k]\n",
        "        print(\"valeur à classer : \" + str(valeur))\n",
        "        sous_liste_triee = insere(sous_liste_triee , valeur)\n",
        "        lon = len(sous_liste_triee)\n",
        "        sous_liste_non_triee = L[lon :]\n",
        "        L = sous_liste_triee + sous_liste_non_triee\n",
        "        print(L)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lMgXynBwJXyE",
        "outputId": "7f34f4b3-a110-4611-b203-af60ff6cd3d3"
      },
      "source": [
        "L = [1,2,5,4,7,3,6]\n",
        "tri_insertion(L)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "valeur à classer : 2\n",
            "rang : 1\n",
            "[1, 2, 5, 4, 7, 3, 6]\n",
            "valeur à classer : 5\n",
            "rang : 2\n",
            "[1, 2, 5, 4, 7, 3, 6]\n",
            "valeur à classer : 4\n",
            "rang : 2\n",
            "[1, 2, 4, 5, 7, 3, 6]\n",
            "valeur à classer : 7\n",
            "rang : 4\n",
            "[1, 2, 4, 5, 7, 3, 6]\n",
            "valeur à classer : 3\n",
            "rang : 2\n",
            "[1, 2, 3, 4, 5, 7, 6]\n",
            "valeur à classer : 6\n",
            "rang : 5\n",
            "[1, 2, 3, 4, 5, 6, 7]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E5aPanZthQQe"
      },
      "source": [
        "### **3.d/ Terminaison et complexité**\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fPxw_eDgg6zN"
      },
      "source": [
        "#### **3.d/*(i)* Preuve et calcul**\n",
        "\n",
        "Justifier la terminaison de l'algorithme de tri pas insertion et donner un ordre de grandeur de sa complexité."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-FVRFTiqhMLN"
      },
      "source": [
        "#### **3.d/*(ii)* Mesure expérimentale de la complexité**\n",
        "\n",
        "Faisons d'abord un peu de ménage dans nos fonctions...\n",
        "\n",
        "Nous allons utiliser le temps d'exécution comme instrument de mesure de la complexité en temps... assez logique, en fait...\n",
        "\n",
        "Pour cela, introduisons un chrono dans notre fonction 'tri_insertion'\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zC7dPgqh8LJ9"
      },
      "source": [
        "import time\n",
        "from math import floor\n",
        "\n",
        "def liste_aleatoire(N) :\n",
        "    ''' Cette fonction reçoit en entrée un entier N\n",
        "    et renvoie une liste L des entiers de 1 à N, dans un ordre aléatoire'''\n",
        "\n",
        "    import numpy.random as rd\n",
        "    U = rd.random(N)\n",
        "    #print(U)\n",
        "    L = [sum(U >= U[i]) for i in range(N)]\n",
        "    return L\n",
        "\n",
        "def cherche_place(L,valeur) :\n",
        "    '''cette fonction reçoit une sous-liste triée, et une valeur\n",
        "    Elle renvoie la place d'insertion de la valeur dans la liste'''\n",
        "    place = 0\n",
        "    for k in range(len(L)) :\n",
        "        if L[k] < valeur :\n",
        "            place = k+1\n",
        "    return place\n",
        "\n",
        "def insere(L, valeur):\n",
        "    '''Cette fonction reçoit une liste triée, une valeur à insérer, cherche la place d'insertion\n",
        "    et retourne la liste triée avec la valeur à sa place.'''\n",
        "    place = cherche_place(L,valeur)\n",
        "    debut = L[:place]\n",
        "    debut.append(valeur)\n",
        "    fin = L[place:]\n",
        "    L = debut+fin\n",
        "    return L\n",
        "\n",
        "def tri_insertion(L):\n",
        "    '''Cette fonction reçoit une liste L en désordre, trie la liste en ordre croissant par le tri par insertion\n",
        "    et renvoie le temps d'exécution'''\n",
        "    t = time.time()\n",
        "\n",
        "    longueur = len(L)\n",
        "    \n",
        "    sous_liste_triee = [L[0]]\n",
        "    sous_liste_non_triee = L[1:] #recopie superficielle\n",
        "    for k in range(1,longueur) :\n",
        "        valeur = L[k]\n",
        "        sous_liste_triee = insere(sous_liste_triee , valeur)\n",
        "        lon = len(sous_liste_triee)\n",
        "        sous_liste_non_triee = L[lon :]\n",
        "        L = sous_liste_triee + sous_liste_non_triee\n",
        "\n",
        "    t = floor((time.time() - t)*1000000)\n",
        "    return t\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kZEe01iliErQ",
        "outputId": "c5f564fa-de24-4cd1-c7a9-f4f6011b2e6a"
      },
      "source": [
        "L = liste_aleatoire(100)\n",
        "print(str(tri_insertion(L)) + \" µs\")\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "704 µs\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EiTO7guXiU8g"
      },
      "source": [
        "liste_N = list(range(1,100))\n",
        "liste_temps = []\n",
        "for N in liste_N :\n",
        "    L = liste_aleatoire(N)\n",
        "    temps_exec = tri_insertion(L)\n",
        "    liste_temps.append(temps_exec)\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 17
        },
        "id": "NY9rgIIxmWYK",
        "outputId": "076b8cf8-39b0-4e0d-978b-4d8f8ba99175"
      },
      "source": [
        "import csv\n",
        "\n",
        "with open('SauvegardeTable2.csv', 'w', newline='') as csvfile:\n",
        "    writer = csv.writer(csvfile, delimiter=';')\n",
        "    writer.writerow(liste_N)\n",
        "    writer.writerow(liste_temps)\n",
        "\n",
        "from google.colab import files\n",
        "files.download(\"SauvegardeTable2.csv\")"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "application/javascript": [
              "\n",
              "    async function download(id, filename, size) {\n",
              "      if (!google.colab.kernel.accessAllowed) {\n",
              "        return;\n",
              "      }\n",
              "      const div = document.createElement('div');\n",
              "      const label = document.createElement('label');\n",
              "      label.textContent = `Downloading \"${filename}\": `;\n",
              "      div.appendChild(label);\n",
              "      const progress = document.createElement('progress');\n",
              "      progress.max = size;\n",
              "      div.appendChild(progress);\n",
              "      document.body.appendChild(div);\n",
              "\n",
              "      const buffers = [];\n",
              "      let downloaded = 0;\n",
              "\n",
              "      const channel = await google.colab.kernel.comms.open(id);\n",
              "      // Send a message to notify the kernel that we're ready.\n",
              "      channel.send({})\n",
              "\n",
              "      for await (const message of channel.messages) {\n",
              "        // Send a message to notify the kernel that we're ready.\n",
              "        channel.send({})\n",
              "        if (message.buffers) {\n",
              "          for (const buffer of message.buffers) {\n",
              "            buffers.push(buffer);\n",
              "            downloaded += buffer.byteLength;\n",
              "            progress.value = downloaded;\n",
              "          }\n",
              "        }\n",
              "      }\n",
              "      const blob = new Blob(buffers, {type: 'application/binary'});\n",
              "      const a = document.createElement('a');\n",
              "      a.href = window.URL.createObjectURL(blob);\n",
              "      a.download = filename;\n",
              "      div.appendChild(a);\n",
              "      a.click();\n",
              "      div.remove();\n",
              "    }\n",
              "  "
            ],
            "text/plain": [
              "<IPython.core.display.Javascript object>"
            ]
          },
          "metadata": {}
        },
        {
          "output_type": "display_data",
          "data": {
            "application/javascript": [
              "download(\"download_dbeb709f-2a1c-4350-b238-a7ec2f4a85ae\", \"SauvegardeTable2.csv\", 655)"
            ],
            "text/plain": [
              "<IPython.core.display.Javascript object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5o-jjvB2pjbS"
      },
      "source": [
        "**Courbe de tendances du tri par insertion, selon la taille de la liste à trier**\n",
        "\n",
        "Cela confirme le comportement en $\\mathcal{O}(N^2)$\n",
        "\n",
        "<img src=\"https://drive.google.com/uc?id=1qY8e77Uy8zn-0q5Ca-czEBQ5DMqBOcOC\" width=\"450\" height=\"300\" />\n",
        "\n",
        "(NB : l'indice R² est un indicateur de la qualité de l'approximation du nuage de points par sa courbe de tendances : plus il est proche de 1, meilleure est l'approximation)\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rR_FOALIq_EF"
      },
      "source": [
        "# **4. L'algorithme de tri de Terminale : le tri fusion (méthode \"Diviser pour régner\")**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JNXkpqeG-BOk"
      },
      "source": [
        "## **4.a/ Principe algorithmique**\n",
        "Le **tri fusion** est l'occasion d'amener un algorithme récursif. \n",
        "Il comprend deux phases :    \n",
        "* tout d'abord on **divise** la liste en deux listes (de taille deux fois plus petites évidemment), jusqu'à ce que les listes obtenues soient de longueur 1, auquel cas, elle sont *a fortiori* triées.\n",
        "* puis, on **fusionne** les listes, c'est-à-dire qu'on les **inter-classe**, (on parle aussi d'**\"intercalation\"**) et de proche en proche, on remonte ainsi, de fusion en fusion, à la liste initiale triée.\n",
        "\n",
        "**exemple :**\n",
        "\n",
        "<img src=\"https://upload.wikimedia.org/wikipedia/commons/6/60/Mergesort_algorithm_diagram.png\" width=\"350\" height=\"360\" />\n",
        "(source image Wikipedia)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YuIN7wH2BlHM"
      },
      "source": [
        "## **4.b/ Fonctions récursives**\n",
        "\n",
        "**illustration ici :** http://lwh.free.fr/pages/algo/tri/tri_fusion.html"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7huT3vvOC--x"
      },
      "source": [
        "def fusion(L1,L2):\n",
        "    '''Cette fonction reçoit deux listes triées et \n",
        "    renvoie la liste obtenue en les fusionnant par inter-classement'''\n",
        "    #index\n",
        "    i1,i2 = 0,0\n",
        "    n1,n2 = len(L1),len(L2)\n",
        "    L=[]\n",
        "    while i1 < n1 and i2 < n2 : # Tant qu'on n'a pas vidé l'une des deux listes,\n",
        "                                # on ajoute à la liste fusionnée le plus petit \n",
        "                                # des deux premiers éléments de chaque liste\n",
        "                                # non encore entrés dans la fusion \n",
        "        if L1[i1] < L2[i2]: \n",
        "            L.append(L1[i1]) \n",
        "            i1 = i1 + 1\n",
        "        else:\n",
        "            L.append(L2[i2])\n",
        "            i2 = i2 + 1\n",
        "    # Quand l'une des deux listes à fusionner est finie, on complète la liste finale\n",
        "    # avec ce qu'il reste de l'autre\n",
        "    if i1 == n1:\n",
        "        L.extend(L2[i2:])\n",
        "    else:\n",
        "        L.extend(L1[i1:])\n",
        "    print(L)\n",
        "    return L\n",
        "     \n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BzTCUDE3IZ1_"
      },
      "source": [
        "**test**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "TbdySzu4H9bT",
        "outputId": "0318bde6-3550-4c37-96a0-1255ae235891"
      },
      "source": [
        "L1 = [1,3,4,7,8]\n",
        "L2 = [2,5,6,9,10,11,12]\n",
        "L = fusion(L1,L2)\n",
        "L"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]"
            ]
          },
          "metadata": {},
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "t5LTKOMJHyGk"
      },
      "source": [
        "def tri_fusion(L):\n",
        "    print(L)\n",
        "    if len(L) <= 1:\n",
        "        return L\n",
        "    # On coupe la liste en deux parts de même longueur (+ ou - 1)\n",
        "    milieu = len(L) // 2\n",
        "    gauche = L[:milieu] # sous-liste de gauche\n",
        "    droite = L[milieu:] # sous-liste de droite\n",
        "\n",
        "    gauche = tri_fusion(gauche) # appel récursif du tri fusion sur la sous-liste de gauche\n",
        "    droite = tri_fusion(droite) # appel récursif du tri fusion sur la sous-liste de droite\n",
        "\n",
        "    L = fusion(gauche, droite)\n",
        "    return L\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "D-bN7UGRJpew"
      },
      "source": [
        "**test**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zMCQWZokJLVO",
        "outputId": "6471b6d0-c6c3-4614-dc02-a0375177bace"
      },
      "source": [
        "L = liste_aleatoire(16)\n",
        "L"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[3, 16, 6, 14, 2, 4, 11, 9, 1, 10, 7, 15, 13, 5, 12, 8]"
            ]
          },
          "metadata": {},
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jmsOZMZ6JRzv",
        "outputId": "d6466c04-a284-49b2-eb6c-71468c35ac8f"
      },
      "source": [
        "tri_fusion(L)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[3, 16, 6, 14, 2, 4, 11, 9, 1, 10, 7, 15, 13, 5, 12, 8]\n",
            "[3, 16, 6, 14, 2, 4, 11, 9]\n",
            "[3, 16, 6, 14]\n",
            "[3, 16]\n",
            "[3]\n",
            "[16]\n",
            "[3, 16]\n",
            "[6, 14]\n",
            "[6]\n",
            "[14]\n",
            "[6, 14]\n",
            "[3, 6, 14, 16]\n",
            "[2, 4, 11, 9]\n",
            "[2, 4]\n",
            "[2]\n",
            "[4]\n",
            "[2, 4]\n",
            "[11, 9]\n",
            "[11]\n",
            "[9]\n",
            "[9, 11]\n",
            "[2, 4, 9, 11]\n",
            "[2, 3, 4, 6, 9, 11, 14, 16]\n",
            "[1, 10, 7, 15, 13, 5, 12, 8]\n",
            "[1, 10, 7, 15]\n",
            "[1, 10]\n",
            "[1]\n",
            "[10]\n",
            "[1, 10]\n",
            "[7, 15]\n",
            "[7]\n",
            "[15]\n",
            "[7, 15]\n",
            "[1, 7, 10, 15]\n",
            "[13, 5, 12, 8]\n",
            "[13, 5]\n",
            "[13]\n",
            "[5]\n",
            "[5, 13]\n",
            "[12, 8]\n",
            "[12]\n",
            "[8]\n",
            "[8, 12]\n",
            "[5, 8, 12, 13]\n",
            "[1, 5, 7, 8, 10, 12, 13, 15]\n",
            "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]"
            ]
          },
          "metadata": {},
          "execution_count": 15
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bmXg2xmWJ1us"
      },
      "source": [
        "**Visualisation dans PythonTutor**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ExL9r0VDJ5vs",
        "outputId": "c32a0145-9b08-4d44-b1eb-03a44f5c77e4"
      },
      "source": [
        "!pip install metakernel\n",
        "\n",
        "from metakernel import register_ipython_magics\n",
        "register_ipython_magics()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Collecting metakernel\n",
            "  Downloading metakernel-0.28.1-py2.py3-none-any.whl (217 kB)\n",
            "\u001b[?25l\r\u001b[K     |█▌                              | 10 kB 18.5 MB/s eta 0:00:01\r\u001b[K     |███                             | 20 kB 19.2 MB/s eta 0:00:01\r\u001b[K     |████▌                           | 30 kB 22.4 MB/s eta 0:00:01\r\u001b[K     |██████                          | 40 kB 25.1 MB/s eta 0:00:01\r\u001b[K     |███████▌                        | 51 kB 27.0 MB/s eta 0:00:01\r\u001b[K     |█████████                       | 61 kB 28.5 MB/s eta 0:00:01\r\u001b[K     |██████████▋                     | 71 kB 27.5 MB/s eta 0:00:01\r\u001b[K     |████████████                    | 81 kB 29.1 MB/s eta 0:00:01\r\u001b[K     |█████████████▋                  | 92 kB 27.9 MB/s eta 0:00:01\r\u001b[K     |███████████████                 | 102 kB 26.4 MB/s eta 0:00:01\r\u001b[K     |████████████████▋               | 112 kB 26.4 MB/s eta 0:00:01\r\u001b[K     |██████████████████              | 122 kB 26.4 MB/s eta 0:00:01\r\u001b[K     |███████████████████▋            | 133 kB 26.4 MB/s eta 0:00:01\r\u001b[K     |█████████████████████▏          | 143 kB 26.4 MB/s eta 0:00:01\r\u001b[K     |██████████████████████▋         | 153 kB 26.4 MB/s eta 0:00:01\r\u001b[K     |████████████████████████▏       | 163 kB 26.4 MB/s eta 0:00:01\r\u001b[K     |█████████████████████████▋      | 174 kB 26.4 MB/s eta 0:00:01\r\u001b[K     |███████████████████████████▏    | 184 kB 26.4 MB/s eta 0:00:01\r\u001b[K     |████████████████████████████▊   | 194 kB 26.4 MB/s eta 0:00:01\r\u001b[K     |██████████████████████████████▏ | 204 kB 26.4 MB/s eta 0:00:01\r\u001b[K     |███████████████████████████████▊| 215 kB 26.4 MB/s eta 0:00:01\r\u001b[K     |████████████████████████████████| 217 kB 26.4 MB/s \n",
            "\u001b[?25hRequirement already satisfied: ipykernel in /usr/local/lib/python3.7/dist-packages (from metakernel) (4.10.1)\n",
            "Requirement already satisfied: jupyter-core in /usr/local/lib/python3.7/dist-packages (from metakernel) (4.9.1)\n",
            "Requirement already satisfied: pexpect>=4.2 in /usr/local/lib/python3.7/dist-packages (from metakernel) (4.8.0)\n",
            "Requirement already satisfied: ptyprocess>=0.5 in /usr/local/lib/python3.7/dist-packages (from pexpect>=4.2->metakernel) (0.7.0)\n",
            "Requirement already satisfied: jupyter-client in /usr/local/lib/python3.7/dist-packages (from ipykernel->metakernel) (5.3.5)\n",
            "Requirement already satisfied: tornado>=4.0 in /usr/local/lib/python3.7/dist-packages (from ipykernel->metakernel) (5.1.1)\n",
            "Requirement already satisfied: traitlets>=4.1.0 in /usr/local/lib/python3.7/dist-packages (from ipykernel->metakernel) (5.1.1)\n",
            "Requirement already satisfied: ipython>=4.0.0 in /usr/local/lib/python3.7/dist-packages (from ipykernel->metakernel) (5.5.0)\n",
            "Requirement already satisfied: pygments in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->metakernel) (2.6.1)\n",
            "Requirement already satisfied: prompt-toolkit<2.0.0,>=1.0.4 in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->metakernel) (1.0.18)\n",
            "Requirement already satisfied: decorator in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->metakernel) (4.4.2)\n",
            "Requirement already satisfied: setuptools>=18.5 in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->metakernel) (57.4.0)\n",
            "Requirement already satisfied: pickleshare in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->metakernel) (0.7.5)\n",
            "Requirement already satisfied: simplegeneric>0.8 in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->metakernel) (0.8.1)\n",
            "Requirement already satisfied: wcwidth in /usr/local/lib/python3.7/dist-packages (from prompt-toolkit<2.0.0,>=1.0.4->ipython>=4.0.0->ipykernel->metakernel) (0.2.5)\n",
            "Requirement already satisfied: six>=1.9.0 in /usr/local/lib/python3.7/dist-packages (from prompt-toolkit<2.0.0,>=1.0.4->ipython>=4.0.0->ipykernel->metakernel) (1.15.0)\n",
            "Requirement already satisfied: python-dateutil>=2.1 in /usr/local/lib/python3.7/dist-packages (from jupyter-client->ipykernel->metakernel) (2.8.2)\n",
            "Requirement already satisfied: pyzmq>=13 in /usr/local/lib/python3.7/dist-packages (from jupyter-client->ipykernel->metakernel) (22.3.0)\n",
            "Installing collected packages: metakernel\n",
            "Successfully installed metakernel-0.28.1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 521
        },
        "id": "-Ilt3qXfJVws",
        "outputId": "d79f6268-99a4-4f14-e0ef-14c63acdd56d"
      },
      "source": [
        "%%tutor # lancement de PythonTutor\n",
        "\n",
        "def fusion(L1,L2):\n",
        "    '''Cette fonction reçoit deux listes triées et \n",
        "    renvoie la liste obtenue en les fusionnant par inter-classement'''\n",
        "    #index\n",
        "    i1,i2 = 0,0\n",
        "    n1,n2 = len(L1),len(L2)\n",
        "    L=[]\n",
        "    while i1 < n1 and i2 < n2 : # Tant qu'on n'a pas vidé l'une des deux listes,\n",
        "                                # on ajoute à la liste fusionnée le plus petit \n",
        "                                # des deux premiers éléments de chaque liste\n",
        "                                # non encore entrés dans la fusion \n",
        "        if L1[i1] < L2[i2]: \n",
        "            L.append(L1[i1]) \n",
        "            i1 = i1 + 1\n",
        "        else:\n",
        "            L.append(L2[i2])\n",
        "            i2 = i2 + 1\n",
        "    # Quand l'une des deux listes à fusionner est finie, on complète la liste finale\n",
        "    # avec ce qu'il reste de l'autre\n",
        "    if i1 == n1:\n",
        "        L.extend(L2[i2:])\n",
        "    else:\n",
        "        L.extend(L1[i1:])\n",
        "    return L\n",
        "     \n",
        "\n",
        " \n",
        "def tri_fusion(L):\n",
        "    if len(L) <= 1:\n",
        "        return L\n",
        "    # On coupe la liste en deux parts de même longueur (+ ou - 1)\n",
        "    milieu = len(L) // 2\n",
        "    gauche = L[:milieu] # sous-liste de gauche\n",
        "    droite = L[milieu:] # sous-liste de droite\n",
        "\n",
        "    gauche = tri_fusion(gauche) # appel récursif du tri fusion sur la sous-liste de gauche\n",
        "    droite = tri_fusion(droite) # appel récursif du tri fusion sur la sous-liste de droite\n",
        "\n",
        "    L = fusion(gauche, droite)\n",
        "    return L\n",
        "\n",
        "\n",
        "\n",
        "#L = [ 2, 6, 3, 4, 5, 1]\n",
        "L =[3,1,4,5,2]\n",
        "tri_fusion(L)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/html": [
              "\n",
              "        <iframe\n",
              "            width=\"100%\"\n",
              "            height=\"500\"\n",
              "            src=\"https://pythontutor.com/iframe-embed.html#code=%0Adef%20fusion%28L1%2CL2%29%3A%0A%20%20%20%20%27%27%27Cette%20fonction%20re%C3%A7oit%20deux%20listes%20tri%C3%A9es%20et%20%0A%20%20%20%20renvoie%20la%20liste%20obtenue%20en%20les%20fusionnant%20par%20inter-classement%27%27%27%0A%20%20%20%20%23index%0A%20%20%20%20i1%2Ci2%20%3D%200%2C0%0A%20%20%20%20n1%2Cn2%20%3D%20len%28L1%29%2Clen%28L2%29%0A%20%20%20%20L%3D%5B%5D%0A%20%20%20%20while%20i1%20%3C%20n1%20and%20i2%20%3C%20n2%20%3A%20%23%20Tant%20qu%27on%20n%27a%20pas%20vid%C3%A9%20l%27une%20des%20deux%20listes%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20on%20ajoute%20%C3%A0%20la%20liste%20fusionn%C3%A9e%20le%20plus%20petit%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20des%20deux%20premiers%20%C3%A9l%C3%A9ments%20de%20chaque%20liste%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20non%20encore%20entr%C3%A9s%20dans%20la%20fusion%20%0A%20%20%20%20%20%20%20%20if%20L1%5Bi1%5D%20%3C%20L2%5Bi2%5D%3A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20L.append%28L1%5Bi1%5D%29%20%0A%20%20%20%20%20%20%20%20%20%20%20%20i1%20%3D%20i1%20%2B%201%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20L.append%28L2%5Bi2%5D%29%0A%20%20%20%20%20%20%20%20%20%20%20%20i2%20%3D%20i2%20%2B%201%0A%20%20%20%20%23%20Quand%20l%27une%20des%20deux%20listes%20%C3%A0%20fusionner%20est%20finie%2C%20on%20compl%C3%A8te%20la%20liste%20finale%0A%20%20%20%20%23%20avec%20ce%20qu%27il%20reste%20de%20l%27autre%0A%20%20%20%20if%20i1%20%3D%3D%20n1%3A%0A%20%20%20%20%20%20%20%20L.extend%28L2%5Bi2%3A%5D%29%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20L.extend%28L1%5Bi1%3A%5D%29%0A%20%20%20%20return%20L%0A%20%20%20%20%20%0A%0A%20%0Adef%20tri_fusion%28L%29%3A%0A%20%20%20%20if%20len%28L%29%20%3C%3D%201%3A%0A%20%20%20%20%20%20%20%20return%20L%0A%20%20%20%20%23%20On%20coupe%20la%20liste%20en%20deux%20parts%20de%20m%C3%AAme%20longueur%20%28%2B%20ou%20-%201%29%0A%20%20%20%20milieu%20%3D%20len%28L%29%20//%202%0A%20%20%20%20gauche%20%3D%20L%5B%3Amilieu%5D%20%23%20sous-liste%20de%20gauche%0A%20%20%20%20droite%20%3D%20L%5Bmilieu%3A%5D%20%23%20sous-liste%20de%20droite%0A%0A%20%20%20%20gauche%20%3D%20tri_fusion%28gauche%29%20%23%20appel%20r%C3%A9cursif%20du%20tri%20fusion%20sur%20la%20sous-liste%20de%20gauche%0A%20%20%20%20droite%20%3D%20tri_fusion%28droite%29%20%23%20appel%20r%C3%A9cursif%20du%20tri%20fusion%20sur%20la%20sous-liste%20de%20droite%0A%0A%20%20%20%20L%20%3D%20fusion%28gauche%2C%20droite%29%0A%20%20%20%20return%20L%0A%0A%0A%0A%23L%20%3D%20%5B%202%2C%206%2C%203%2C%204%2C%205%2C%201%5D%0AL%20%3D%5B3%2C1%2C4%2C5%2C2%5D%0Atri_fusion%28L%29&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&py=3&rawInputLstJSON=%5B%5D&curInstr=0&codeDivWidth=350&codeDivHeight=400\"\n",
              "            frameborder=\"0\"\n",
              "            allowfullscreen\n",
              "        ></iframe>\n",
              "        "
            ],
            "text/plain": [
              "<IPython.lib.display.IFrame at 0x7f1f67d8b510>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "thoBqRrvM4dZ"
      },
      "source": [
        "def liste_aleatoire(N) :\n",
        "    ''' Cette fonction reçoit en entrée un entier N\n",
        "    et renvoie une liste L des entiers de 1 à N, dans un ordre aléatoire'''\n",
        "\n",
        "    import numpy.random as rd\n",
        "    U = rd.random(N)\n",
        "    #print(U)\n",
        "    L = [sum(U >= U[i]) for i in range(N)]\n",
        "    return L\n",
        "\n",
        "\n",
        "def fusion(L1,L2):\n",
        "    '''Cette fonction reçoit deux listes triées et \n",
        "    renvoie la liste obtenue en les fusionnant par inter-classement'''\n",
        "    #index\n",
        "    i1,i2 = 0,0\n",
        "    n1,n2 = len(L1),len(L2)\n",
        "    L=[]\n",
        "    while i1 < n1 and i2 < n2 : # Tant qu'on n'a pas vidé l'une des deux listes,\n",
        "                                # on ajoute à la liste fusionnée le plus petit \n",
        "                                # des deux premiers éléments de chaque liste\n",
        "                                # non encore entrés dans la fusion \n",
        "        if L1[i1] < L2[i2]: \n",
        "            L.append(L1[i1]) \n",
        "            i1 = i1 + 1\n",
        "        else:\n",
        "            L.append(L2[i2])\n",
        "            i2 = i2 + 1\n",
        "    # Quand l'une des deux listes à fusionner est finie, on complète la liste finale\n",
        "    # avec ce qu'il reste de l'autre\n",
        "    if i1 == n1:\n",
        "        L.extend(L2[i2:])\n",
        "    else:\n",
        "        L.extend(L1[i1:])\n",
        "    return L\n",
        "     \n",
        "\n",
        " \n",
        "def tri_fusion(L):\n",
        "    if len(L) <= 1:\n",
        "        return L\n",
        "    # On coupe la liste en deux parts de même longueur (+ ou - 1)\n",
        "    milieu = len(L) // 2\n",
        "    gauche = L[:milieu] # sous-liste de gauche\n",
        "    droite = L[milieu:] # sous-liste de droite\n",
        "\n",
        "    gauche = tri_fusion(gauche) # appel récursif du tri fusion sur la sous-liste de gauche\n",
        "    droite = tri_fusion(droite) # appel récursif du tri fusion sur la sous-liste de droite\n",
        "\n",
        "    L = fusion(gauche, droite)\n",
        "    return L\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3z1hZIV2KsB-"
      },
      "source": [
        "import time\n",
        "from math import floor\n",
        "liste_exp = range(1,13)\n",
        "liste_N = [2**n for n in liste_exp]\n",
        "liste_temps = []\n",
        "for N in liste_N :\n",
        "    L = liste_aleatoire(N)\n",
        "    t = time.time()\n",
        "    tri_fusion(L)\n",
        "    temps_exec = floor((time.time() - t)*100000)\n",
        "    liste_temps.append(temps_exec)\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 17
        },
        "id": "bcyHRTHcMtwu",
        "outputId": "295ae03b-6ca9-4298-f9ae-09781cf2a36c"
      },
      "source": [
        "import csv\n",
        "\n",
        "with open('SauvegardeTable3.csv', 'w', newline='') as csvfile:\n",
        "    writer = csv.writer(csvfile, delimiter=';')\n",
        "    writer.writerow(liste_N)\n",
        "    writer.writerow(liste_temps)\n",
        "\n",
        "from google.colab import files\n",
        "files.download(\"SauvegardeTable3.csv\")"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "application/javascript": [
              "\n",
              "    async function download(id, filename, size) {\n",
              "      if (!google.colab.kernel.accessAllowed) {\n",
              "        return;\n",
              "      }\n",
              "      const div = document.createElement('div');\n",
              "      const label = document.createElement('label');\n",
              "      label.textContent = `Downloading \"${filename}\": `;\n",
              "      div.appendChild(label);\n",
              "      const progress = document.createElement('progress');\n",
              "      progress.max = size;\n",
              "      div.appendChild(progress);\n",
              "      document.body.appendChild(div);\n",
              "\n",
              "      const buffers = [];\n",
              "      let downloaded = 0;\n",
              "\n",
              "      const channel = await google.colab.kernel.comms.open(id);\n",
              "      // Send a message to notify the kernel that we're ready.\n",
              "      channel.send({})\n",
              "\n",
              "      for await (const message of channel.messages) {\n",
              "        // Send a message to notify the kernel that we're ready.\n",
              "        channel.send({})\n",
              "        if (message.buffers) {\n",
              "          for (const buffer of message.buffers) {\n",
              "            buffers.push(buffer);\n",
              "            downloaded += buffer.byteLength;\n",
              "            progress.value = downloaded;\n",
              "          }\n",
              "        }\n",
              "      }\n",
              "      const blob = new Blob(buffers, {type: 'application/binary'});\n",
              "      const a = document.createElement('a');\n",
              "      a.href = window.URL.createObjectURL(blob);\n",
              "      a.download = filename;\n",
              "      div.appendChild(a);\n",
              "      a.click();\n",
              "      div.remove();\n",
              "    }\n",
              "  "
            ],
            "text/plain": [
              "<IPython.core.display.Javascript object>"
            ]
          },
          "metadata": {}
        },
        {
          "output_type": "display_data",
          "data": {
            "application/javascript": [
              "download(\"download_8e619ac4-3bab-4143-81a4-12b0e4b7ab81\", \"SauvegardeTable3.csv\", 80)"
            ],
            "text/plain": [
              "<IPython.core.display.Javascript object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Bwx-GyIvW9FW"
      },
      "source": [
        "## **4.c/ Complexité**\n",
        "La phase de division est d'ordre  $\\mathcal{O}(log_2 (N))$ : chaque étage a des listes deux fois plus petites que l'étage précédent, on cherche donc le nombre $p$ tel que $2^p$ soit immédiatement supérieur à N, c'est ce qu'on appelle le $log_2(N)$.\n",
        "\n",
        "Mais $log_2(N) = \\frac{ln(n)}{ln(2)}$, et donc, par la règle du produit d'un \"grand-O\" par un réel, la phase de division est en $\\mathcal{O}(ln (N))$.\n",
        "\n",
        "La phase de fusion est, de manière assez évidente, d'ordre $N$.\n",
        "\n",
        "Ainsi, l'algorithme de tri fusion complet a pour ordre de grandeur $\\mathcal{O}(N \\times ln (N))$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yUvIhSM8NFLI"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}