agreg/Tri_a_bulle_et_tri_cocktail.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#Exercice-d'algorithmique---Agrégation-Option-Informatique\" data-toc-modified-id=\"Exercice-d'algorithmique---Agrégation-Option-Informatique-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Exercice d'algorithmique - Agrégation Option Informatique</a></div><div class=\"lev2 toc-item\"><a href=\"#Préparation-à-l'agrégation---ENS-de-Rennes,-2016-17\" data-toc-modified-id=\"Préparation-à-l'agrégation---ENS-de-Rennes,-2016-17-11\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Préparation à l'agrégation - ENS de Rennes, 2016-17</a></div><div class=\"lev2 toc-item\"><a href=\"#À-propos-de-ce-document\" data-toc-modified-id=\"À-propos-de-ce-document-12\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>À propos de ce document</a></div><div class=\"lev2 toc-item\"><a href=\"#Le-problème-:-tri-à-bulles-et-tri-cocktail\" data-toc-modified-id=\"Le-problème-:-tri-à-bulles-et-tri-cocktail-13\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Le problème : tri à bulles et tri cocktail</a></div><div class=\"lev2 toc-item\"><a href=\"#Tri-à-bulles\" data-toc-modified-id=\"Tri-à-bulles-14\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Tri à bulles</a></div><div class=\"lev2 toc-item\"><a href=\"#Tests\" data-toc-modified-id=\"Tests-15\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Tests</a></div><div class=\"lev3 toc-item\"><a href=\"#Utilitaire-pour-des-tests\" data-toc-modified-id=\"Utilitaire-pour-des-tests-151\"><span class=\"toc-item-num\">1.5.1&nbsp;&nbsp;</span>Utilitaire pour des tests</a></div><div class=\"lev3 toc-item\"><a href=\"#Tests-du-tri-à-bulle\" data-toc-modified-id=\"Tests-du-tri-à-bulle-152\"><span class=\"toc-item-num\">1.5.2&nbsp;&nbsp;</span>Tests du tri à bulle</a></div><div class=\"lev2 toc-item\"><a href=\"#Tri-cocktail\" data-toc-modified-id=\"Tri-cocktail-16\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Tri cocktail</a></div><div class=\"lev2 toc-item\"><a href=\"#Tests\" data-toc-modified-id=\"Tests-17\"><span class=\"toc-item-num\">1.7&nbsp;&nbsp;</span>Tests</a></div><div class=\"lev2 toc-item\"><a href=\"#Comparaison\" data-toc-modified-id=\"Comparaison-18\"><span class=\"toc-item-num\">1.8&nbsp;&nbsp;</span>Comparaison</a></div><div class=\"lev3 toc-item\"><a href=\"#Première-comparaison-:-$n-=-100$\" data-toc-modified-id=\"Première-comparaison-:-$n-=-100$-181\"><span class=\"toc-item-num\">1.8.1&nbsp;&nbsp;</span>Première comparaison : <span class=\"MathJax_Preview\" style=\"color: inherit;\"></span><span class=\"MathJax MathJax_Processing\" id=\"MathJax-Element-3-Frame\" tabindex=\"0\"></span><script type=\"math/tex\" id=\"MathJax-Element-3\">n = 100</script></a></div><div class=\"lev3 toc-item\"><a href=\"#Autre-comparaison-:-$n-=-1000$\" data-toc-modified-id=\"Autre-comparaison-:-$n-=-1000$-182\"><span class=\"toc-item-num\">1.8.2&nbsp;&nbsp;</span>Autre comparaison : <span class=\"MathJax_Preview\" style=\"color: inherit;\"></span><span class=\"MathJax MathJax_Processing\" id=\"MathJax-Element-4-Frame\" tabindex=\"0\"></span><script type=\"math/tex\" id=\"MathJax-Element-4\">n = 1000</script></a></div><div class=\"lev2 toc-item\"><a href=\"#Conclusion\" data-toc-modified-id=\"Conclusion-19\"><span class=\"toc-item-num\">1.9&nbsp;&nbsp;</span>Conclusion</a></div><div class=\"lev3 toc-item\"><a href=\"#Question-/-exercice\" data-toc-modified-id=\"Question-/-exercice-191\"><span class=\"toc-item-num\">1.9.1&nbsp;&nbsp;</span>Question / exercice</a></div><div class=\"lev3 toc-item\"><a href=\"#Liens\" data-toc-modified-id=\"Liens-192\"><span class=\"toc-item-num\">1.9.2&nbsp;&nbsp;</span>Liens</a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercice d'algorithmique - Agrégation Option Informatique\n",
    "## Préparation à l'agrégation - ENS de Rennes, 2016-17\n",
    "- *Date* : 29 août 2017\n",
    "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## À propos de ce document\n",
    "- Ceci est une *proposition* de correction, pour un exercice (simple) d'algorithmique, pour la préparation à l'[agrégation de mathématiques, option informatique](http://Agreg.org/Textes/).\n",
    "- Ce document est un [notebook Jupyter](https://www.Jupyter.org/), et [est open-source sous Licence MIT sur GitHub](https://github.com/Naereen/notebooks/tree/master/agreg/), comme les autres solutions de textes de modélisation que [j](https://GitHub.com/Naereen)'ai écrite cette année.\n",
    "- L'implémentation sera faite en OCaml, version 4+ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The OCaml toplevel, version 4.04.2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : int = 0\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sys.command \"ocaml -version\";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "\n",
    "## Le problème : tri à bulles et tri cocktail\n",
    "\n",
    "On s'intéresse à deux algorithmes de tris.\n",
    "Pour plus de détails, voir les pages Wikipédia (ou le [Cormen] par exemple) :\n",
    "\n",
    "- [Tri à bulle](https://fr.wikipedia.org/wiki/Tri_%C3%A0_bulles),\n",
    "- [Tri cocktail](https://fr.wikipedia.org/wiki/Tri_cocktail).\n",
    "\n",
    "On veut implémenter les deux et les comparer, sur plein d'entrées."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "\n",
    "## Tri à bulles\n",
    "\n",
    "Commençons par le plus classique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val swap : 'a array -> int -> int -> unit = <fun>\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(** Un échange T[i] <-> T[j]. Utilise une valeur temporaire *)\n",
    "let swap tab i j =\n",
    "    let tmp = tab.(i) in\n",
    "    tab.(i) <- tab.(j);\n",
    "    tab.(j) <- tmp\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le tri à bulle a une complexité en $\\mathcal{O}(n^2)$ dans le pire des cas et en moyenne.\n",
    "Il a l'avantage d'être en place."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val tri_bulle : ('a -> 'a -> int) -> 'a array -> unit = <fun>\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let tri_bulle cmp tab =\n",
    "    let n = Array.length tab in\n",
    "    for i = n - 1 downto 1 do\n",
    "        for j = 0 to i - 1 do\n",
    "            if cmp tab.(j + 1) tab.(j) < 0 then\n",
    "                swap tab (j + 1) j;\n",
    "        done\n",
    "    done\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On utilise une fonction de comparaison générique. La fonction ``compare`` ([``Pervasives.compare``](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Pervasives.html#VALcompare)) fonctionne pour tous les types par défaut."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une version plus efficace existe aussi ([voir ces explications](https://fr.wikipedia.org/wiki/Tri_%C3%A0_bulles#Principe_et_pseudo-code))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val tri_bulle_opt : ('a -> 'a -> int) -> 'a array -> unit = <fun>\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let tri_bulle_opt cmp tab =\n",
    "    let n = Array.length tab in\n",
    "    let i = ref 0 in\n",
    "    let last_swap = ref (-1) in\n",
    "    while !i < n - 1 do\n",
    "        (* séquence d'échanges sur T[i..n]: *)\n",
    "        last_swap := n - 1;\n",
    "        for j = n-1 downto !i + 1 do\n",
    "            if cmp tab.(j) tab.(j-1) < 0 then begin\n",
    "                swap tab j (j-1);\n",
    "                last_swap := j - 1\n",
    "            end;\n",
    "            (* i avance \"plus vite\" :*)\n",
    "            i := !last_swap + 1;\n",
    "        done\n",
    "    done\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "\n",
    "## Tests\n",
    "\n",
    "On fait quelques tests."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Utilitaire pour des tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val maxint : int = 1000\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(** Taille max des éléments dans les tableaux aléatoires *)\n",
    "let maxint = int_of_float(1e3);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val rand_array : int -> int array = <fun>\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(** Créer un tableau aléatoire. En O(n). *)\n",
    "let rand_array length =\n",
    "    Array.init length (fun _ -> Random.int maxint)\n",
    ";; "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val isInjArray : 'a array -> bool = <fun>\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(** Vérifie que chaque élément du tableau n'y est qu'une seule fois (test l'égalité <> et pas !==).\n",
    "    Mal codé, en O(n^2). *)\n",
    "let isInjArray tab =\n",
    "    try begin\n",
    "        Array.iteri (fun i x -> \n",
    "            (Array.iteri (fun j y -> \n",
    "                assert( (x<>y) || (i=j) ) \n",
    "            ) tab) \n",
    "        ) tab;\n",
    "        true\n",
    "        end\n",
    "    with _ -> false\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val rand_array_inj : int -> int array = <fun>\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(** En moyenne, est en O(n^2) si [maxint] est bien plus grand que [n]. *)\n",
    "let rand_array_inj = function\n",
    "    | 0 -> [||]\n",
    "    | length ->\n",
    "        let tab = ref (rand_array length) in\n",
    "        while not(isInjArray (!tab)) do\n",
    "            tab := rand_array length;\n",
    "        done;\n",
    "        !tab\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette fonction prend un seul argument, la taille du tableau :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int array = [|344; 685; 182; 641; 439; 500; 104; 20; 921; 370; 217; 885|]\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rand_array_inj 12;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int array = [|949; 678; 615; 412; 401; 606; 428; 869; 289; 393; 14; 423|]\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rand_array_inj 12;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int array = [|723; 544; 96; 803; 500; 570; 649; 212; 755; 211; 357; 197|]\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rand_array_inj 12;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fonction de test :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val print : ('a, out_channel, unit) format -> 'a = <fun>\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val testtri :\n",
       "  ((int -> int -> int) -> int array -> 'a) ->\n",
       "  (int -> int -> int) -> int -> int -> unit -> unit = <fun>\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let print = Printf.printf;; \n",
    "\n",
    "let testtri mysort cmp length nbrun () =\n",
    "    print \"Test d'un tri, %i simulations avec des tableaux de longueur %i.\\n \" nbrun length;\n",
    "    for i = 0 to nbrun - 1 do\n",
    "        let t1 = rand_array length in\n",
    "        let t2 = Array.copy t1 in\n",
    "        mysort cmp t1;\n",
    "        Array.fast_sort cmp t2;\n",
    "        try assert( t1 = t2 ) with _ -> begin\n",
    "            print \"Avec des tableaux de taille %i, le test numéro %i a échoué.\" length i;\n",
    "            Format.printf \"@[t1=[|\"; Array.iter (fun i -> Format.printf \" %i;\" i) t1; Format.printf \"|]@]@ \";\n",
    "            Format.printf \"@[t2=[|\"; Array.iter (fun i -> Format.printf \" %i;\" i) t2; Format.printf \"|]@]@ \";\n",
    "        end;\n",
    "    done;\n",
    "    flush_all ();\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tests du tri à bulle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction de tri par défaut marche bien, évidemment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Test d'un tri, 10 simulations avec des tableaux de longueur 10.\n"
     ]
    }
   ],
   "source": [
    "testtri Array.sort compare 10 10 ();;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Test d'un tri, 10 simulations avec des tableaux de longueur 10.\n"
     ]
    }
   ],
   "source": [
    "testtri tri_bulle compare 10 10 ();;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Test d'un tri, 10 simulations avec des tableaux de longueur 10.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "testtri tri_bulle_opt compare 10 10 ();;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ça marche !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Test d'un tri, 1000 simulations avec des tableaux de longueur 100.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "testtri tri_bulle compare 100 1000 ();;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "\n",
    "## Tri cocktail"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il est très semblable au tri à bulle, sauf que le tableau sera parcouru alternativement dans les deux sens.\n",
    "\n",
    "Le tri cocktail a une complexité en $\\mathcal{O}(n^2)$ dans le pire des cas et en moyenne.\n",
    "Il a l'avantage d'être en place."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val tri_cocktail : ('a -> 'a -> int) -> 'a array -> unit = <fun>\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let tri_cocktail cmp tab =\n",
    "    let n = Array.length tab in\n",
    "    let echange = ref true in\n",
    "    while !echange do\n",
    "        echange := false;\n",
    "        (* Parcours croissant *)\n",
    "        for j = 0 to n - 2 do\n",
    "            if cmp tab.(j + 1) tab.(j) < 0 then begin\n",
    "                swap tab (j + 1) j;\n",
    "                echange := true\n",
    "            end;\n",
    "        done;\n",
    "        (* Parcours decroissant *)\n",
    "        for j = n - 2 downto 0 do\n",
    "            if cmp tab.(j + 1) tab.(j) < 0 then begin\n",
    "                swap tab (j + 1) j;\n",
    "                echange := true\n",
    "            end;\n",
    "        done;\n",
    "    done;\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il existe aussi une version plus efficace, qui diminue la taille des parcours au fur et à mesure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val tri_cocktail_opt : ('a -> 'a -> int) -> 'a array -> unit = <fun>\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let tri_cocktail_opt cmp tab =\n",
    "    let n = Array.length tab in\n",
    "    let echange = ref true in\n",
    "    let debut = ref 0 and fin = ref (n - 2) in\n",
    "    while !echange do\n",
    "        echange := false;\n",
    "        (* Parcours croissant *)\n",
    "        for j = !debut to !fin do\n",
    "            if cmp tab.(j + 1) tab.(j) < 0 then begin\n",
    "                swap tab (j + 1) j;\n",
    "                echange := true\n",
    "            end;\n",
    "        done;\n",
    "        fin := !fin - 1;\n",
    "        (* Parcours decroissant *)\n",
    "        for j = !fin downto !debut do\n",
    "            if cmp tab.(j + 1) tab.(j) < 0 then begin\n",
    "                swap tab (j + 1) j;\n",
    "                echange := true\n",
    "            end;\n",
    "        done;\n",
    "        debut := !debut + 1;\n",
    "    done;\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "\n",
    "## Tests\n",
    "Et d'autres tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Test d'un tri, 10 simulations avec des tableaux de longueur 10.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "testtri tri_cocktail compare 10 10 ();;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Test d'un tri, 10 simulations avec des tableaux de longueur 10.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "testtri tri_cocktail_opt compare 10 10 ();;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ça marche !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Test d'un tri, 1000 simulations avec des tableaux de longueur 100.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "testtri tri_cocktail compare 100 1000 ();;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "\n",
    "## Comparaison"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Avec [ce morceau de code](https://stackoverflow.com/a/9061574/) on peut facilement mesurer le temps d'exécution :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val time : (unit -> 'a) -> 'a = <fun>\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let time f =\n",
    "    let t = Sys.time() in\n",
    "    let res = f () in\n",
    "    Printf.printf \"    Temps en secondes: %fs\\n\" (Sys.time() -. t);\n",
    "    flush_all ();\n",
    "    res\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Première comparaison : $n = 100$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test d'un tri, 10000 simulations avec des tableaux de longueur 100.\n",
      "     Temps en secondes: 2.612000s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time (testtri Array.sort compare 100 10000);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test d'un tri, 10000 simulations avec des tableaux de longueur 100.\n",
      "     Temps en secondes: 2.976000s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time (testtri tri_bulle compare 100 10000);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test d'un tri, 10000 simulations avec des tableaux de longueur 100.\n",
      "     Temps en secondes: 3.144000s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time (testtri tri_bulle_opt compare 100 10000);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test d'un tri, 10000 simulations avec des tableaux de longueur 100.\n",
      "     Temps en secondes: 3.380000s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time (testtri tri_cocktail compare 100 10000);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test d'un tri, 10000 simulations avec des tableaux de longueur 100.\n",
      "     Temps en secondes: 2.724000s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time (testtri tri_cocktail_opt compare 100 10000);;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sur de petits tableaux, les versions \"optimisées\" ne sont pas plus forcément plus rapides (comme toujours).\n",
    "\n",
    "On vérifie quand même que sur des tableaux aléatoires, le tri cocktail optimisé semble le plus rapide des quatre implémentations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Autre comparaison : $n = 1000$\n",
    "\n",
    "Ca suffit à voir que les quatre algorithmes implémentés ici ne sont pas en temps sous quadratique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test d'un tri, 1000 simulations avec des tableaux de longueur 1000.\n",
      "     Temps en secondes: 3.072000s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time (testtri Array.sort compare 1000 1000);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test d'un tri, 1000 simulations avec des tableaux de longueur 1000.\n",
      "     Temps en secondes: 26.116000s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time (testtri tri_bulle compare 1000 1000);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test d'un tri, 1000 simulations avec des tableaux de longueur 1000.\n",
      "     Temps en secondes: 29.944000s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time (testtri tri_bulle_opt compare 1000 1000);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test d'un tri, 1000 simulations avec des tableaux de longueur 1000.\n",
      "     Temps en secondes: 27.296000s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time (testtri tri_cocktail compare 1000 1000);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test d'un tri, 1000 simulations avec des tableaux de longueur 1000.\n",
      "     Temps en secondes: 22.584000s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time (testtri tri_cocktail_opt compare 1000 1000);;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "\n",
    "## Conclusion\n",
    "\n",
    "Les deux algorithmes ne sont pas trop difficiles à implémenter, et fonctionnent de façon très similaire.\n",
    "\n",
    "### Question / exercice\n",
    "- Prouver la correction de chaque algorithme, à l'aide d'invariants bien choisis.\n",
    "- Prouver la complexité en temps.\n",
    "- Pourquoi ces noms, à bulle et cocktail ?\n",
    "\n",
    "### Liens\n",
    "Allez voir [d'autres notebooks](https://nbviewer.jupyter.org/github/Naereen/notebooks/tree/master/agreg/) !"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.04.2",
   "language": "OCaml",
   "name": "ocaml-jupyter"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.04.2"
  },
  "notify_time": "5",
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "11px",
    "width": "251px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": true,
   "toc_section_display": "block",
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}