module · algorithmes de tri · 10 min
Quatre façons de mettre 16 nombres dans l'ordre.
Pas à pas, observe comment chaque algorithme compare, échange, et finit par produire un tableau trié. Compte les opérations — elles n'ont pas du tout le même coût.
défi · ressentir la complexité
palier 1 / 4
Sans rien lancer : sur CE tableau, quel algorithme fait le MOINS de comparaisons ? Choisis, puis vérifie — les compteurs se révèlent.
algo le moins coûteuxle tableau
bac à sable · exploration libre
Compare les quatre algorithmes sans contrainte : choisis-en un, lance la simulation, observe les comparaisons et les échanges.
étape 1 / 2comparaisons 0échanges 0
réglages
16
×3
à retenir
comme une main de cartes : on prend chaque élément et on l'insère à sa place dans la partie déjà triée.
def tri_insertion(t):
for i in range(1, len(t)):
cle = t[i]
j = i - 1
while j >= 0 and t[j] > cle:
t[j + 1] = t[j]
j -= 1
t[j + 1] = cle
return tpourquoi le tri fusion gagne sur les grands tableaux
| algorithme | n = 100 | n = 10 000 | n = 1 000 000 |
|---|---|---|---|
| sélection, insertion, bulles (n²) | 10 000 | 100 000 000 | 10¹² |
| fusion (n log n) | ~ 700 | ~ 130 000 | ~ 20 000 000 |
À un million d'éléments, le tri fusion est environ 50 000 fois plus rapide. C'est pour ça que Python utilise Timsort (variante de fusion) en interne.