I. C'est quoi un tri ?

Trier une liste ou une collection d'éléments, ça consiste à les réordonner pour qu'ils soient en ordre croissant ou décroissant.

On peut écrire une condition nécessaire et suffisante pour qu'une liste soit triée dans l'ordre croissant :

On va en général définir des fonctions de tri, qui prennent en argument une liste et la trient. On distingue deux sortes de fonctions :

• les tris en place (in-place) qui modifient la liste originale en réordonnant les éléments, afin qu'elle soit triée ;
• les tris qui renvoient une nouvelle liste, triée, qui contient exactement les mêmes éléments que la liste originale.

II. Pourquoi trier ?

Raisons de présentation : dans une table, une liste, ou d'autres données destinées à un affichage, il est souvent utile de trier les éléments. Imaginez un dictionnaire où les mots sont dans un ordre aléatoire !

Raisons informatiques : en informatique, on se retrouve souvent dans une situation où il est plus rapide de trier une liste avant de l'utiliser.

• Recherche d'éléments : à la manière d'un dictionnaire, il est beaucoup plus rapide de chercher un élément dans une liste triée, que dans une liste dans le désordre.
• Ordonnancement.
• Et bien plus...

III. Comment trier ?

a) Le tri à bulle

Idée : à chaque étape, on compare deux éléments adjacents. S'ils sont dans le bon ordre, on les laisse. Sinon, on les échange.

def tri_bulle(L):
    """Trie la liste L "in place" avec l'algorithme du tri à bulle"""
    for i in range(len(L) - 1):
        for j in range(len(L) - 1 - i):
            if L[j] > L[j+1]:
                L[j], L[j+1] = L[j+1], L[j]

Par exemple :

L = [4, 1, 2, 8, 3, 1, 9]
tri_bulle(L)
print(L)

La fonction animer_tri(fonction_de_tri, liste) permet de voir le déroulement d'un tri : chaque élément est une barre, et les éléments comparés sont en rouge. Essayez avec d'autres listes !

b) Tri par sélection

Idée : on prend d'abord le minimum de la liste, et on le place au début. Puis on répète sur le reste de la liste.

def tri_selection(L):
    """Trie la liste L "in place" avec l'algorithme du tri par sélection"""
    for i in range(len(L) - 1):
        el_min = L[i]
        for j in range(i + 1, len(L)):
            if L[j] < el_min:
                el_min, L[j] = L[j], el_min
        L[i] = el_min

c) Tri par insertion

Idée : on insère, un par un, chaque élément à sa place dans une nouvelle liste triée.

def insere(L, x):
    """Insère l'élément x à sa place dans la liste triée L in-place"""
    L.append(x)
    for i in range(len(L) - 1, 0, -1):
        if L[i] < L[i-1]:
            L[i], L[i-1] = L[i-1], L[i]
        else: 
            break

L = [1, 3, 5, 8]
insere(L, 4)
print(L)

def tri_insertion(L):
    """renvoie une nouvelle liste contenant les éléments de L, triée par insertion."""
    L_triee = []
    for x in L:
        insere(L_triee, x)
    return L_triee

print(tri_insertion([4, 1, 2, 8, 3, 1, 9]))

d) Tri par insertion en place

On va faire une fonction insere qui prend en argument une liste L dont les k premiers éléments (d'indices 0, 1, ..., k-1) sont triés dans l'ordre croissant, un indice k et un élément x.

La fonction insère alors l'élément x dans les k premiers éléments de L, en écrasant l'élément d'indice k.

def insere(L, k, x):
    #boucle sur (k-1), (k-2), ..., 1, 0
    for i in range(k-1, -1, -1):
        #Si x est plus grand que l'élément actuel, on le range juste après, et on s'arrête
        if x > L[i]:
            L[i+1] = x
            return
        #sinon, on décale l'élément d'un cran pour laisser de la place à x
        else:
            L[i+1] = L[i]
    #si on arrive au bout, c'est que x est le plus petit élément
    L[0] = x

L = [1, 3, 5, 8, 4]   # les 4 premiers éléments sont triés
insere(L, 4, 4)       # on insère l'élément d'indice 4 parmi eux
print(L)

On utilise ensuite cette fonction pour réaliser le tri :

def tri_insertion(L):
    """Trie L en ordre croissant, par insertion, in-place"""
    #On insère le (k+1)ème élément dans les k premiers.
    for k in range(len(L)):
        insere(L, k, L[k])

e) Propriétés

f) Caractéristiques d'un tri

La stabilité compte quand on trie des données selon un critère : par exemple, des élèves déjà rangés par ordre alphabétique, que l'on trie par note. Avec un tri stable, les élèves qui ont la même note restent dans l'ordre alphabétique.

def tri_insertion_cle(L, cle):
    """Tri par insertion en place, selon la valeur de cle(x) pour chaque élément x."""
    for i in range(1, len(L)):
        x = L[i]
        j = i
        while j > 0 and cle(L[j - 1]) > cle(x):   # > strict : on ne dépasse pas un élément égal
            L[j] = L[j - 1]
            j -= 1
        L[j] = x

eleves = [("Alice", 14), ("Bob", 12), ("Chloé", 14), ("David", 12), ("Emma", 16)]
tri_insertion_cle(eleves, lambda e: e[1])
eleves

Bob est toujours avant David, et Alice avant Chloé : le tri par insertion est stable.

g) Tri par comptage

Si les éléments à trier sont des entiers entre et (des notes entre 0 et 20, par exemple), on peut trier sans aucune comparaison : on compte combien de fois apparaît chaque valeur, puis on reconstruit la liste triée.

def tri_comptage(L, m):
    """Trie une liste d'entiers compris entre 0 et m - 1."""
    compte = [0] * m
    for x in L:
        compte[x] += 1
    resultat = []
    for v in range(m):
        for k in range(compte[v]):
            resultat.append(v)
    return resultat

tri_comptage([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5], 10)

La complexité est en : on parcourt la liste une fois, puis les valeurs possibles. Quand est petit devant , c'est plus rapide que les tris comparatifs ! En revanche, il faut connaître l'intervalle des valeurs, et il utilise une liste supplémentaire de taille .

Exercices

def est_triee(L):
    for i in range(len(L) - 1):
        if L[i] > L[i + 1]:
            return False
    return True

def tri_selection_decroissant(L):
    for i in range(len(L)):
        i_max = i
        for j in range(i + 1, len(L)):
            if L[j] > L[i_max]:
                i_max = j
        L[i], L[i_max] = L[i_max], L[i]