Aller au contenu

Trier suivant un critère☘

Dans la page précédente, nous avons trier suivant un critère "naturel": l'ordre usuel sur les nombres.

Mais il est tout à fait possible de trier suivant d'autres critères.

Exemple☘

On dispose d'une liste d'entiers naturels:

L = [ 12, 67, 32, 434, 531, 10, 100]

On aimerait les ranger dans l'ordre croissant du chiffre des unités. Pour cela, il suffit de préciser une clef avec la syntaxe suivante:

def unite(entier):
    """
    entier est un entier naturel.
    renvoie le chiffre des unités de entier (en base dix)
    """
    return entier%10

L = [ 12, 67, 32, 434, 531, 10, 100]
L.sort(key=unite)

Après ces lignes, la valeur de L est [10, 100, 531, 12, 32, 434, 67].

Que s'est-il passé ?

Python a associé à chaque élément de la liste son image par la fonction unite puis a rangé les éléments de la liste suivant l'ordre croissant de ces images par la fonction unite.

Exercice☘

Trier la liste précédente suivant l'ordre décroissant du chiffre des unités.

Solution

Il suffit d'utiliser reverse=True.

def unite(entier):
    """
    entier est un entier naturel.
    renvoie le chiffre des unités de entier (en base dix)
    """
    return entier%10

    L = [ 12, 67, 32, 434, 531, 10, 100]
    L.sort(key=unite, reverse=True)

Tri suivant le chiffre des dizaines☘

Ecrire une fonction prenant en paramètre une liste d'entiers naturels et renvoyant en sortie une liste triée suivant l'ordre croissant du chiffre des dizaines (sans effet de bord sur la liste donnée en argument: elle doit rester intacte).

Chiffre des dizaines

Avec de l'arithmétique élémentaire:

def dizaine(entier):
    """
    entier est un entier naturel.
    renvoie le chiffre des dizaines de entier (en base dix)
    """
    nb_dizaines = entier//10 # le nombre de dizaines
    chiffre_dizaine = nb_dizaines%10 # le chiffre des dizaines
    return chiffre_dizaine

Avec une astuce du langage Python:

def dizaine(entier):
    """
    entier est un entier naturel.
    renvoie le chiffre des dizaines de entier (en base dix)
    """
    return  int(str(entier)[-2])

On a d'abord tranformé l'entier en chaîne avec str(entier) puis récupéré l'avant dernier caractère avec str(entier)[-2] et enfin transformé ce caractère en entier avec int.

le tri

Comme on veut éviter les effets de bord sur la liste, on utilisera sorted plutôt que sort.

def dizaine(entier):
    """
    entier est un entier naturel.
    renvoie le chiffre des dizaines de entier (en base dix)
    """
    nb_dizaines = entier//10 # le nombre de dizaines
    chiffre_dizaine = nb_dizaines%10 # le chiffre des dizaines
    return chiffre_dizaine

def tri_suivant_dizaine(tab):
    """
    tab est une liste d'entiers naturels
    renvoie la liste triée suivant l'ordre croissant du chiffre des dizaines
    """
    return sorted(tab, key=dizaine)

Exemple d'appel:

>>> L = [ 12, 67, 32, 434, 531, 10, 100]
>>> tri_suivant_dizaine(L)
[100, 12, 10, 32, 434, 531, 67]

Tri stable☘

Le tri en langage python est dit stable, ce qui signifie que deux éléments indiscernables par le critère de tri choisi sont laissés dans le même ordre que la liste de départ.

Exemple.

Dans l'illustration ci-dessus, nous avons trié la liste L = [ 12, 67, 32, 434, 531, 10, 100] suivant l'ordre croissant du chiffre des dizaines.
Dans le résultat [100, 12, 10, 32, 434, 531, 67], nous constatons que le nombre 12 est situé avant le nombre 10. Pourquoi ?

Solution

Dans la liste initiale L, 12 est situé avant 10. Comme 12 et 10 sont indiscernables suivant le critère choisi (parce qu'ils ont le même chiffre des dizaines), Python les laisse dans la liste finale dans le même ordre que dans la liste initiale (c'est la propriété de stabilité du tri python).

Vous pouvez observer que le résultat du tri de M = [10, 67, 32, 434, 531, 12, 100] (où l'on a placé 10 avant 12) suivant le même critère (ordre croissant du chiffre des dizaines) donnera une liste où cette fois 10 est avant 12.

Question. Si vous triez maintenant N = [34, 23, 10, 12, 10] suivant le même critère, qu'obtiendrez-vous ? (essayez de répondre avant de tester).

Solution

On obtient [10, 12, 10, 23, 34]. 10 et 12 étant indiscernables suivant le critère choisi, on peut obtenir un 10 avant 12 et un 10 après, ils sont conservés dans l'ordre de la liste initiale.

Tri suivant le nombre de chiffres pairs.☘

Trier une liste d'entiers naturels suivant le nombre de chiffres pairs constituant chaque entier.

Par exemple, 214 sera placé après 113 puisque 214 possède deux chiffres pairs tandis que 113 en possède 0. Par contre 124 et 216 sont indiscernables par ce critère (et resteront dans la liste finale dans l'ordre de leur apparition dans la liste initiale).

Nombre de chiffres pairs

On commence par définir une fonction renvoyant le nombre de chiffres pairs d'un entier.

  • Avec un peu d'arithmétique. On récupère les chiffres avec l'algorithme des divisions en cascade vu plus tôt dans l'année (à connaître parfaitement, rappelons le) et avec un compteur, on détermine le nombre de chiffres pairs.
def nombre_de_chiffres_pairs(entier):
    """
    entier est un entier naturel.
    renvoie le nombre de chiffres pairs de l'entier
    """

    # on traite le cas de l'entier 0 à part:
    if entier == 0: return 1


    # cas des entiers > 0:
    # initialisation du compteur de chiffres pairs:
    compteur = 0

    # récupération des chiffres par divisions en cascade:
    while entier != 0:
        unite = entier%10
        if unite%2 == 0: 
            compteur += 1
        entier = entier//10

    return  compteur
  • Avec l'astuce python déjà vue plus haut:
def nombre_de_chiffres_pairs(entier):
    """
    entier est un entier naturel.
    renvoie le nombre de chiffres pairs de l'entier
    """
    return len([c for c in str(entier) if int(c)%2 == 0])
le tri
  • Avec sort:
def tri_suivant_nb_chiffres_pairs(tab):
    """
    tab est une liste d'entiers naturels
    trie la liste   suivant l'ordre croissant du 
    nombre de chiffres pairs de chaque entier 
    """
    tab.sort(key=nombre_de_chiffres_pairs)
  • Avec sorted:
def tri_suivant_nb_chiffres_pairs(tab):
    """
    tab est une liste d'entiers naturels
    renvoie une liste, ayant mêmes éléments que tab, 
    triée suivant l'ordre croissant du 
    nombre de chiffres pairs de chaque entier.
    """
    return sorted(tab, key=nombre_de_chiffres_pairs)

Remarque. Observez la différence dans le choix des mots de la chaîne de documentation. Avec sorted, la fonction renvoie une liste triée. Avec sort, la fonction trie la liste.

Pairs d'abord☘

On dispose d'une liste d'entiers naturels. On veut trier cette liste en plaçant les entiers pairs en premier puis les entiers impairs.

Exemple.

Pour la liste L = [3, 22, 5, 6, 10, 7, 5, 4] le résultat sera [22, 6, 10, 4, 3, 5, 7, 5].

Programmez cela.

fonction critère

Quelle fonction définir pour le critère ? On définit une fonction qui associe à chaque entier pair un nombre (par exemple 0) et qui à chaque entier impair associe un autre nombre, plus grand que celui qui est associé aux pairs (par exemple 1).

Le reste modulo 2 convient par exemple:

def reste_modulo2(n):
    """
    n est un entier
    renvoie le reste modulo 2 de l'entier n
    """
    return n%2

Mais on pourrait par exemple utiliser:

def critere(n):
    """
    n est un entier
    renvoie le reste modulo 2 de l'entier n
    """
    if n%2 == 0:
        return 42
    else:
        return 666
le tri
  • Avec sort :
def pairs_dabord(tab):
    """
    tab est une liste d'entiers
    trie tab en plaçant les pairs à l'avant
    """
    tab.sort(key=reste_modulo2)
  • Avec sorted:
def pairs_dabord(tab):
    """ 
    tab est une liste d'entiers
    renvoie une liste, de mêmes éléments que tab, où les pairs sont placés à l'avant.
    """
    return sorted(tab, key=reste_modulo2)