Tris de listes

Complément - niveau basique¶

Python fournit une méthode standard pour trier une liste, qui s’appelle, sans grande surprise, sort.

La méthode sort¶

Voyons comment se comporte sort sur un exemple simple :

liste = [8, 7, 4, 3, 2, 9, 1, 5, 6]
print('avant tri', liste)
liste.sort()
print('apres tri', liste)

avant tri [8, 7, 4, 3, 2, 9, 1, 5, 6]
apres tri [1, 2, 3, 4, 5, 6, 7, 8, 9]

On retrouve ici, avec l’instruction liste.sort() un cas d’appel de méthode (ici sort) sur un objet (ici liste), comme on l’avait vu dans la vidéo.

La première chose à remarquer est que la liste d’entrée a été modifiée, on dit “en place”, ou encore “par effet de bord”. Voyons cela sous pythontutor :

%load_ext ipythontutor

%%ipythontutor height=200 ratio=0.8
liste = [3, 2, 9, 1]
liste.sort()

On aurait pu imaginer que la liste d’entrée soit restée inchangée, et que la méthode de tri renvoie une copie triée de la liste, ce n’est pas le choix qui a été fait, cela permet d’économiser des allocations mémoire autant que possible et d’accélérer sensiblement le tri.

La fonction sorted¶

Si vous avez besoin de faire le tri sur une copie de votre liste, la fonction sorted vous permet de le faire :

%%ipythontutor height=200 ratio=0.8
liste1 = [3, 2, 9, 1]
liste2 = sorted(liste1)

Tri décroissant¶

Revenons à la méthode sort et aux tris en place. Par défaut la liste est triée par ordre croissant, si au contraire vous voulez l’ordre décroissant, faites comme ceci :

liste = [8, 7, 4, 3, 2, 9, 1, 5, 6]
print('avant tri', liste)
liste.sort(reverse=True)
print('apres tri décroissant', liste)

avant tri [8, 7, 4, 3, 2, 9, 1, 5, 6]
apres tri décroissant [9, 8, 7, 6, 5, 4, 3, 2, 1]

Nous n’avons pas encore vu à quoi correspond cette formule reverse=True dans l’appel à la méthode - ceci sera approfondi dans le chapitre sur les appels de fonction - mais dans l’immédiat vous pouvez utiliser cette technique telle quelle.

Chaînes de caractères¶

Cette technique fonctionne très bien sur tous les types numériques (enfin, à l’exception des complexes ; en guise d’exercice, pourquoi ?), ainsi que sur les chaînes de caractères :

liste = ['spam', 'egg', 'bacon', 'beef']
liste.sort()
print('après tri', liste)

The history saving thread hit an unexpected error (OperationalError('attempt to write a readonly database')).History will not be written to the database.après tri ['bacon', 'beef', 'egg', 'spam']

Comme on s’y attend, il s’agit cette fois d’un tri lexicographique, dérivé de l’ordre sur les caractères. Autrement dit, c’est l’ordre du dictionnaire. Il faut souligner toutefois, pour les personnes n’ayant jamais été exposées à l’informatique, que cet ordre, quoique déterministe, est arbitraire en dehors des lettres de l’alphabet.

Ainsi par exemple :

# deux caractères minuscules se comparent
# comme on s'y attend
'a' < 'z'

Bon, mais par contre :

# si l'un est en minuscule et l'autre en majuscule,
# ce n'est plus le cas
'Z' < 'a'

Ce qui à son tour explique ceci :

# la conséquence de 'Z' < 'a', c'est que
liste = ['abc', 'Zoo']
liste.sort()
print(liste)

['Zoo', 'abc']

Et lorsque les chaînes contiennent des espaces ou autres ponctuations, le résultat du tri peut paraître surprenant :

# attention ici notre premiere chaîne commence par une espace
# et le caractère 'Espace' est plus petit
# que tous les autres caractères imprimables
liste = [' zoo', 'ane']
liste.sort()
print(liste)

[' zoo', 'ane']

À suivre¶

Il est possible de définir soi-même le critère à utiliser pour trier une liste, et nous verrons cela bientôt, une fois que nous aurons introduit la notion de fonction.