Accueil > Structures de données et algorithmes >

📚 Algorithmes de tri classiques

Survol et attentes

Comme avec les algorithmes de recherche, les algorithmes de tri sont des bons exercices pour développer la capacité à analyser une tâche de traitement de données et d’arriver à une solution valide.

Les algorithmes de tri sont généralement plus complexes que les algorithmes de recherche parce que le nombre de comparaisons à faire est plus grand et il faut déplacer des éléments pour produire l’ordre voulu.

Pour ces types de problèmes, au quotidien, vous utiliserez généralement des solutions optimisées comme la méthode sort des différents objets de votre langage de programmation.

Exemple et solution

Dans les exemples ci dessous, la partie triée de la collection se trouve à la gauche et la partie non triée se trouve à la droite.

Le tri par sélection trouve l’index du plus petit élément dans la partie non triée de la collection et échange l’élément à cette position avec le premier élément de la partie non triée. En répétant cette action, la partie triée grandie à mesure que la partie non triée diminue jusqu’à ce qu’on atteigne la fin de la collection. Voici le portrait entrée/traitement/sortie (ETS) pour l’algorithme :

Points clés sur le tri par sélection :

• La “sélection” fait référence à l’idée que cette algorithme sélectionne la valeur minimale parmis toutes les valeurs non triées pour ensuite l’ajouter à la fin de la partie triée.
• Il faut toujours comparer toutes les valeurs de la collection jusqu’à l’avant-dernière position même si la collection est déjà triée.

Le tri par insertion fonctionne différemment. Il compare la prochaine valeur non-triée avec les valeurs déjà triées, afin d’insérer cette valeur au bon endroit. Voici le portrait entrée/traitement/sortie (ETS) pour l’algorithme :

Points clés sur le tri par insertion :

• Le nom “insertion” fait référence à l’idée que la prochaine valeur non triée est insérée au bon endroit dans la partie triée.
• Si la collection est déjà triée, cet algorithme fera un minimum de comparaisons et aucun échange de positions. Il est donc plus efficace que le tri par sélection dans cette situation.
• Si la collection est triée avec l’ordre opposé (p.ex du plus grand au plus petit), le pire cas pour cet algorithme, le tri par insertion fera le même nombre de comparaisons que le tri par sélection.

Objectifs d’apprentissage

À la fin de cette leçon vous devrez être en mesure de :

• Différencier le tri par sélection du tri par insertion selon des descriptions ou des exemples d’implémentation.
• Identifier les meilleurs et les pires cas de l’état initial du tableau sur la performance de chacun de ces algorithmes de tri (p. ex. si le tableau est déjà ou presque trié, si le tableau est trié dans l’ordre opposé, etc.)

Critères de succès

• Je suis capable d’utiliser la méthode sort d’un ArrayList, d’un LinkedList ou d’Arrays pour faire une recherche dans différents types de collections Java.
• Je suis capable d’implémenter et d’expliquer un algorithme de tri par insertion pour des tableaux.

Notes et exercices

Pratique avec les algorithmes de base

Vous pouvez trouvez des vidéos explicatives, des exemples d’implémentations Java utilisant des tableaux et des ArrayList et des exercices interactifs en lien avec ce sujet sur le site CS Awesome, notamment la section suivante :

• Section 7.6 Algorithmes de tri