Dans la vie courante, on parle de tri quand on veut ranger les objets par paquets en fonction d'un ou plusieurs critères et de classement pour ranger les objets dans un certain ordre. En informatique, la distinction n'est pas faite et on utilise couramment le mot tri pour du classement.
Un tri par sélection s'effectue en plusieurs étapes. La première consiste à parcourir tous les éléments du tableau pour trouver la valeur maximale (ou minimale). La deuxième étape est de remplacer une valeur par une autre pour effectuer un tri croissant ou décroissant.
Pour parcourir un tableau de valeurs, on utilise une structure de boucle finie, donc une boucle for. La boucle while n'est pas adaptée à une liste connue de résultats mais à une série d'évènements qui se suivent. Un test est plutôt utilisé à l'intérieur de la boucle.
L'utilisation de fonctions sert à éviter les répétitions dans le code, c'est surtout une question de lisibilité et de réutilisabilité du code. Une fonction qu'on a écrite une fois, peut être réutilisée. Cela fait surtout gagner en efficacité dans le développement.
Pour le tri par sélection, comme pour le tri par insertion, le nombre de comparaison augmente en carré. On dit que sa complexité est quadratique.
On additionne à chaque étape le nombre de valeurs - 1. Ainsi pour 5 éléments, dans la mesure où on compare un élément du tableau au reste du tableau, il y a 4 comparaisons, puis, 3 à l'étape suivante, puis 2, puis 1, donc 4 + 3 + 2 + 1 = 10
Si la première valeur est plus petite que la deuxième, l'algorithme de tri par insertion ne fait pas de comparaison puisque les deux valeurs sont déjà rangées. Il n'y a comparaison que quand la première valeur est plus grande que la deuxième.
Comme on ne sait pas avant la comparaison où l'on va ranger la valeur stockée dans la variable, la boucle while est la plus adaptée que la boucle for.
8
Félicitations pour le score parfait !Encore un petit effort !
Retente ta chance, tu peux faire mieux.
Pour suivre tes progrès, crée ton compte Lumni, c’est gratuit !
Je crée mon compteJoue à ce quiz et gagne facilement jusqu'à 80 Lumniz en te connectant !
Il n’y a pas de Lumniz à gagner car tu as déjà vu ce contenu. Ne t’inquiète pas, il y a plein d’autres vidéos, jeux, quiz ou articles intéressants à explorer et toujours plus de Lumniz à remporter.
Les algorithmes de tri
En algorithmique, les fonctions de tri sont très importantes, elles font partie des fonctions de base d'un langage de programmation. On distingue plusieurs types de tri. Le tri par sélection et le tri par insertion sont les plus courants, mais il en existe de nombreux autres pour différents usages, comme le tri en tas, le tri par fusion ou encore le tri à bulles... Ces algorithmes ont des performances très différentes mais sont aussi plus ou moins complexes. Il s'agit donc toujours de trouver un compromis entre efficacité et complexité.