Tri de tableaux

Introduction

Nous allons voir comment python tri des tableaux avec la méthode sort() et la fonction sorted(). La méthode sort() tri le tableau sur lequel elle est appliquée et modifie ce tableau alors que la fonction sorted() renvoie un nouveau tableau trié :

>>> tab = [5,65,2,1,63,4,8,420]
>>> sorted(tab)
[1, 2, 4, 5, 8, 63, 65, 420]
>>> tab
[5, 65, 2, 1, 63, 4, 8, 420] // Ici tab n’a pas été modifié
>>> tab.sort()
>>> tab
[1, 2, 4, 5, 8, 63, 65, 420] // tab est maintenant trié

sort() et sorted() ont à peu près le même fonctionnement. Nous utiliserons sorted() pour avoir une notation plus simple.

Tableau d’entiers

Lorsqu’on trie un tableau d’entiers, le fonctionnement est assez classique : les entiers sont placés par ordre croissant.

1) Donnez le résultat de l’instruction suivante :

>>> sorted([7,-6,12,76,0])

Remarque : tout cela fonctionne également avec les flottants.

Tableau de chaînes de caractères

Python trie les chaînes de caractère par ordre lexicographique. Pour les chaînes en minuscule, tout va bien :

2) Donnez le résultat de l’instruction suivante :

>>> sorted(['pomme', 'poire', 'banane', 'kiwi'])

Pour les chaînes avec des majuscules, ça se complique. L’ordre lexicographique utilisé par Python utilise le code unicode des caractères :

3) Donnez le résultat de l’instruction suivante :

>>> sorted(['Pomme', 'poire', 'banane', 'kiwi'])

« Pomme » se place en premier car le code unicode de 'P' (80) est plus petit que celui de 'b' (98). (rappel :la fonction ord() permet d’obtenir le code unicode d’un caractère)

Pour obtenir l’ordre alphabétique, il faut d’abord activer votre locale :

>>> import locale
>>> locale.setlocale(locale.LC_ALL, "")

Puis utiliser sorted() avec l’option key=locale.strxfrm.

4) Donnez le résultat de l’instruction suivante :

>>> sorted(['Pomme', 'poire', 'banane', 'kiwi'], key=locale.strxfrm)

Cas particulier des entiers dans les chaînes de caractères

Attention une chaîne de caractère contenant un entier reste triée comme une chaîne de caractère.

5) Donner le résultat de l’instruction suivante :

>>> sorted(['12', '2', '0', '102'])

Ce comportement est normal car il respecte l’ordre lexicographique.

Inverser l’ordre de tri

Une option permet d’inverser l’ordre de tri : reverse = True.

6) Donnez le résultat de l’instruction suivante :

>>> sorted([7,-6,12,76,0], reverse = True)

Questions (sans tester en Python si possible)

7) Donnez le résultat de sorted(['19', 'vacances', 'voyage', '9']).

8) Donnez le résultat de sorted(['A', 'b', 'Ba', 'aB', 'aa']).

Pour aller plus loin

Si vous voulez approfondir le sujet, voici une page assez complète sur le sujet du tri des tableaux : http://pascal.ortiz.free.fr/contents/python/tri/tri.html

Vous pouvez également faire les activités sur les données structurées de France-ioi