Introduction

Dans le monde numérique, le tri des données est une opération fondamentale qui permet d'organiser l'information de manière efficace. Comprendre les algorithmes de tri, comme le tri par insertion et le tri par sélection, est essentiel pour développer des compétences en algorithmique. Ce cours vous guidera à travers ces deux méthodes, leur fonctionnement, ainsi que des exemples concrets pour mieux les appréhender.

1. Qu'est-ce qu'un algorithme de tri ?

Les algorithmes de tri sont des procédures qui réorganisent les éléments d'une liste selon un certain ordre, généralement croissant ou décroissant. L'importance du tri réside dans sa capacité à faciliter la recherche, l'analyse et la présentation des données.

1.1 Importance du tri

Le tri est utilisé dans de nombreux domaines, tels que la gestion de bases de données, le traitement de données et même dans des applications de la vie quotidienne comme les classements sportifs. Par exemple, un classement d'élèves selon leurs notes nécessite un algorithme de tri. De plus, dans le domaine du traitement de données, le tri est souvent une étape préliminaire avant d'appliquer d'autres algorithmes, comme la recherche ou l'analyse statistique.

#### Exemple concret
Considérons une classe de 5 élèves avec leurs notes : [15, 8, 12, 20, 10]. Pour établir un classement, nous devons trier ces notes. Le résultat trié serait : [8, 10, 12, 15, 20]. Cette opération de tri permet ensuite de déterminer rapidement qui a obtenu la meilleure note.

1.2 Applications pratiques du tri

Le tri ne se limite pas aux notes scolaires. Dans le secteur commercial, le tri des produits par prix ou par popularité est crucial pour améliorer l'expérience client. Par exemple, un site de e-commerce peut afficher les produits triés par prix croissant pour aider les utilisateurs à trouver ce qu'ils recherchent rapidement. En informatique, le tri est également utilisé dans les algorithmes de recherche, où une liste triée permet d'optimiser le temps de réponse lors de la recherche d'un élément.

#### Exemple chiffré
Imaginons une liste de prix de produits : [29.99, 9.99, 19.99, 49.99, 14.99]. En triant cette liste, nous obtenons : [9.99, 14.99, 19.99, 29.99, 49.99]. Cela permet aux clients de voir rapidement les options les moins chères en premier. Un autre exemple pourrait être une liste de temps de course de 5 athlètes : [12.5, 11.2, 15.0, 10.8, 13.4]. Après tri, nous aurions : [10.8, 11.2, 12.5, 13.4, 15.0], ce qui permettrait de déterminer facilement le meilleur temps.

2. Tri par insertion

Le tri par insertion est un algorithme simple et intuitif. Il fonctionne en construisant progressivement une liste triée à partir d'une liste non triée.

2.1 Principe de fonctionnement

1. On commence avec le premier élément, qui est déjà trié.
2. On prend le prochain élément et on l'insère à la bonne position dans la liste triée.
3. On répète cette opération jusqu'à ce que tous les éléments soient triés.

#### Mini-exercice
Considérons la liste suivante : [7, 3, 5, 2, 6]. Appliquez le tri par insertion et montrez les étapes intermédiaires.
Correction :

• On commence avec le premier élément : [7]


• On insère 3 : [3, 7]


• On insère 5 : [3, 5, 7]


• On insère 2 : [2, 3, 5, 7]


• On insère 6 : [2, 3, 5, 6, 7]

La liste finale est triée : [2, 3, 5, 6, 7].

2.2 Exemple concret

Imaginons que nous ayons la liste suivante : [5, 2, 4, 6, 1, 3].

• On commence avec le premier élément : [5]