[Musique] dans cette capsule vidéo consacré un système de tri nous allons étudier cette fois ci en détail le tri par sélection second opus sur les tripes pour notre programme de première le tri par sélection sera l'occasion de réutiliser les notions vues précédemment lors de l'étude du tri par insertion nous reprendrons donc la même structure pour étudier ce tri entre l'algorithme le code en python et bien sûr l'étude de sa complexité allez en route pour la découverte cette vidéo propose quelques exemples de code python n'hésitez pas à mettre la vidéo sur pause quand cela vous est nécessaire puis tapez dans votre idée au pit ont préféré les différents codes afin de bien les assimiler c'est en effet en codant que l'on apprend à koné voyons tout d'abord les grands principes du tri par sélection on parle de tri lorsque l'on veut classer des données de type construit avec une relation d'ordre défini par exemple ranger dénombre dans l'ordre croissant bien sûr vous trouverez une fonction adaptée à cet exemple en python et dans tous les langages de haut niveau capables de réaliser cela directement avec des listes mais il est indispensable de connaître les principales familles d'algorithmes pouvant y mener quel est l'intérêt vous aurez toujours besoin de ranger autre chose que des nombres avec une relation d'ordre inconnu dans le langage utilisé le principe du tri par sélection est assez simple on parcourt la liste en cherchant le plus petit élément du tableau restant à trier et on le positionne en première place à l'endroit où on se trouve première étape on cherche le plus petit élément de la liste en général on les change avec celui qui est au début le premier élément est maintenant donc le plus petit est donc bien placé on cherche ensuite le plus petit élément de la liste en partant du deuxième élément est en les changes avec celui qui est placé à la deuxième place les deux premiers éléments sont donc les plus petits et sont donc rangés dans l'ordre on poursuit ainsi jusqu'à l'avant-dernier éléments de la liste pour réaliser la recherche du minimum nous utiliserons une fonction déjà développés permettant de rechercher 'l'indice du minimum dans une liste donnée à partir d'un rang déterminer on bouclera ainsi jusqu'à l'avant-dernière données de notre liste initiale on parcourt donc toute la liste sauf le dernier élément et pour chaque position la partie des indices inférieurs et déjà trié on recherche juste le minimum de la partie de la liste d' indice supérieur c'est-à-dire la partie de droite de notre liste pour comprendre comment fonctionne l'algorithme du tri par sélection nous reprenons un exemple avec une liste de six éléments nous allons donc sur le premier élément rechercher le minimum pour rechercher le minimum nous allons donc parcourir à partir de notre premier élément la liste donc le premier élément et 14 correspond à notre premier minimum et puis nous avançons dans notre liste nous trouvons finalement que 10 est à nouveau un nouveau minimum nous continuons d'examiner notre liste nous trouvons 4 qui est inférieur à 10 donc qui devient notre nouveau minimum donc la recherche du minimum va continuer comme cela en parcourant l'ensemble des valeurs de notre liste jusqu'à la fin donc en passant le 28 le 21 et enfin directement le 25 une fois arrivé à cela notre premier minimum correspondant à l'ensemble de la liste et 4 nous allons donc prendre 4 et le positionner en premier sur notre liste nous incrémente ont donc d'un cran notre indice de boucles général et nous arrivons à l'ain 10,1 nous allons rechercher le minimum dans la sous- liste de droite hélas ou liste de droite nous prenons 10 qui est le premier élément qui correspond finalement au minimum par défaut et nous avançons dans notre liste 14 puis 28 nous avons toujours dit ce qui est le minimum de l'ensemble des valeurs examiné 21 qui correspond toujours à une valeur supérieure à 10 donc qu'il n'ait pas choisi comme minimum et 25 sur l'ensemble de la partie de droite de notre liste nous avons bien trouvé notre minimum 10 il est bien positionné et nous continuons ainsi nous passons à lundi ce numéro 2 14 14 devient notre premier minimum et nous parcourons jusqu'à la fin nous avons bien 14 qui est le minimum nous avons donc bien positionné le minimum nous continuons à lundi ce numéro 3 cette fois-ci 28 qui est pris par défaut comme étant le minimum et nous allons donc examiner toute la partie de droite de notre lice pour voir si nous avons quelque chose qui est inférieur à 28 nous passons donc dans la recherche du minimum à 21,21 et notre nouveau minimum puisqu'il est inférieur à 28 nous continuerons jusqu'à la fin quand même pour vérifier 25 est supérieur à 21 notre minimum et 21 nous allons donc permuter 28 et 21 est positionné donc le nouveau minimum à lundi ce numéro 3 même chose lorsque nous arrivons à lundi ce numéro 4 de notre boucle général nous prenons la première valeur par défaut donc le 28 le 28 et considéré comme le minimum nous avançons dans la liste qui reste à découvrir c'est à dire juste le dernier élément 25-25 est plus petit que 28 nous allons donc permuter ces deux valeurs et nous nous arrêtons dans la boucle général du fort à cet élément 1 puisque de toute façon il ça sert à rien d'examiner le dernier 28 sera forcément le minimum d'une soulist d'un seul élément et nous avons donc trier ici par sélection nous avons sélectionné le minimum dans le reste de notre liste à chaque étape nous avons donc trouvé notre minimum est positionné l'ensemble des valeurs la lys et donc trier le principe du tri par sélection correspond donc à la recherche d'un minimum dans la sous- listes restantes maintenant que nous avons vu les grands principes du tri par sélection nous allons pouvoir passer en détail à son algorithme l'algorithme de tri par sélection en fait se décompose en deux parties tout d'abord la fonction mini qui va rechercher avec comme paramètre liste et index de début le plus petit élément d'une liste donnée à partir donc de l'indicent nommé début nous initialise on en fait l'index min à début puis ensuite nous allons boucler pour y allant de début à la longueur de notre liste donc aux derniers éléments si notre liste d'index mini est supérieur à notre liste d'index i à ce moment là nous avons trouvé en fait un nouveau l index min et il reçoit donc y est nous allons boucler sur l'ensemble de notre liste jusqu'à la fin une fois que nous avons eu nous sommes sortis de notre boucle nous pouvons retourner notre index min cette fois ci la fonction mini sera appelé dans le programme principal et notre programme principal sera extrêmement simple nous allons réaliser en fait une boucle pour y allant de zéro à la longueur de notre liste - nous n'avons pas besoin d'aller aux derniers éléments puisqu'il sera comparée avec l'avant-dernier et donc la permutation pourra avoir lieu déjà avec l'avant dernière éléments l'index du mini reçoit en réalité le résultat de notre fonction mini qu'elle nous avons passé le paramètre liste est le paramètre et à quel endroit nous sommes déjà dans notre liste tout ce que nous avons déjà trié est à gauche en fait de vie ce qui reste à trier est à droite une fois que nous avons fait ça nous échangeons liste de i et liste d'index du mini nous pourrions ici vérifier en fait qu'il est nécessaire d'échanger mais en fait cela va plus vite d'échanger de manière directe plutôt que de faire un test de structures conditionnelle puis ensuite d'échanger si nécessaire maintenant que nous connaissons les grands principes de notre algorithme nous allons pouvoir passer à sa programmation avec le langage python en programmation avec python la première chose à faire est de programmer en fait la fonction mini qui aura ces deux paramètres liste et début donc à la ligne 55 nous effectuons un déf mini de liste le début puis tout de suite nous initialise on lundi aux premiers éléments de notre liste on considère finalement que le plus petit est le premier élément ensuite eh bien nous allons examiner tous les éléments à partir du suivant après des débuts puisque le premier a été considéré comme étant plus petit et dans cette boucle fort en fait en partant de début + 1 jusqu'à la fin de notre liste nous allons comparer si notre index de notre plus petit est supérieur à la valeur examiné liste de y si c'est le cas et bien nous avons trouvé en fait un nouveau minimum notre index min en fête est supérieure à sept éléments donc en fait il est plus le new l'ancien minimum nous avons notre nouveau minimum et doux mémorisons son abbé son index à la ligne 65 en réalisant avec ce mini est égale à une fois que nous avons bouclé sur tous les éléments de la liste nous pouvons retourner cet élément au programme principal dans le programme principal donc nous utilisons une petite liste d'exemples à landing 70 et nous allons dès la ligne 72 bouclée sur l'ensemble de nos indices sauf le dernier puisque nous allons l'examiner en avant dernier cas donc à la ligne 74 nous recherchons le minier dans la seconde partie de notre liste la partie en fait inférieur à ea a déjà été triés à ce niveau là et nous allons ensuite permuté liste de vie et liste d'index du mini il y a donc en fait ici une boucle fort de la fonction mini un briquet dans la boucle forts du programme principal cela aura une incidence particulière dans l'étude de la complexité la terminaison under trolls gorrite est en simple à prouver puisque nous avons des boucles bornes efforts nous allons passer à l'étude de la complexité pour l'étude de la complexité nous allons fonctionner comme précédemment calculant en fait grossièrement le nombre d'étapes nécessaires pour résoudre notre algorithme donc nous écrivons ici notre algorithme est en phase nous allons évaluer le nombre d'étapes dans le pire des cas nous avons donc deux parties à évaluer la première partie correspondant à la fonction min et la seconde partie à notre programme principal dans la fonction minier l'initialisation d'index min à début nous conte pour une étape et ensuite nous avons une boucle fort pour y allant de début à la longueur de notre liste donc dans le pire des cas entre aisne - début étape-ci début est égal à zéro le pire des cas sera égal à n ensuite nous avons bien sûr notre structure conditionnelle avec notre cyliste index mini supérieur à liste de y nous avons une étape à chaque boucle fort puis en fait nous avons l'affectation d'un decs mini a eu une étape au pire des cas à chaque boucle fort nous ne rentrons pas de manière systématique en fait dans la structure conditionnelle mais si la liste et rangés par ordre décroissant et bien c'est le cas et enfin nous retournons index mini nous avons donc ici une étape dans le programme principal nous avons une boucle fort très standard avec haine - une étape puisque nous n'examinons pas le dernier élément puis dans cette boucle fort nous avons l'appel index mini qui reçoit donc il ya quand même une affectation au retour en fait de notre fonction et ensuite il y a les changes les changes en fait correspond à deux ou trois étapes suivant le langage de programmation avec python nous pouvons faire un échange en deux étapes la plupart des langages nécessite trois étapes donc dans la dernière colonne nous repérons en fait manière plus mathématique dans le pire des cas en fait combien il faut d'étape nous arrivons un total ici de 3 n o car est plus à haisnes -4 alors c'est assez approximatif avec le nombre d'étapes pour les changes est ici nous nous positionnons dans le pire des cas ce qui compte c'est d'avoir un ordre de grandeur et notre ordre de grandeur en fait est que notre rotation habitués l'eau la notation de lan do au de haine au carré en fait nous sommes donc dans le pire des cas en complexité quadratique notre évaluation de la complexité en fonction des algorithmes de tri nous conduit comme précédemment à voir que cette complexité peut passer dans les pires des cas en fait un ordre quadra tric ô de haine au carré à une complexité en fait plus acceptable o n look de haine et nous avons les écarts que nous avions repéré précédemment par pour le tri par insertion en fait qui n'est absolument pas notable pour un nombre de valeurs très faible une centaine par exemple ce que nous avons à peu près en fait toujours 6 millisecondes et qu'il devient assez considérable lorsque nous passons en fait à 10000 20000 ou quarante mille éléments dans une liste qui est quand même relativement courant et cette fois ci nous avons des écarts qui sont considérables puisque nous passons en fait pour un tri par sélection autour d'une trentaine de secondes contre 0,5 secondes pour un tri que nous verrons en terminale qui correspond au tri fusion qui lui à une complexité en n lob de haine c'est à vous vous venez de découvrir une méthode de tri le tri par sélection il en existe bien d'autres dont le tri par fusion qui sera étudiée en terminale il est essentiel que vous soyez au point sur la compréhension d'un algorithme de l'imbrication des deux boucles et que vous ayez assimiler la façon de déterminer à la main sans rigueur mathématique la complexité d'un tel algorithmes vous pouvez maintenant reprendre les exemples présentés dans cette capsule pour les adapter à vos projets en particulier je vous encourage à coder l'algorithme du tri par sélection à le tester avec des listes prises au hasard par exemple ajouter des chronomètres avec la bibliothèque times de python à votre algorithmes pour mesurer le temps mis pour trier une liste en variant les exemples liste de dix mille éléments déjà trié listes présentes par ordre décroissant liste aléatoire et comparer les temps mis par ses algorithmes dans ces trois cas vous pourriez avoir des surprises allez bon courage [Musique] [Musique]