Sorting Algorithms · Algorithmes de tri
| English | Français |
|---|---|
| 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/ | in place |
Putting things in order
- Sorting 排序 rearranges elements into order (smallest to largest, say).
- The AP course covers two simple sorts: selection sort 选择排序 and insertion sort 插入排序.
- Both use nested loops and swap or shift elements into place.
- Sorting first is what lets you use fast binary search afterwards.
Mettre des choses en ordre
- Trier 排序 réorganise les éléments dans l'ordre (du plus petit au plus grand, par exemple).
- Le cours AP couvre deux tris simples : trih par sélection 选择排序 et tri 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.
Selection sort
- Find the smallest remaining element and swap it to the front.
- Then find the smallest of what's left, swap it into the next spot, and so on.
- The front of the array grows sorted; the back shrinks unsorted.
- One swap per pass — but it still scans the rest each pass.
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.
Insertion sort
- Take the next element and shift it back into its correct place among the already-sorted front.
- Like sorting a hand of cards: slot each new card where it belongs.
- The sorted region grows by one each pass.
- Fast when the data is already nearly sorted.
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.
How much work
- Both sorts use nested loops, so they do about
n²comparisons in the worst case. - That's fine for small arrays but slow for very large ones.
- They sort in place 原地 — no second array needed.
- The exam wants you to trace them, not just name them.
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écessaire.
- L'examen veut que vous les tracez, pas seulement que vous les nommiez.
Selection sort SWAPS the smallest remaining element to the front; insertion sort SHIFTS each new element back into the sorted part — don't mix them up. Both are O(n²) nested-loop sorts and both sort in place. Trace them step by step (the AP exam asks for the array's state after each pass), rather than memorising a name.
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.
Selection sort on [3, 1, 2]:
- Pass 1: smallest is
1; swap to front →[1, 3, 2]. - Pass 2: smallest of
[3, 2]is2; swap →[1, 2, 3]. - Sorted — the front grew one element per pass.
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.
Sorting orders elements. Selection sort repeatedly swaps the smallest remaining element to the front; insertion sort shifts each new element back into the sorted part. Both are nested-loop, in-place, O(n²) sorts. Sorting enables fast binary search afterwards.
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.
Stepping through a sort · Parcourir un tri
Each pass places one more element in order. · Chaque passage place un élément de plus en ordre.
Selection sort works by... · Le tri par sélection fonctionne en...
Selection sort selects the minimum and swaps it forward. · Le tri par sélection sélectionne le minimum et l'échange vers l'avant.
Insertion sort works by... · Le tri par insertion fonctionne en...
Insertion sort inserts each element into its sorted place. · Le tri par insertion insère chaque élément à sa place triée.
In the worst case, both sorts do about... · Dans le cas le plus défavorable, les deux tris effectuent environ...
Nested loops give O(n²). · Les boucles imbriquées donnent O(n²).
Both selection and insertion sort work in place (no second array). · Les tris par sélection et par insertion fonctionnent in-place (sans second tableau).
They rearrange the same array. · Ils réarrangent le même tableau.
Order the passes of selection sort on [3, 1, 2]. · Ordonnez les passages du tri par sélection sur [3, 1, 2].
Front grows sorted, one element per pass. · L'avant grandit trié, un élément par passage.
Sorting first is useful because it lets you later use... · Trier d'abord est utile car cela permet ensuite d'utiliser...
Binary search needs sorted data. · La recherche binaire nécessite des données triées.