Bases & algorithmique · 6 mondes · 18 étapes
Algorithmique
Apprendre à penser un problème, en Python, dans le navigateur.
Progression
0 %
0/18 étapes terminées
Intermédiaire · 10 min de lecture
Les tris
Sélection, insertion, et pourquoi sorted() gagne
1Définition
Trier, c'est réorganiser une collection selon un ordre. Les tris élémentaires (sélection, insertion, bulles) sont en O(n²) ; les tris efficaces (fusion, rapide, Timsort) atteignent O(n log n), qui est la limite théorique des tris par comparaison.
2Principes fondamentaux
01
Un tri est une recherche répétée
Le tri par sélection cherche le minimum n fois. Comprendre ça démystifie tous les tris.
02
L'insertion aime l'ordre existant
Sur une liste presque triée, le tri par insertion devient quasi linéaire. C'est pourquoi il survit à l'intérieur des tris industriels.
03
Stabilité
Un tri est stable s'il préserve l'ordre initial des valeurs égales. Indispensable pour trier par deux critères successifs. sorted() est stable.
04
En production, on n'écrit pas son tri
sorted() est en C, hybride, testé par des millions d'usages. L'écrire soi-même une fois sert à le comprendre, pas à le remplacer.
3Exemples pratiques
L'échange, en une ligne
1colis[i], colis[mini] = colis[mini], colis[i]Python construit un couple à droite puis le réaffecte à gauche : pas besoin de variable temporaire.
Trier par un critère
1joueurs = [("ana", 42), ("bo", 17), ("cy", 42)]2 3par_score = sorted(joueurs, key=lambda j: j[1], reverse=True)4print(par_score) # [('ana', 42), ('cy', 42), ('bo', 17)]key choisit sur quoi trier. La stabilité garde « ana » devant « cy » puisqu'ils avaient le même score et cet ordre d'origine.
4Erreurs courantes
Confondre sort() et sorted()
À éviter
tries = prix.sort() # None !À faire
prix.sort() # modifie prixtries = sorted(prix) # nouvelle listePourquoi : .sort() trie sur place et renvoie None. sorted() renvoie une nouvelle liste et laisse l'originale intacte.
Échanger avec une seule affectation
À éviter
a = bb = aÀ faire
a, b = b, aPourquoi : La première version écrase a avant de l'avoir sauvegardé : les deux valeurs finissent identiques.
Modifier une liste pendant qu'on la parcourt
À éviter
for x in liste: if x < 0: liste.remove(x)À faire
liste = [x for x in liste if x >= 0]Pourquoi : Retirer un élément décale les suivants : la boucle en saute. Construire une nouvelle liste est sûr et plus lisible.
5Subtilités à connaître
- ◆
sorted()de Python utilise Timsort, conçu pour exploiter les portions déjà triées des données réelles. - ◆Le tri rapide est en moyenne le plus performant, mais son pire cas est O(n²) — d'où les versions hybrides.
- ◆On peut trier sans comparer (tri par comptage, radix) et descendre sous n log n, à condition de connaître la nature des données.
6Vérifie ta compréhension
Question 1/3
Score 0
Que renvoie prix.sort() ?
Envie d'essayer ? Ouvre le Labo et recopie les exemples pour les modifier.