Algorithmes de tri

L'une des opérations les plus courantes en programmation est le tri d'objets.

Un algorithme de tri consiste en une suite finie d'opérations permettant d'organiser une collection d'objets selon un ordre prédéterminé. Par conséquent, les objets à trier font partie d'un ensemble muni d'une relation d'ordre comme, par exemple, l'ordre numérique ou lexicographique. Le but de cette section est d'étudier quelques algorithmes de tri élémentaires bien adaptés aux listes contenant peu de données. Parmi ces méthodes élémentaires, nous mettrons l'accent dans un premier temps sur le tri par sélection, le tri par insertion et le tri par bulles puis nous traiterons d'un algorithme de tri plus performant appelé le tri par fusion pour finalement nous pencher sur l'un des algorithmes de tri les plus populaires de par ses performances qui est le tri rapide.

La principale caractéristique qui permet de décrire l'efficacité d'un algorithme de tri est sa complexité algorithmique. Cette analyse permet de prévoir les ressources (comme la quantité de mémoire) nécessaires à l'algorithme et de mesurer son temps d'exécution. Ce temps peut être estimé en calculant le nombre moyen de comparaisons et déplacements exécutés pour trier un ensemble de n éléments. Comme nous le verrons dans cette section, les méthodes de tri élémentaires requièrent un nombre d'étapes correspondant approximativement au carré du nombre d'éléments à trier, ce qui s'avère souvent inefficace lorsque le nombre n d'éléments à trier est grand. Néanmoins, nous verrons que le tri rapide réalise l'opération de tri en un temps croissant comme nlog(n) en fonction du nombre n d'éléments à trier.

Table des matières

Cette section a pour but de décrire, comparer et d'implémenter les principaux algorithmes de tri classiques. Les liens suivants permettent d'atteindre directement ses principales parties:

• Tri par sélection
• Tri par insertion
• Tri par bulles
• Tri par fusion
• Tri rapide

Objectifs

Au terme de cette section, chaque élève devra être capable de :

• expliquer ce qu'est la complexité algorithmique et l'illustrer au travers des algorithmes de tri;
• décrire le déroulement des algorithmes de tri élémentaires (sélection, insertion, par bulles) ainsi que du tri par fusion et du tri rapide appliqués à une liste d'entiers;
• comparer les performances des algorithmes de tri élémentaires en terme de nombre de comparaisons et de déplacements/échanges nécessaires;
• pour chaque algorithme de tri élémentaire, déterminer la meilleure et la pire configuration possible de la liste sur laquelle est appliqué l'algorithme;
• implémenter chacun des algorithmes de tri élémentaires;
• implémenter le tri par fusion;
• dénombrer les comparaisons nécessaires au tri par fusion pour ordonner une liste de n éléments dans le meilleur et le pire des cas;
• décrire le déroulement du tri rapide sur une liste quelconque à partir de son code;
• identifier le meilleur et le pire des cas sur lequel peut être appliqué le tri rapide;
• justifier le nombre de comparaison nécessaires au tri rapide d'une liste de n éléments dans le meilleur et le pire des cas.

Présentation

Cette section est complétée d'une présentation faite en classe et accessible dans l'encadré ci-dessous: