1NSI 10 TRIS

Trier


Les objets structurés (listes, dictionnaires, ...) ne sont pas toujours dans l'ordre alpha ou numéraire. Une opération importante de préparation de ces données est de les trier.
En python il y a deux façons simple de trier les listes :
    sort(liste) → Trie la liste en place, et en modifie sa valeur

    liste_triee = liste.sorted() → Trie une copie de la liste. La liste initiale n'est pas affectée

Les 2 méthodes à connaître sont le tri par insertion et le tri par sélection. Le tri par insertion est aussi appelé "tri du joueur de cartes" car c'est les plus intuitif à réaliser.

Comparer les tris


Comme il est vu dans les notions précédentes, une façon simple de comparer les tris est de mesurer leur complexité. Les 2 tris précédents sont de complexité quadratique, O(n2), ce qui n'est pas très satisfaisant poyur un grand nombre de valeurs.
On peut comparer d'autres formes de tris ici ou bien dans cette animation :


DOCUMENTS :