ICS4U

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.

Définitions

Vous devrez comprendre deux algorithmes de recherche : le tri par sélection et le tri par insertion.

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.

Description	Partie triée	Partie non triée
Côté	Gauche	Droit
Index	0 … i	i+1 … length - 1

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 :

Entrée	Traitement	Sortie
Une liste ou un tableau de valeurs	1. Identifier l’index min comme l’index de la première valeur dans la partie non-triée du tableau. 2. Comparer la valeur à l’index min avec toutes les valeurs restantes dans la partie non triée : si l’autre valeur est plus petite, changer l’index min pour l’index de la valeur plus petite. 3. Échanger la valeur du premier élément de la partie non-triée avec la valeur à l’index min. 4. Avancer d’une position dans la collection et répéter les étapes 1 à 3 jusqu’à ce qu’on arrive à l’avant dernier index.	Retourner rien (le tableau ou la liste original est trié sur place en mémoire)

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 :

Entrée	Traitement	Sortie
Une liste ou un tableau de valeurs	1. Définir l’index actuel à 1. 2. Pendant que actuel est moins grand que la taille de la collection - 1, répéter les étapes 3 à 7. 3. Assigner à temp la valeur à l’index actuel. 4. Définir l’index final comme (actuel - 1). 5. Pendant que final est plus grand que 0 ET temp et plus petit que la valeur à l’index final, diminuer la valeur de final par 1. 6. Échanger les valeurs aux index actuel et final. 7. Augmenter actuel par 1.	Retourner rien (le tableau ou la liste original est trié sur place en mémoire)

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