{"cells":[{"metadata":{},"cell_type":"markdown","source":"

TP n°19 : les algorithmes de tri

"},{"metadata":{},"cell_type":"markdown","source":"
\nUn algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique. Ils peuvent également servir pour mettre des données sous forme canonique ou les rendre plus lisibles pour l'utilisateur.\n\nSource : [Wikipedia](https://fr.wikipedia.org/wiki/Algorithme_de_tri)\n
"},{"metadata":{},"cell_type":"markdown","source":"#
⚠ Pensez à sauvegarder régulièrement votre travail (cliquez sur le bouton qui clignote en bleu en haut à gauche) ⚠
"},{"metadata":{},"cell_type":"markdown","source":"# 1. Les algorithmes de tri"},{"metadata":{},"cell_type":"markdown","source":"## 1.1. Tri par insertion"},{"metadata":{},"cell_type":"markdown","source":"### 1.1.1. Définition"},{"metadata":{},"cell_type":"markdown","source":"
Le tri par insertion est celui qu'utilise un joueur de cartes : on parcourt la liste des cartes à trier du début à la fin. Au moment où l’on considère le ième élément, les i−1 premiers sont déjà triés, et on insère ce ième élément à la bonne place parmi les i−1. En pratique, on fait « remonter » ce ième élément en l’échangeant avec son prédécesseur tant qu’il est plus grand que lui.\n \nLe principe du tri par insertion est donc d'insérer à la nième itération le nième élément à la bonne place.
"},{"metadata":{},"cell_type":"markdown","source":"!!! info Regarder la vidéo suivante : \n[![Tri insertion](https://img.youtube.com/vi/bRPHvWgc6YM/0.jpg)](https://www.youtube.com/embed/bRPHvWgc6YM \"Tri Insertion\")\n \n et cette animation :\n![animation](https://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Insertion-sort-example-300px.gif/220px-Insertion-sort-example-300px.gif)\n!!!"},{"metadata":{},"cell_type":"markdown","source":"### 1.1.2. L'algorithme"},{"metadata":{"trusted":true},"cell_type":"markdown","source":"!!! abstract L'algorithme de tri par insertion (en pseudo-code) :\n\nFonction tri_par_insertion(tableau t)\n\n pour i de 1 à longueur(t) - 1\n \n # on mémorise t[i] dans une variable x\n x ← t[i] \n\n # on décale vers la droite les éléments de t[0] à t[i - 1]\n # qui sont plus grands que x (= t[i]) en partant de t[i - 1]\n j ← i \n tant que j > 0 et t[j - 1] > x\n t[j] ← t[j - 1]\n j ← j - 1\n\n # on place x dans le \"trou\" laissé par le décalage\n t[j] ← x\n \n fin pour\nFin Fonction\n!!!"},{"metadata":{},"cell_type":"markdown","source":"### 1.1.3. Application"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nCompléter le code de la fonction `tri_insertion` ci-dessous, en vous aidant de l'algorithme ci-dessus, qui :\n- prend en paramètre une liste de nombres entiers ;\n- retourne cette liste triée par ordre croissant en utilisant la méthode du tri par insertion décrite dans l'algorithme.\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def tri_insertion(tableau):\n \"\"\"\n Fonction Tri par insertion\n \n Entrée : une liste \"tableau\" d'entiers tableau\n Sortie : renvoie la liste \"tableau\" triée par ordre croissant\n \"\"\"\n # Votre code ici\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Vérification de votre code, vous pouvez faire des tests ici...\n","execution_count":null,"outputs":[]},{"metadata":{"editable":false,"deletable":false,"trusted":false},"cell_type":"code","source":"# Cette cellule NE DOIT PAS ETRE modifiée\n# Test final de la fonction de cette partie\n# Si la fonction est correcte alors aucun message d'erreur ne devrait apparaitre après l'exécution de cette cellule\n\ntableau = [5, 2, 0, 3, 7, 1, 4, 8, 6]\nassert tri_insertion(tableau) == [0, 1, 2, 3, 4, 5, 6, 7, 8]","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 1.2. Tri par sélection"},{"metadata":{},"cell_type":"markdown","source":"### 1.2.1. Définition"},{"metadata":{},"cell_type":"markdown","source":"
Le principe du tri par sélection est de chercher le plus petit élément d'une liste (tableau) pour le mettre en premier, puis de repartir du second élément et de chercher le plus petit élément de la liste restante pour le mettre en second, etc...
"},{"metadata":{},"cell_type":"markdown","source":"!!! info Regarder la vidéo suivante :\n\n[![Tri par sélection](https://img.youtube.com/vi/8u3Yq-5DTN8/0.jpg)](https://www.youtube.com/embed/8u3Yq-5DTN8 \"Tri par sélection\")\n\n et cette animation :\n![animation](https://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif) \n!!!"},{"metadata":{},"cell_type":"markdown","source":"### 1.2.2. L'algorithme"},{"metadata":{},"cell_type":"markdown","source":"!!! abstract L'algorithme de tri par sélection (en pseudo-code) :\n\nFonction tri_selection(tableau t)\n\n n ← longueur(t)\n pour i de 0 à n - 2\n minimum ← i\n pour j de i + 1 à n - 1\n si t[j] < t[minimum] alors minimum ← j\n fin pour\n \n si minimum ≠ i alors échanger t[i] et t[minimum]\n fin pour\nFin fonction\n!!!"},{"metadata":{},"cell_type":"markdown","source":"!!! info Remarque :\nUne variante consiste à procéder de façon symétrique, en plaçant d'abord le plus grand élément à la fin, puis le second plus grand élément en avant-dernière position, etc.\n!!!"},{"metadata":{},"cell_type":"markdown","source":"### 1.2.3. Application"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire \nCompléter le code de la fonction `tri_selection` ci-dessous, en vous aidant de l'algorithme ci-dessus, qui :\n- prend en paramètre une liste de nombres entiers\n- retourne cette liste triée par ordre croissant en utilisant la méthode du tri par sélection\n \nIl faut commencer par compléter le code des 2 premières fonctions à l'aide de leur docstring (documentation). Ces fonctions seront ensuite utilisées dans la fonction `tri_selection`.\n\nVous pouvez également vous aider de l'algorithme ci-dessus pour compléter le code de la fonction `tri_selection`.\n\n→ L'idéal serait de faire les deux méthodes !\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def inverser_elements(tableau, i, j):\n \"\"\"\n Fonction qui inverse la position des éléments d'indice i et j dans le tableau tab\n Cette fonction retourne le tableau.\n \"\"\"\n # Votre code ici \n\ndef recherche_plus_petit_element(tableau, i):\n \"\"\"\n Fonction qui prend en paramètre une liste et un indice i \n Elle retourne l'indice du plus petit élément du tableau à partir \n de l'indice i (c'est à dire qu'elle recherche cet élément dans tableau[i..])\n \"\"\"\n # Votre code ici\n\ndef tri_selection(tableau):\n \"\"\"\n Fonction Tri par selection\n \n Entrée : une liste d'entiers \"tableau\"\n Sortie: renvoie la liste \"tableau\" triée par ordre croissant\n \"\"\"\n # Votre code ici\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Vérification de votre code, vous pouvez faire des tests ici...\n","execution_count":null,"outputs":[]},{"metadata":{"editable":false,"deletable":false,"trusted":false},"cell_type":"code","source":"# Cette cellule NE DOIT PAS ETRE modifiée\n# Tests finaux des fonctions de cette partie\n# Si vos fonctions sont correctes alors aucun message d'erreur ne devrait apparaitre après l'exécution de cette cellule\n\ntableau = [5, 2, 0, 3, 7, 1, 4, 8, 6]\nassert inverser_elements(tableau, 0, 1) == [2, 5, 0, 3, 7, 1, 4, 8, 6]\nassert recherche_plus_petit_element(tableau, 0) == 2\nassert recherche_plus_petit_element(tableau, 3) == 5\nassert tri_selection(tableau) == [0, 1, 2, 3, 4, 5, 6, 7, 8]","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 1.3. Complexité"},{"metadata":{},"cell_type":"markdown","source":"
La complexité en temps (ou complexité temporelle) est le nombre d’opérations élémentaires maximum exécutées par l’algorithme pour toute entrée (donc dans le pire des cas). Le terme \"temps\" peut être trompeur. On ne parle évidemment pas ici de seconde ou de minute, une complexité n’a pas d’unité. C’est un nombre... de quelques choses. On parle de complexité en temps (et pas de complexité d’instructions) car on admet que chaque opération élémentaire s’exécute en temps unitaire, si bien que le temps d’exécution est effectivement donné par le nombre d’opérations élémentaires exécutées.\n\nRemarque : pour indiquer cette complexité, on utilise souvent des notations asymptotiques telles que O, Ω, Θ (dites notations de Landau) qui sont de simples écritures servant à simplifier la représentation de la complexité.\n
"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nRechercher sur le web les complexités temporelles (noms et notations asymptotiques) des algorithmes étudiés, en fonction de la taille `n` du tableau à trier :\n \n- tri par insertion ;\n- tri par sélection.\n!!!"},{"metadata":{},"cell_type":"raw","source":"tri par insertion :\n\n\ntri par sélection :"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nRécrire les fonctions `tri_insertion` et `tri_selection`, vues précédemment, en les renommant `tri_insertion_avec_compteur` et `tri_selection_avec_compteur`, en rajoutant dans le code de celles-ci un compteur (variable `compteur` par exemple) qui compte le nombre de comparaisons effectuées par la fonction et une instruction qui renvoie la valeur de ce compteur (la fonction se terminera donc par `return compteur`).\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Votre code ici ...\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Vous pouvez faire des tests ici...\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 1.4. Vitesse d'exécution"},{"metadata":{},"cell_type":"markdown","source":"Les cellules qui suivent permettrent de visualiser les temps d'exécution de ces deux algorithmes de tri.\nExécutez ces cellules puis étudiez leur code et cherchez à comprendre leur fonctionnement."},{"metadata":{"trusted":false},"cell_type":"code","source":"# ATTENTION : ces instructions prennent un peu de temps, soyez patient\n\nimport time\nimport random\nimport matplotlib.pyplot as plt\n\ndef generer_temps_calcul(debut, fin, pas, fontion_de_tri):\n chronos = []\n for n in range(debut, fin, pas ):\n tableau = [random.randint(1, 1000000) for i in range(n)]\n debut = time.perf_counter()\n fontion_de_tri(tableau)\n temps = time.perf_counter() - debut\n chronos.append(temps)\n return chronos\n\ndef afficher_graphique_temps_tri(debut, fin, pas, fontion_de_tri):\n abscisses = list(range(debut, fin, pas))\n chronos = generer_temps_calcul(debut, fin, pas, fontion_de_tri)\n plt.plot(abscisses, chronos, 'r.')\n plt.xticks(abscisses[::2], [str(x) for x in abscisses[::2]], rotation = 'vertical')\n plt.title('temps d\\'exécution de la recherche d\\'occurence (parcours séquentiel)')\n plt.xlabel('taille du tableau')\n plt.ylabel('temps d\\'exécution en secondes')\n plt.show()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"raw","source":"# Explications du fonctionnement des fonctions :\n\n\n"},{"metadata":{"trusted":false},"cell_type":"code","source":"# ATTENTION : cette instruction prend entre 20 et 60 secondes, soyez patient\n\nafficher_graphique_temps_tri(0, 10000, 500, tri_selection)","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# ATTENTION : ces instructions prennent un peu de temps, soyez patient\n\ndef afficher_graphique_TOUS_tris(debut, fin, pas):\n abscisses = list(range(debut, fin, pas))\n dico = {}\n for fonction_de_tri in [tri_selection, tri_insertion]: \n chronos = generer_temps_calcul(debut, fin, pas, fonction_de_tri)\n dico[fonction_de_tri.__name__] = chronos\n plt.plot(abscisses, dico[fonction_de_tri.__name__] , alpha = 0.8, label = fonction_de_tri.__name__, marker = 'o', lw = 3)\n plt.xticks(abscisses[::2], [str(x) for x in abscisses[::2]], rotation = 'vertical')\n plt.title('temps d\\'exécution de la recherche d\\'occurence (parcours séquentiel)')\n plt.xlabel('taille du tableau')\n plt.ylabel('temps d\\'exécution en secondes')\n plt.legend(loc = 'upper left')\n plt.show()","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# ATTENTION : cette instruction prend entre 1 et 2 minutes, soyez patient\n\nafficher_graphique_TOUS_tris (0, 10000, 500)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"!!! question Question\nQuelle conclusion peut-on en tirer ?\n!!!"},{"metadata":{},"cell_type":"raw","source":"# Votre réponse ici ...\n"},{"metadata":{"trusted":false},"cell_type":"markdown","source":"# 3. La méthode `sort` et la fonction `sorted()` de Python"},{"metadata":{},"cell_type":"markdown","source":"
On a déjà vu que Python possède des outils pour trier des listes :\n
\n \n
"},{"metadata":{},"cell_type":"markdown","source":"Exemples d’utilisation :"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Exécuter la cellule pour vérifier que la liste L a bien été triée\nL = [5, 3, 1, 9, 8, 2]\nL.sort()\nprint(L)","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Exécuter la cellule pour vérifier que sorted(L) est une liste triée\nL = [5, 3, 1, 9, 8, 2]\nsorted(L)","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Exécuter cette cellule pour vérifier que la liste L est la liste d'origine\nL","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"markdown","source":"!!! info Remarque :\nBien noter que `sort` est une méthode. Une méthode est une fonction attachée à un objet, voilà pourquoi, on doit mettre un point entre l'objet et le nom de la méthode, comme par exemple : `L.append(x)` ou, pour les dictionnaires, `d.items()`.\n!!!"},{"metadata":{},"cell_type":"markdown","source":"On peut avoir la docstring (documentation) de la méthode `sort` avec `help` :"},{"metadata":{"trusted":false},"cell_type":"code","source":"help(L.sort) # exécuter cette cellule pour avoir la docstring de la méthode \"sort\"","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"On constate qu'il s'agit bien d'un tri en place (The sort is in-place) et que par défaut, l'argument reverse est à False. On peut lire aussi lors dans la dernière phrase explicative que l'argument reverse permet de trier par ordre croissant ou décroissant.\n\nTester les instructions suivantes :"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Exécuter la cellule pour vérifier que la liste L a bien été triée par ordre décroissant\nL = [5, 3, 1 , 9, 8, 2]\nL.sort(reverse = True)\nprint(L)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"On peut aussi obtenir la docstring (documentation) de la fonction `sorted` avec `help` :"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Exécuter cette cellule pour avoir la docstring de la fonction \"sorted()\"\nhelp(sorted)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"On peut lire que cette fonction renvoie une nouvelle liste (donc la liste d'origine n'est pas modifiée : ce n'est pas un tri en place) et on remarque la présence de l'argument `reverse`.\n\nTester les instructions suivantes :"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Exécuter la cellule pour vérifier que \"sorted(L)\"\" est une liste triée\nL = [5, 3, 1, 9, 8, 2]\nsorted(L, reverse = True)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# 4. Pour aller plus loin"},{"metadata":{},"cell_type":"markdown","source":"!!! info Regarder la vidéo suivante :\n\n[![Tri par sélection](https://img.youtube.com/vi/x4ODr5jU0i0/0.jpg)](https://www.youtube.com/watch?v=x4ODr5jU0i0 \"Terminaison et Invariant de boucle\")\n!!!"},{"metadata":{"trusted":false},"cell_type":"markdown","source":"!!! info \nIl existe d'autres algorithmes de tri plus efficaces que les tris par sélection et par insertion et tout aussi efficaces que ceux qu'utilisent la fonction `sorted()` (ou la méthode `sort`). Voir le site suivant où on trouve aussi des animations pour comprendre les différents tris : site interstices sur les algorithmes de tri.\n!!!"}],"metadata":{"kernelspec":{"name":"python3","display_name":"Python 3","language":"python"},"celltoolbar":"Éditer les Méta-Données"},"nbformat":4,"nbformat_minor":2}