4- Tris
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
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.
Loading editor...
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 :
Loading editor...
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 !
Quelle est la complexité du tri à bulle ? Avec n = len(L).
Pour chaque valeur de i, la boucle interne fait n - 1 - i itérations en
Réfléchissez à d'autres manières de trier une liste. Comment procédez-vous, naturellement, si on vous demande de trier la liste [4, 1, 2, 8, 3, 1, 9] ?
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.
Loading editor...
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_minQuelle est la complexité du tri par sélection ? Avec n = len(L).
Comme pour le tri à bulle, la boucle interne fait i : la complexité est en
c) Tri par insertion
Idée : on insère, un par un, chaque élément à sa place dans une nouvelle liste triée.
Loading editor...
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:
breakLoading editor...
L = [1, 3, 5, 8] insere(L, 4) print(L)
Quelle est la complexité de la fonction insere ? Avec n = len(L).
L'ajout L.append(x) est en temps constant. La boucle fait ensuite au plus
Loading editor...
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_trieeLoading editor...
print(tri_insertion([4, 1, 2, 8, 3, 1, 9]))
Quelle est la complexité de la fonction tri_insertion ? Avec n = len(L).
On appelle n fois la fonction insere, sur une liste de taille au plus n, donc en
Pouvez-vous écrire une version in-place du tri par insertion ?
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.
Loading editor...
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] = xLoading editor...
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 :
Loading editor...
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])Comparez le nombre de comparaisons des différents tris sur une liste déjà triée, par exemple [1, 2, 3, 4, 5, 6, 7, 8, 9], puis sur une liste triée dans l'ordre inverse.
e) Propriétés
Que se passe-t-il dans chacun des algorithmes si la liste est déjà triée ? Si elle est "presque" triée ?
Si on regarde la fonction du tri par insertion en place, en particulier l'insertion, elle ne fait qu'une seule itération si l'élément est déjà à sa place. Donc tout se passe comme si la liste était simplement parcourue une fois, pour une complexité dans le meilleur cas en
f) Caractéristiques d'un tri
Définitions
Un algorithme de tri est :
- en place s'il modifie directement la liste, sans utiliser une autre liste de même taille ;
- stable s'il ne change pas l'ordre relatif des éléments égaux ;
- comparatif s'il n'accède aux éléments qu'en les comparant deux à deux.
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.
Loading editor...
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])
elevesBob est toujours avant David, et Alice avant Chloé : le tri par insertion est stable.
| Tri | En place | Stable | Comparatif | Complexité (pire cas) |
|---|---|---|---|---|
| À bulles | oui | oui | oui | |
| Par sélection | oui | non | oui | |
| Par insertion | oui | oui | oui | |
| Fusion (voir h) | non | oui | oui | |
| Par comptage | non | oui | non |
Montrer que le tri par sélection n'est pas stable, en trouvant une liste de couples pour laquelle il change l'ordre de deux éléments égaux.
Avec [(2, "a"), (2, "b"), (1, "c")] triée selon le premier élément : le minimum (1, "c") est échangé avec le premier élément (2, "a"), ce qui donne [(1, "c"), (2, "b"), (2, "a")] : (2, "b") est passé devant (2, "a").
g) Tri par comptage
Si les éléments à trier sont des entiers entre
Loading editor...
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
h) Tri fusion
Les tris vus jusqu'ici sont en
- Couper la liste à trier en deux parts égales.
- Trier chaque partie séparément.
- Fusionner les deux parties triées.
On va s'intéresser à ces étapes une par une.
Couper la liste en deux
Loading editor...
def partition(L):
"""Prend une liste en argument, et renvoie deux nouvelles listes contenant chacune la moitié des éléments (avec un de plus dans la deuxième si nécessaire)"""
n = len(L)
milieu = n//2
moitie_1 = L[0:milieu]
moitie_2 = L[milieu:n]
return (moitie_1, moitie_2)Loading editor...
partition([4, 1, 2, 8, 3, 1, 9])
Trier chaque partie séparément
On va trier les parties en utilisant... le tri fusion lui-même !
Fonctions récursives
Une fonction peut s'appeler elle-même : on dit qu'elle est récursive (on y reviendra en détail dans le chapitre sur la récursivité). Pour ne pas boucler à l'infini, chaque appel doit se faire sur une entrée plus petite, jusqu'à un cas de base qu'on sait traiter directement : ici, une liste de 0 ou 1 élément, qui est déjà triée.
Fusionner deux listes triées
Idée : on aimerait placer tous les éléments contenus dans les deux listes moitie_1 et moitie_2 dans une nouvelle liste resultat. On va prendre les éléments un par un !
Loading editor...
def fusion(L1, L2):
"""fusionne deux listes triées en ordre croissant en une seule liste triée également."""
resultat = []
i1 = 0
i2 = 0
#On transfère les éléments tant qu'on n'a terminé aucune des deux listes
while i1 < len(L1) and i2 < len(L2):
if L1[i1] <= L2[i2]: # <= : en cas d'égalité, on prend d'abord l'élément de L1 (le tri est stable)
resultat.append(L1[i1])
i1 += 1
else:
resultat.append(L2[i2])
i2 += 1
#Une fois qu'une liste est terminée, on peut transférer tout ce qu'il reste dans l'autre !
reste1 = L1[i1:]
reste2 = L2[i2:]
resultat = resultat + reste1 + reste2
#Un seul des deux restes sera non vide (grâce à la condition du "while")
return resultatLoading editor...
fusion([1, 4, 8, 9], [1, 2, 3, 10])
Pour visualiser la fusion, voici la même fonction, qui note chaque étape pour l'animer avec animer_liste. On affiche L1, puis L2, puis le résultat en cours de construction ; les deux éléments comparés sont en rouge :
En combinant les trois
Loading editor...
def tri_fusion(L):
if len(L) <= 1:
return L[:]
#partition
moitie_1, moitie_2 = partition(L)
#tri récursif
moitie_1 = tri_fusion(moitie_1)
moitie_2 = tri_fusion(moitie_2)
#fusion
return fusion(moitie_1, moitie_2)Complexité du tri fusion
La fusion de deux listes, de longueur totale resultat. En coupant en deux à chaque fois, on fait environ
En revanche, il n'est pas en place : il crée de nouvelles listes.
Exercices
Exercice 1
Écrire une fonction est_triee(L) qui renvoie True si la liste L est triée dans l'ordre croissant, False sinon. Quelle est sa complexité ?
Loading editor...
def est_triee(L):
for i in range(len(L) - 1):
if L[i] > L[i + 1]:
return False
return True Complexité
Exercice 2
Adapter le tri par sélection pour trier une liste dans l'ordre décroissant.
Loading editor...
Il suffit de chercher le maximum au lieu du minimum :
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]Exercice 3
On veut trier une liste de 1 000 000 de notes (des entiers entre 0 et 20). Quel tri choisir ? Écrire l'appel correspondant.
Le tri par comptage, en tri_comptage(notes, 21).