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.
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éter les passages. Après
n − 1passages, la liste est certainement triée ; on peut s'arrêter plus tôt si un passage ne provoque aucun échange.
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)
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)
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.
En pseudocode Cambridge
- Tri bulle avec une variable
temppour l'échange, sur un tableaulist[1:n].
FOR i ← 1 TO n - 1
FOR j ← 1 TO n - 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
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.
À 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.
Watch a sort run
Sorting repeatedly compares and swaps until everything is in order.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
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).
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Write bubble_sort(items) that sorts the list into ascending order using bubble sort. Change the list in place.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Write insertion_sort(items) that sorts the list into ascending order using insertion sort. Change the list in place.
Cliquez sur Exécuter pour voir le résultat ici.