Sorting · Tri
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · Cette page nécessite un navigateur récent (avec support SharedArrayBuffer). Veuillez mettre à jour Chrome, Edge, Firefox ou Safari vers la dernière version.
English
Putting items in order
- Sorting arranges a list into order, usually smallest first.
- The key move is a swap: exchange two items.
- In Python:
a[i], a[j] = a[j], a[i]swaps two list items in one line.
Français
Mettre des éléments en ordre
- Tri arrange une liste dans l'ordre, généralement du plus petit au plus grand.
- Le mouvement clé est un échange : échanger deux éléments.
- En Python :
a[i], a[j] = a[j], a[i]échange deux éléments de liste en une ligne.
English
Bubble sort
- Compare each pair of neighbours; swap them if they are out of order.
- After one full pass, the largest item has "bubbled" to the end.
- Repeat the passes until no swaps are needed.
Français
Tri bulle
- Comparez chaque paire de voisins ; échangez-les s'ils sont dans le mauvais ordre.
- Après un passage complet, l'élément le plus grand a « bulonné » jusqu'à la fin.
- Répétez les passes jusqu'à ce qu'aucun échange ne soit nécessaire.
data = [3, 1, 2]
n = len(data)
for i in range(n - 1):
for j in range(n - 1 - i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
print(data)
English
Insertion sort
- Treat the left part of the list as already sorted.
- Take the next item and slide it left until it sits in the right place.
- Like sorting playing cards in your hand, one at a time.
Français
Tri par insertion
- Traitez la partie gauche de la liste comme déjà triée.
- Prenez l'élément suivant et faites-le glisser vers la gauche jusqu'à ce qu'il soit bien placé.
- Comme le tri de cartes à jouer dans votre main, une par une.
data = [3, 1, 2]
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j + 1] = data[j]
j = j - 1
data[j + 1] = key
print(data)
English
Compare them
- Both check roughly
n × npairs, so both are slow on big lists. - Insertion sort is fast when the list is almost sorted already.
- Faster methods exist, but bubble and insertion are easy to understand.
Français
Comparez-les
- Les deux vérifient environ
n × npaires, donc les deux sont lents sur de grandes listes. - Le tri par insertion est rapide quand la liste est presque déjà triée.
- Des méthodes plus rapides existent, mais le tri bulle et l'insertion sont faciles à comprendre.
English
In Cambridge pseudocode
- Bubble sort with a
tempvariable for the swap.
Français
En pseudocode Cambridge
- Tri bulle avec une variable
temppour l'échange.
FOR i ← 0 TO LENGTH(list) - 2
FOR j ← 0 TO LENGTH(list) - 2 - i
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
ENDIF
NEXT j
NEXT i
English
Common mistakes
- Bubble and insertion sort are both O(n²).
- Trace a small list by hand to check your sort works.
Français
Erreurs courantes
- Le tri bulle et l'insertion sont tous deux O(n²).
- Tracez une petite liste à la main pour vérifier que votre tri fonctionne.
English
Now you try
- Each task changes the list in place — no need to return it.
- Press Check answer to test your code.
Français
À vous maintenant
- Chaque tâche modifie la liste in situ — pas besoin de la retourner.
- Appuyez sur Vérifier la réponse pour tester votre code.
Explore · Explorer
Watch a sort run · Regardez un tri s'exécuter
Sorting repeatedly compares and swaps until everything is in order. · Le tri compare et échange répétitivement jusqu'à ce que tout soit en ordre.
Write swap(items, i, j) that exchanges the items at index i and index j in the list. Change the list in place (no return). · Écrivez swap(items, i, j) qui échange les éléments aux indices i et j dans la liste. Modifiez la liste in place (pas de return).
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write bubble_sort(items) that sorts the list into ascending order using bubble sort. Change the list in place. · Écrivez bubble_sort(items) qui trie la liste en ordre croissant en utilisant le tri à bulles. Modifiez la liste in place.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write insertion_sort(items) that sorts the list into ascending order using insertion sort. Change the list in place. · Écrivez insertion_sort(items) qui trie la liste en ordre croissant en utilisant le tri par insertion. Modifiez la liste in place.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.