Algorithmes de tri
Introduit| English | Sens |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | Tri |
| selection sort/sɪˈlekʃn sɔːt/ | tri par sélection |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | tri par insertion |
| in place/ɪn pleɪs/ | en place |
Mettre des choses en ordre
- Le trien réorganise les éléments par ordre (du plus petit au plus grand, par exemple).
- Le cours AP couvre deux triels simples : le trier par sélection et le trier par insertion.
- Tous deux utilisent des boucles imbriquées et échangent ou déplacent les éléments à leur place.
- Trier d'abord permet d'utiliser ensuite la recherche binaire rapide.
Tri par sélection
- Trouvez l'élément restant le plus petit et échangez-le vers le début.
- Ensuite, trouvez le plus petit parmi ce qui reste, échangez-le dans la position suivante, et ainsi de suite.
- Le début du tableau devient trié ; la fin diminue en étant non trié.
- Un échange par passage — mais il parcourt toujours le reste à chaque passage.

Un tri par insertion, déplaçant chaque clé à sa place itération après itération
Tri par insertion
- Prenez l'élément suivant et déplacez-le vers l'arrière à sa place correcte parmi le début déjà trié.
- Comme trier un jeu de cartes : insérez chaque nouvelle carte à l'endroit qu'elle mérite.
- La région triée s'agrandit d'un élément à chaque passage.
- Rapide lorsque les données sont déjà presque triées.
Combien de travail
- Les deux tris utilisent des boucles imbriquées, donc ils effectuent environ
n²comparaisons dans le cas le plus défavorable. - C'est acceptable pour de petits tableaux, mais lent pour de très grands.
- Ils trient en place — aucun second tableau n'est nécessaire.
- L'examen veut que vous les tracez, pas seulement que vous les nommiez.
Le tri par sélection ÉCHANGE l'élément restant le plus petit vers le début ; le tri par insertion DÉPLACE chaque nouvel élément vers l'arrière dans la partie triée — ne les mélangez pas. Les deux sont des tris en boucles imbriquées O(n²) et trient tous deux en place. Tracez-les étape par étape (l'examen AP demande l'état du tableau après chaque passage), plutôt que de mémoriser un nom.
Tri par sélection sur [3, 1, 2] :
- Passage 1 : le plus petit est
1; échange vers le début →[1, 3, 2]. - Passage 2 : le plus petit de
[3, 2]est2; échange →[1, 2, 3]. - Trié — le début s'est agrandi d'un élément à chaque passage.
Trier ordonne les éléments. Le tri par sélection échange répétitivement l'élément restant le plus petit vers le début ; le tri par insertion déplace chaque nouvel élément vers l'arrière dans la partie triée. Les deux sont en boucles imbriquées, en place, des tris O(n²). Trier permet ensuite une recherche binaire rapide.
Parcourir un tri
Chaque passage place un élément de plus en ordre.
Le tri par sélection fonctionne en...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Le tri par sélection sélectionne le minimum et l'échange vers l'avant.
Le tri par insertion fonctionne en...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Le tri par insertion insère chaque élément à sa place triée.
Dans le cas le plus défavorable, les deux tris effectuent environ...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Les boucles imbriquées donnent O(n²).
Les tris par sélection et par insertion fonctionnent in-place (sans second tableau).
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Ils réarrangent le même tableau.
Ordonnez les passages du tri par sélection sur [3, 1, 2].
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
L'avant grandit trié, un élément par passage.
Trier d'abord est utile car cela permet ensuite d'utiliser...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
La recherche binaire nécessite des données triées.