TD8_comparaison_tris.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TD Comparateur de tris"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous avons étudié la semaine dernière deux algorithmes de tris : \n",
    "- le tri par sélection\n",
    "- le tri par insertion\n",
    "\n",
    "L'objectif du TD de cette semaine est d'appliquer ces 2 algorithmes sur des exemples de listes et de les comparer avec l'algorithme de tri natif utilisé par Python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Tri par sélection :\n",
    "En vous aidant de l'animation ci-dessous, rappeler le principe de l'algorithme du tri par sélection :\n",
    "![selection](select_sort.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.1. Principe du tri par sélection :__\n",
    "\n",
    "\n",
    "_écrire ici le principe_\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "__1.2. Récupérer dans le TD de la semaine dernière le script de ce tri et coller le code en dessous :__  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#code de la fonction tri par sélection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.3. Utiliser la liste aléatoire suivante pour tester le tri par sélection__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import *\n",
    "liste=[randint(1,100) for i in range(10)]\n",
    "print(liste)\n",
    "#compléter le code ci-dessous pour afficher la liste triée avec le tri par sélection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Tri par insertion :\n",
    "Observer de même l'animation suivante et rappeler le principe de l'alogorithme du tri par insertion :\n",
    "![insertion](tri_insert_anim.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__2.1. Principe du tri par insertion :__\n",
    "\n",
    "\n",
    "_écrire ici le principe_\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "__2.2. Récupérer dans le TD de la semaine dernière le script de ce tri et coller le code en dessous :__  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#code de la fonction du tri par insertion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__2.3. Utiliser la liste aléatoire suivante pour tester votre fonction et afficher la liste triée__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "liste=[randint(1,100) for i in range(10)]\n",
    "print(liste)\n",
    "#Compléter le code ci-dessous pour afficher la liste triée avec le tri par insertion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Observation des tris en activité\n",
    "Visualiser les 3 vidéos suivantes (__avec le son !__) pour une comparaison visuelle des 2 tris au programme de la NSI.\n",
    "\n",
    "La troisième vidéo est donnée à titre de curiosité pour vous montrer d'autres types de tris bien plus efficaces (mais aussi plus complexes à coder...)\n",
    "\n",
    "- video tri par insertion (1min57) :  https://youtu.be/8oJS1BMKE64?list=PLZh3kxyHrVp_AcOanN_jpuQbcMVdXbqei\n",
    "\n",
    "\n",
    "- video tri par selection (1min22) : https://youtu.be/92BfuxHn2XE?list=PLZh3kxyHrVp_AcOanN_jpuQbcMVdXbqei\n",
    "\n",
    "\n",
    "- vidéo de comparaison de 15 tris (5min49) :  https://www.youtube.com/watch?v=kPRA0W1kECg)\n",
    "\n",
    "Le nom du tri apparait en haut à gauche de la vidéo accompagné du nombre de comparaisons, du nombre d'accès aux données et du temps de calcul."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Comparaison des tris du programme\n",
    "Après cette petite récréation, passons aux choses sérieuses.\n",
    "\n",
    "Pour comparer les deux tris par insertion et sélection, il sera nécessaire d'utiliser la fonction `time()`inclue dans le package `time`.  \n",
    "Nous avons déjà utilisé cette fonction dans un TP précédent, revoir ci-nécessaire ce TP pour plus d'explications.\n",
    "\n",
    "On chargera donc en mémoire le script suivant et on complètera son code.  \n",
    "Ne pas oublier de relancer les deux fonctions du __1.__ et __2.__ \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "#début du décompte du temps\n",
    "t1 = time.time()\n",
    "#mettre le code ici\n",
    "t2 = time.time()\n",
    "#affichage du temps d'execution \n",
    "print(\"temps d'execution du tri : \", t2-t1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Travail demandé :__\n",
    "1. Construire une liste de 3000 entiers pris au hasard entre 1 et 10000.  \n",
    "Mesurer le temps d'exécution pour les 2 algorithmes et comparer.\n",
    "\n",
    "_Attention : pensez à reconstruire la liste entre les 2 tris !_\n",
    "\n",
    "2. Construire cette fois une liste d' entiers __consécutifs__ de 0 à 2999.  \n",
    "Mesurer le temps d'exécution pour les 2 algorithmes et comparer.\n",
    "\n",
    "3. Construire enfin une liste de 100000 entiers aléatoires entre 1 et 100000 et mesurer le temps d'execution avec le tri proposé par défaut de Python ( fonction `sort()` )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "jupytext": {
   "formats": "ipynb,md"
  },
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}