Tris

Trier un tableau consiste à ordonner ses éléments par ordre croissant (ou décroissant) selon un critère.

Les fonctions de tri sont disponibles dans les bibliothèques standard des langages de programmation. Ce cours explique comment utiliser ces fonctions ; les cours suivants présentent à des fins pédagogiques différents algorithmes (il en existe de nombreux).

Le tri d’un tableau contenant des éléments simples comme des nombres est facile : il suffit de comparer les valeurs des éléments.

Dans le cas des chaînes de caractère, la comparaison est alphabétique (plus exactement selon la valeur ASCII des caractères) ; ainsi “félicitations" < "super” (ce n’est pas la longueur qui importe).

Lorsque les éléments sont d’un type plus complexe (par exemple un dictionnaire ou une classe), il faut définir un critère de comparaison : Par exemple, pour des Objets de la classe Commande avec comme attributs client et date, le critère de comparaison pourrait être en priorité la date puis le client en cas d’égalité..

La méthode sort

La méthode sort s’applique à un objet de la classe List (un tableau) :

valeurs = [ 3, 1, 2, 5, 4]
valeurs.sort()
print(valeurs)

Cette fonction modifie le tableau d’origine (le (dés)ordre initial est perdu). Pour conserver l’original, il faut utiliser la fonction sorted qui prend en paramètre d’entrée l’objet à trier et renvoie une copie triée :

valeursNonTriees = [ 3, 1, 2, 5, 4]
valeursTriees = sorted(valeursTriees)
print(valeursNonTriees)
print(valeursTriees)

Le principe est le même que pour le tri de nombres :

valeurs = ["super", "bravo", "félicitations"]
valeurs.sort()                              #modifie l'ordre des éléments
print(valeurs)

valeursNonTriees = [ "Tehau", "Revanui", "Ilam"]
valeursTriees = sorted(valeursNonTriees)    #valeursNonTriees n'est pas modifié
print(valeursNonTriees)
print(valeursTriees)

Pour des objets plus complexes, la méthode sort ou la fonction sorted ont besoin de savoir comparer les objets ; deux approches sont possibles :

• définir une méthode de comparaison au niveau de la classe :

from __future__ import annotations
import datetime

class Commande:
    def __init__(self, date: datetime.date, client: str):
        self.date = date
        self.client = client
    
    def __repr__(self) -> str: #__str__
        return self.client + " " + self.date.isoformat()
    
    def __lt__(self, other: Commande) -> bool: #renvoie True si self < other
        return self.date < other.date or \
               self.date == other.date and self.client <= other.client

if __name__ == "__main__":
    commandes = []
    commandes.append(Commande(datetime.date(2026, 2, 2), "Sabord Eric"))
    commandes.append(Commande(datetime.date(2026, 2, 1), "Nui Reva"))
    commandes.append(Commande(datetime.date(2026, 2, 2), "Miti Tehau"))
    
    print(commandes)    #non trié
    commandes.sort()
    print(commandes)    #trié

• passer en paramètre key à sort / sorted ; key doit être une fonction (souvent anonyme — cf lambda) qui prend en paramètre l’objet et renvoie une valeur comparable (souvent une chaîne de caractères) :

from __future__ import annotations
#from typing import Any #n'importe quel type
import datetime

class Personne:
    def __init__(self, nom: str, prenom: str):
        self.nom = nom
        self.prenom = prenom
    
    def __repr__(self) -> str: #__str__
        return self.nom + " " + self.prenom

#def keyFunc(obj: Any) -> str:
#   return str(obj)

if __name__ == "__main__":
    personnes = []
    personnes.append(Personne("Sabord", "Eric"))
    personnes.append(Personne("Nui", "Reva"))
    personnes.append(Personne("Miti", "Tehau"))
    
    print(personnes)
    #personnes.sort(key = keyFunc) #souvent remplacé par expression lambda
    personnes.sort(key = lambda p: str(p))
    print(personnes)

Certains langages utilisent une fonction de comparaison int compFunction(objet1, objet2) qui renvoie :

• -1 si objet1 < objet2
• 0 si objet1 == objet2
• et 1 si objet1 > objet2

Exemple (Java) :

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Personne {
    String nom;
    String prenom;
    Personne(String nom, String prenom) {
        this.nom = nom;
        this.prenom = prenom;
    }
    public String toString() {
        return nom + " " + prenom;
    }
}

public class Main {
    public static void main(String[] args) {
        List<Personne> personnes = new ArrayList<>();
        personnes.add(new Personne("Sabord", "Eric"));
        personnes.add(new Personne("Nui", "Reva"));
        personnes.add(new Personne("Miti", "Tehau"));

        System.out.println(personnes); //non trié
        
        Collections.sort(personnes, (o1, o2) -> { //fonction anonyme
            int c = o1.nom.compareTo(o2.nom); //-1 (o1.nom < o2.nom), 0 ou 1
            return c == 0 ? o1.prenom.compareTo(o2.prenom) : c;
                //la comparaison des prénoms n'a lieu que si les noms sont égaux
        });

        System.out.println(personnes); //trié
    }
}

Pour inverser l’ordre des éléments, il suffit de permuter le premier et le dernier, le deuxième et l’avant dernier et ainsi de suite jusqu’au milieu :

from typing import List

def inverse(tab : List[float]) -> List[float]:
    """
    inverse l'ordre des éléments du tableau
    @param tab le tableau de valeurs, en entrée-sortie (par adresse)
    @return le tableau inversé (pour doctests)
    >>> inverse([])
    []
    >>> inverse([2, 1, 3])
    [3, 1, 2]
    >>> inverse([4, 3, 2, 1])
    [1, 2, 3, 4]
    """
    
    n = len(tab)
    for i in range(n // 2):
        tab[i], tab[n-1-i] = tab[n-1-i], tab[i] #permutation python
    
    return tab


if __name__ == "__main__":
    import doctest; doctest.testmod()
    t1 = [1,3,2,5,4]
    inverse(t1)
    print(t1)

Cet algorithme effectue n // 2 permutations, soit une complexité en O(n).

Remarque : il est inutile de renvoyer le tableau (car il est modifié par la fonction — cf passage en entrée-sortie), mais c’est plus pratique pour écrire des doctests.