{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithmes de tri (2) : tri par sélection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Principe\n",
    "- le travail sur le fait essentiellement sur les **indices**.\n",
    "- on part de l'indice du premier élément, on considère que cet élément est l'élément minimum.\n",
    "- on parcourt les éléments suivants, et si on repère un élémént plus petit que notre mininum on garde en mémoire l'indice de ce nouvel élément minimum.\n",
    "- une fois le parcours fini, on échange l'élément de travail avec l'élément minimum qui a été trouvé.\n",
    "- on avance d'un élément, et on recommence, jusqu'à l'avant-dernier.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Animation\n",
    "Considérons la liste `[5, 4, 2, 1]`  \n",
    "Voici le fonctionnement de l'algorithme :  \n",
    "![](data/selection.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Codage de l'algorithme\n",
    "\n",
    "Complétez l'algorithme ci-dessous"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tri(l) :\n",
    "    for k in range(0, len(l)-1):\n",
    "        indice_du_minimum = k\n",
    "        for i in range(k+1,len(l)) :\n",
    "            if l[i] < l[indice_du_minimum]:\n",
    "                indice_du_minimum = i\n",
    "        l[k], l[indice_du_minimum] = l[indice_du_minimum], l[k]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Vérification :*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 4, 5, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "a = [7, 5, 2, 8, 1, 4]\n",
    "tri(a)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Complexité de l'algorithme\n",
    "\n",
    "Pour pouvoir utiliser la fonction `%timeit`, nous allons modifier légèrement notre algorithme de tri : comme la fonction `%timeit` effectue un grand nombre d'appel à la fonction `tri()`, la liste serait triée dès le premier appel et les autres appels essaieraient donc de tri une liste *déjà triée*. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tri(L) :\n",
    "    l = list(L) # pour ne pas modifier la liste passée en argument.\n",
    "    for k in range(0, len(l)-1):\n",
    "        indice_du_minimum = k\n",
    "        for i in range(k+1,len(l)) :\n",
    "            if l[i] < l[indice_du_minimum]:\n",
    "                indice_du_minimum = i\n",
    "        l[k], l[indice_du_minimum] = l[indice_du_minimum], l[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [k for k in range(100,0,-1)] #on se place dans le pire des cas : une liste triée dans l'ordre décroissant"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = [k for k in range(200,0,-1)] #on se place dans le pire des cas : une liste triée dans l'ordre décroissant"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "632 µs ± 14.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit tri(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.35 ms ± 35.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit tri(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En comparant les temps de tri des listes `a` et `b`, que pouvez-vous supposer sur la complexité du tri par sélection ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une liste à trier 2 fois plus longue prend 4 fois plus de temps : l'algorithme semble de complexité **quadratique**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calcul du nombre d'opérations\n",
    "Dénombrons le nombre d'opérations, pour une liste de taille $n$.\n",
    "- boucle for : elle s'exécute $n-1$ fois.\n",
    "- deuxième boucle for imbriquée : elle exécute d'abord 1 opération, puis 2, puis 3... jusqu'à $n-1$. Or \n",
    "$$1+2+3+\\dots+n-1=\\dfrac{n \\times (n-1)}{2}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vérification expérimentale\n",
    "\n",
    "Insérez un compteur `c` dans votre algorithme pour vérifier le calcul précédent. On pourra renvoyer cette valeur en fin d'algorithme par un `return c`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Preuve de la terminaison de l'algorithme\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Est-on sûr que notre algorithme va s'arrêter ?  \n",
    "À l'observation du programme, constitué de deux boucles `for` imbriquées, il n'y a pas d'ambiguïté : on ne peut pas rentrer dans une boucle infinie. Le programme s'arrête forcément au bout de d'un nombre fixe d'opérations. \n",
    "D'après nos calculs sur la complexité, ce nombre de tours de boucles est égal à $$\\dfrac{n \\times (n-1)}{2}$$ \n",
    "\n",
    "Ceci prouve que l'algorithme se terminera.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Preuve de la correction de l'algorithme\n",
    "Les preuves de correction sont des preuves théoriques. La preuve ici s'appuie sur le concept mathématique de **récurrence**. \n",
    "Principe du raisonnement par récurrence : \n",
    "une propriété $P(n)$ est vraie si :\n",
    "- $P(0)$ (par exemple) est vraie\n",
    "- Pour tout entier naturel $n$, si $P(n)$ est vraie alors $P(n+1)$ est vraie.\n",
    "\n",
    "Ici, la propriété serait : « Quand $k$ varie entre 0 et `longueur(liste) -1`, la sous-liste de longueur $k$ est triée dans l'ordre croissant.» On appelle cette propriété un **invariant de boucle** (sous-entendu : elle est vraie pour chaque boucle)\n",
    "\n",
    "- quand $k$ vaut 0, on place le minimum de la liste en l[0], la sous-liste l[0] est donc triée.\n",
    "-  si la sous-liste de $k$ éléments est triée, l'algorithme rajoute en dernière position de la liste le minimum de la sous-liste restante, dont tous les éléments sont supérieurs au maximum de la sous-liste de $k$ éléments. La sous-liste de $k+1$ éléments est donc aussi triée.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}