Sorting algorithms · Algorithmes de tri
| English | Français |
|---|---|
| bubble sort/ˈbʌbl sɔːt/ | tri à bulles |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | tri par insertion |
| in place/ɪn pleɪs/ | in place |
| stable/ˈsteɪbl/ | stable |
The sort that is slow on purpose
- Every serious library sorts with an algorithm no exam asks you to write. Bubble sort and insertion sort are both $O(n^2)$, and both are beaten by any decent sort on a large list.
- They are on the syllabus anyway, and for a good reason: they are short enough to trace by hand, and tracing one is how you learn what a sort actually does to an array.
- There is also a real case for insertion sort. On a list that is small, or already nearly sorted, it is genuinely the fastest thing there is, and real libraries switch to it for exactly those cases.
- This lesson is bubble sort 冒泡排序 and insertion sort 插入排序: the algorithms, their behaviour, and where each one wins.
Le tri qui est lent intentionnellement
- Chaque bibliothèque sérieuse trie avec un algorithme que les examens ne vous demandent pas d'écrire. Le tri à bulles et le tri par insertion sont tous deux $O(n^2)$, et les deux sont battus par n'importe quel bon tri sur une grande liste.
- Ils figurent au programme de toute façon, et pour une bonne raison : ils sont assez courts pour être tracés à la main, et tracer l'un d'eux est la meilleure façon d'apprendre ce qu'un tri fait réellement à un tableau.
- Il existe aussi un cas réel pour le tri par insertion. Sur une liste petite ou presque triée, il est véritablement le plus rapide qui soit, et les bibliothèques réelles basculent dessus pour exactement ces raisons.
- Cette leçon porte sur le tri à bulles (冒泡排序) et le tri par insertion (插入排序) : les algorithmes, leur comportement et là où chacun l'emporte.
Bubble sort
- Each pass compares adjacent pairs and swaps any that are out of order, so the largest remaining value "bubbles" to the end.
- After pass $k$ the last $k$ elements are final, which is why the inner loop stops at $n - \text{pass}$.
- The
swappedflag lets it stop early: if a whole pass makes no swap, the list is sorted.
Tri bulle
FOR pass ← 1 TO n - 1
swapped ← FALSE
FOR i ← 1 TO n - pass
IF A[i] > A[i + 1] THEN
swap A[i], A[i + 1]
swapped ← TRUE
ENDIF
NEXT i
IF NOT swapped THEN // already sorted
EXIT FOR
ENDIF
NEXT pass
- Chaque passe compare des paires adjacentes et échange celles qui sont hors ordre, de sorte que la plus grande valeur restante « remonte à la bulle » vers la fin.
- Après la passe $k$, les derniers $k$ éléments sont définitifs, c'est pourquoi la boucle intérieure s'arrête à $n - \text{pass}$.
- Le drapeau
swappedlui permet de s'arrêter précocement : si une passe entière ne produit aucun échange, la liste est triée.
Insertion sort
- It builds a sorted section at the front, growing by one each time. Each new element is held aside as
key, larger elements are shifted right to open a gap, and the key is dropped in. - This is how most people sort a hand of playing cards, which is the analogy the exam expects.
The left is sorted, the right is untouched, and the boundary moves right
Tri par insertion
FOR i ← 2 TO n
key ← A[i]
j ← i - 1
WHILE j >= 1 AND A[j] > key DO
A[j + 1] ← A[j] // shift right
j ← j - 1
ENDWHILE
A[j + 1] ← key // drop it in
NEXT i
- Il construit une section triée à l'avant, qui grandit d'un élément à chaque fois. Chaque nouvel élément est mis de côté comme
key, les éléments plus grands sont déplacés vers la droite pour créer un espace, et la clé est insérée à cet endroit. - C'est ainsi que la plupart des gens trient un jeu de cartes, ce qui est l'analogie attendue par les examens.
La partie gauche est triée, la partie droite est intacte, et la frontière se déplace vers la droite
Sorting algorithms · Algorithmes de tri
compare adjacent, swap if needed · comparer les éléments adjacents, échanger si nécessaire
Step through a bubble sort: each pass floats the largest value to the end. · Parcourir un tri à bulles : chaque passage fait remonter la valeur la plus grande à la fin.
Bubble sort works by: · Le tri à bulles fonctionne par :
Each pass swaps adjacent pairs, "bubbling" the largest element to the end. · Chaque passage échange les paires adjacentes, « faisant remonter » l'élément le plus grand à la fin.
The average/worst-case time complexity of bubble sort is: · La complexité temporelle moyenne/pire cas du tri à bulles est :
Two nested loops over n elements give O(n²); the best case (already sorted) is O(n) with the early exit. · Deux boucles imbriquées sur n éléments donnent O(n²) ; le meilleur cas (déjà trié) est O(n) avec sortie anticipée.
Worked example: trace one pass
- Trace the first pass of a bubble sort on 5, 3, 8, 1.
- Compare 5 and 3: out of order, swap, giving 3, 5, 8, 1. Compare 5 and 8: in order, no swap. Compare 8 and 1: swap, giving 3, 5, 1, 8.
- After one pass the largest value, 8, is in its final position, and one more comparison per pass can be skipped from now on.
- Now trace insertion sort's third step on 3, 5, 8, 1. The key is 1. Shift 8, 5 and 3 each one place right, then place 1 at the front: 1, 3, 5, 8. Show the array after every step; that is where the marks are.
Exemple résolu : tracer une passe
- Tracez la première passe d'un tri à bulles sur 5, 3, 8, 1.
- Comparez 5 et 3 : hors ordre, échange, donnant 3, 5, 8, 1. Comparez 5 et 8 : dans l'ordre, pas d'échange. Comparez 8 et 1 : échange, donnant 3, 5, 1, 8.
- Après une passe, la plus grande valeur, 8, est dans sa position finale, et une comparaison de moins par passe peut être omise dès maintenant.
- Maintenant tracez la troisième étape du tri par insertion sur 3, 5, 8, 1. La clé est 1. Déplacez 8, 5 et 3 d'une place vers la droite, puis placez 1 au début : 1, 3, 5, 8. Montrez le tableau après chaque étape ; c'est là que se trouvent les points.
Insertion sort builds the sorted result by: · Le tri par insertion construit le résultat trié en :
It grows a sorted prefix on the left, shifting larger elements right to drop each key into place. · Il étend un préfixe trié à gauche, décalant les éléments plus grands vers la droite pour placer chaque clé.
How does insertion sort place each new element? · Comment le tri par insertion place-t-il chaque nouvel élément ?
Holding the key aside and shifting is what distinguishes it from bubble sort's repeated adjacent swaps. · Garder la clé de côté et décaler distingue cette méthode des échanges adjacents répétés du tri à bulles.
Performance
| bubble | insertion | |
|---|---|---|
| best case | $O(n)$, one pass with no swaps | $O(n)$, already sorted, no shifts |
| average and worst | $O(n^2)$ | $O(n^2)$ |
| extra memory | $O(1)$, in place 原地 | $O(1)$, in place |
| stable | yes | yes, stable 稳定 |
- In place means it needs only a constant amount of extra memory, sorting within the array itself. Stable means two equal values keep their original relative order, which matters when a list has already been sorted by another field.
- Both reach $O(n)$ on already-sorted data, but only if bubble sort has the
swappedflag. Without it, it always performs every pass.
Performances
| bulles | insertion | |
|---|---|---|
| meilleur cas | $O(n)$, une passe sans échanges | $O(n)$, déjà trié, pas de déplacements |
| moyenne et pire | $O(n^2)$ | $O(n^2)$ |
| mémoire supplémentaire | $O(1)$, in place (原地) | $O(1)$, in place |
| stable | oui | oui, stable (稳定) |
- In place signifie qu'il ne nécessite qu'une quantité constante de mémoire supplémentaire, triant directement dans le tableau. Stable signifie que deux valeurs égales conservent leur ordre relatif initial, ce qui est important lorsqu'une liste a déjà été triée selon un autre champ.
- Tous deux atteignent $O(n)$ sur des données déjà triées, mais seulement si le tri à bulles a le drapeau
swapped. Sans lui, il effectue toujours tous les passages.
After the first pass of a bubble sort on 5, 3, 8, 1, what is the array? Write the four numbers separated by commas. · Après le premier passage d'un tri à bulles sur 5, 3, 8, 1, quel est le tableau ? Écrire les quatre nombres séparés par des virgules.
5 and 3 swap, 5 and 8 do not, 8 and 1 swap. The largest value has reached the end, so the next pass can be one comparison shorter. · 5 et 3 échangent, 5 et 8 ne changent pas, 8 et 1 échangent. La valeur la plus grande a atteint la fin, donc le prochain passage peut faire une comparaison de moins.
Worked example: which sort, and why
- A list of 200,000 records must be sorted from scratch. Neither: both are $O(n^2)$, so a merge or quick sort at $O(n \log n)$ is needed. Say so rather than choosing the least bad.
- A sorted list of 10,000 gains 5 new records at the end and must be sorted again. Insertion sort: the data is nearly sorted, so each new key shifts only a short distance and it approaches $O(n)$.
- A teaching example must be traced by hand on paper. Bubble sort: it is the simplest to follow, which is its real remaining use.
- Justify from the state of the data and the size, not from a general preference.
Exemple résolu : quel tri, et pourquoi
- Une liste de 200,000 enregistrements doit être triée à partir de zéro. Ni l'un ni l'autre : les deux sont $O(n^2)$, il est donc nécessaire d'effectuer un tri par fusion ou un tri rapide à $O(n \log n)$. Précisez-le plutôt que de choisir le moins mauvais.
- Une liste triée de 10,000 gagne 5 nouveaux enregistrements à la fin et doit être triée à nouveau. Tri par insertion : les données sont presque triées, donc chaque nouvelle clé ne se déplace que sur une courte distance et elle approche $O(n)$.
- Un exemple pédagogique doit être tracé à la main sur papier. Tri à bulles : c'est le plus simple à suivre, c'est son usage principal restant.
- Justifiez à partir de l'état des données et de la taille, pas d'une préférence générale.
Match each sorting idea to what it means. · Reliez chaque idée de tri à sa signification.
Bubble swaps neighbours, insertion grows a sorted prefix; both are O(n²) worst-case; stability is about equal-key order. · Les bulles échangent les voisins, l'insertion étend un préfixe trié ; les deux ont un pire cas O(n²) ; la stabilité concerne l'ordre des clés égales.
Insertion sort runs close to O(n) on small or nearly-sorted arrays, because few elements need to be shifted. · Le tri par insertion s'approche de O(n) sur les petits tableaux ou presque triés, car peu d'éléments doivent être déplacés.
On nearly-sorted data each new item is already almost in place — which is why insertion sort beats fancier sorts on small inputs. · Sur des données presque triées, chaque nouvel élément est déjà presque en place — c'est pourquoi le tri par insertion bat les tris plus complexes sur les petites entrées.
Which are true of both bubble sort and insertion sort? Select all · tout that apply. · Quelles affirmations sont vraies pour le tri à bulles ET le tri par insertion ? Sélectionnez toutes les options qui s'appliquent.
On a large unsorted list an O(n log n) sort wins decisively. Saying so is the right answer, not choosing the least bad of the two. · Sur une grande liste non triée, un tri O(n log n) l'emporte décisivement. Dire cela est la bonne réponse, pas choisir le moins mauvais des deux.
Why one pass is not the whole story
- Both sorts do repeated passes, and the exam distinguishes them by what one pass achieves and by when they stop.
- A bubble sort pass compares adjacent pairs and swaps them, so one pass carries the largest remaining item to its final place. The whole sort is $n - 1$ passes.
- An insertion sort pass takes the next item and moves it back into the already-sorted part, so after $k$ passes the first $k$ items are sorted among themselves but not yet in final position.
- Bubble sort can be improved with a flag: if a pass makes no swaps, the list is already sorted and the algorithm stops. On nearly-sorted data that turns it into one pass.
- Without the flag, both are $n^2$ in the worst case, which is why either is a poor choice for a large file and why the exam asks about small ones.
Pourquoi une seule passe ne suffit pas
- Les deux triers effectuent des passes répétées, et l'examen les distingue par ce qu'une passe atteint et par quand ils s'arrêtent.
- Une passe de tri à bulles compare des paires adjacentes et les échange, donc une passe transporte le plus grand élément restant à sa place définitive. Le tri complet nécessite $n - 1$ passes.
- Une passe de tri par insertion prend l'élément suivant et le replique dans la partie déjà triée, donc après $k$ passes, les premiers $k$ éléments sont triés entre eux mais pas encore dans leur position finale.
- Le tri à bulles peut être amélioré avec un drapeau : si une passe ne produit aucun échange, la liste est déjà triée et l'algorithme s'arrête. Sur des données presque triées, cela le réduit à une seule passe.
- Sans le drapeau, les deux sont $n^2$ dans le cas le plus défavorable, ce qui explique pourquoi l'un ou l'autre est un mauvais choix pour un grand fichier et pourquoi l'examen porte sur de petits fichiers.
A sorted list of 10,000 records gains 5 new records at the end. Which sort suits re-sorting it? · Une liste triée de 10,000 enregistrements gagne 5 nouveaux enregistrements à la fin. Quel tri convient pour les réorganiser ?
Nearly sorted data is exactly insertion sort's best case, approaching O(n). Real libraries switch to it for this reason. · Les données presque triées correspondent exactement au meilleur cas du tri par insertion, s'approchant de O(n). Les bibliothèques réelles basculent dessus pour cette raison.
Match each sort to what one pass achieves. · Reliez chaque tri à ce qu'un seul passage accomplit.
That difference is what a trace question is really testing. A bubble-sort flag also lets it stop early on nearly-sorted data, which insertion sort handles well anyway. · Cette différence est ce qu'une question de trace teste vraiment. Un indicateur de tri à bulles permet aussi de s'arrêter tôt sur des données presque triées, ce que le tri par insertion gère bien de toute façon.
Marks that slip away
- Bubble sort compares adjacent pairs. An answer that compares an element with all the others is describing a different algorithm.
- The inner loop shortens each pass, because the end of the array is already final. Say why.
- Insertion sort shifts elements right to open a gap; it does not swap repeatedly. The distinction is the point of the algorithm.
- Both are $O(n^2)$ on average and at worst, and $O(n)$ at best. Give the case with the order.
Pièges qui font perdre des points
- Le tri à bulles compare des paires adjacentes. Une réponse qui compare un élément avec tous les autres décrit un algorithme différent.
- La boucle intérieure se raccourcit à chaque passe, car la fin du tableau est déjà définitive. Expliquez pourquoi.
- Le tri par insertion décale les éléments vers la droite pour créer un espace ; il n'échange pas de manière répétée. Cette distinction est le cœur de l'algorithme.
- Les deux sont $O(n^2)$ en moyenne et au pire, et $O(n)$ au mieux. Donnez le cas avec la complexité.
You've got it
- bubble sort: repeated passes comparing adjacent pairs and swapping, largest bubbling to the end, inner loop shortening each pass, with a
swappedflag for early exit - insertion sort: grow a sorted section at the front, holding each key aside, shifting larger elements right and dropping the key into the gap
- both are $O(n^2)$ average and worst, $O(n)$ best, in place and stable
- insertion sort genuinely wins on small or nearly sorted lists; for a large unsorted list neither is the right answer
Vous avez compris
- tri à bulles : passes répétées comparant des paires adjacentes et échangeant, la plus grande remontant à la bulle vers la fin, boucle intérieure se raccourcissant à chaque passe, avec un drapeau
swappedpour sortie anticipée - tri par insertion : faire croître une section triée à l'avant, mettant chaque clé de côté, décalant les éléments plus grands vers la droite et plaçant la clé dans l'espace
- les deux sont $O(n^2)$ en moyenne et au pire, $O(n)$ au mieux, in place et stable
- le tri par insertion l'emporte véritablement sur les listes petites ou presque triées ; pour une grande liste non triée, ni l'un ni l'autre n'est la bonne réponse