Le tri selon Python⚓︎
Fonctions de tri⚓︎
Python trie les tableaux avec la méthode list.sort (tri en place, le tableau est mis à jour) :
>>> tableau = [3, 4, 0, 2, 1]
>>> tableau.sort()
>>> tableau
[0, 1, 2, 3, 4]
Remarque
Il faut toutefois que les éléments du tableau soient comparables les uns avec les autres.
Par exemple, les str et les int sont deux types comparables, Python peut évaluer les expressions 'allo' < 'hello' et 3 < 5. Les tableaux ['allo', 'hello'] et [3, 5] peuvent donc être triés.
Par contre, le tableau ['allo', 'hello', 3, 5] ne peut pas être trié car 'allo' et 3 ne sont pas comparables.
Il est aussi possible de trier des list ou d'autres types de données tels que les tuple et les dict en utilisant la fonction sorted. Dans ce cas, Python crée un nouveau tableau contenant les mêmes valeurs que l'argument et le trie. La fonction renvoie la copie triée, l'argument initial n'est pas modifié.
>>> un_tuple = (3, 4, 0, 2, 1)
>>> sorted(un_tuple)
[0, 1, 2, 3, 4]
>>> un_tuple
(3, 4, 0, 2, 1)
Attention
Dans le cas ou l'argument est un dictionnaire, sorted renvoie le tableau des clés trié dans l'ordre croissant :
>>> dictionnaire = {'Nicolas': 30, 'Élodie': 5}
>>> sorted(dictionnaire)
['Nicolas', 'Élodie']
On notera au passage que lors de la comparaison des chaînes de caractères, Python compare les codes ASCII de chaque caractère. Ceci explique que 'É' (de code 201) soit supérieur à 'N' (de code 78) !
Dans les deux cas il est possible de passer un booléen reverse en argument. Si l'on passe reverse = True, le tri se fera dans l'ordre décroissant. Par défaut on a reverse = False (tri dans l'ordre croissant).
>>> tableau = [3, 4, 0, 2, 1]
>>> tableau.sort(reverse = True)
>>> tableau
[4, 3, 2, 1, 0]
Si l'on fournit des données structurées à la fonction de tri (des list ou des tuple par exemple), le tri se fera tout d'abord sur le premier élément de chaque donnée, puis sur le deuxième etc :
>>> tableau = [("Alphonse", 100), ("Zélie", 0), ("Alphonse", 50)]
>>> tableau.sort()
>>> tableau
[('Alphonse', 50), ('Alphonse', 100), ('Zélie', 0)]
Il peut arriver que l'on souhaite trier le tableau en selon un critère particulier. C'est le cas par exemple si les données sont des couples de valeurs et que l'on souhaite effectuer le tri sur la seconde valeur de chaque couple.
Dans ce cas on utilise le mot-clé key et l'on passe en argument une fonction qui renvoie la seconde valeur de chaque couple :
>>> def second(couple):
... return couple[1]
...
>>> tableau = [("Alphonse", 100), ("Zélie", 0), ("Alphonse", 50)]
>>> tableau.sort(key = second)
>>> tableau
[('Zélie', 0), ('Alphonse', 50), ('Alphonse', 100)]
Le Tim Sort⚓︎
L'algorithme de tri utilisé par Python est le Tim Sort créé par Tim Peters en 2002.
Pas que Python !
Le Tim Sort est aussi utilisé dans les langages et plateformes suivants : Java SE 7, Android, GNU Octave, Swift et Rust.
Cet algorithme part de l'hypothèse que, dans la majorité des cas, les données à trier comprennent des plages déjà triées.
On peut imaginer la situation d'un magasin qui, jour après jour, ajoute ses ventes quotidiennes à un tableau préexistant et le trie. Chaque matin, le tableau initial est trié, seules les valeurs du jour sont à trier.
Dans ce cadre, le Tim Sort profite des qualités de deux tris étudiés dans ce cours :
- le tri par insertion est très efficace dans le cas de petits tableaux presque triés mais pas dans le cas de grands tableaux,
- le tri fusion est très efficace dans le cas de grands tableaux mais pas pour de petits tableaux.
L'idée principale de ce tri est donc la suivante :
- parcourir le tableau et y repérer des plages déjà triées ou presque,
- si besoin, trier ces plages à l'aide du tri par insertion,
- fusionner ces plages à l'aide de l'opération de fusion du tri fusion.
Remarque
Le fonctionnement réel de l'algorithme est plus technique que cette simple présentation.
L'un des intérêts de cette démarche est d'éviter un certain nombre d'étapes de partage lors du tri fusion. Si l'on considère par exemple que les plages recherchées contiennent \(32 = 2^5\) éléments, alors on économise \(5\) étapes de partage.