On suppose qu'on a une liste de nombres (ou d'éléments qu'il est possible d'ordonner, par exemple des chaînes de caractères) et on cherche comment on peut les trier dans l'ordre croissant. Dans ce chapitre on prendra pour exemple des cartes numérotées.
Les deux algorithmes au programme de première consistent à construire une nouvelle liste à partir de l'ancienne, tout en vidant l'ancienne liste, et en s'assurant que pendant toute la construction, la nouvelle liste est (et reste) triée.
def tri_selection(liste_à_trier:list) -> list: liste_triée = [] while not vide(liste_à_trier): carte = minimum(liste_à_trier) enlever(liste_à_trier,carte) ajouter(liste_triée,carte) return liste_triée
def vide(liste:list) -> bool: return len(liste)==0
Voir le chapitre sur les listes en Python
def enlever(liste:list,elt:float): liste.remove(elt)
On rajoute la carte à la fin de la nouvelle liste, cela
se fait par +=
ou append
:
def ajouter(liste:list,elt:float): liste.append(elt)
À chaque étape, on retire une carte du jeu restant à trier : le nombre de cartes qui reste à trier est un variant de la boucle, c'est-à-dire une quantité positive qui décroît (ici, d'une unité à la fois) à chaque itération.
L'existence d'un variant prouve que l'algorithme se termine en un temps fini.
À chaque étape, on retire la plus petite carte du jeu non trié. Toutes les cartes qui sont déjà triées sont donc encore plus petites que celle-ci (puisqu'on les a déjà retirées auparavant). En plaçant la nouvelle carte à la fin de la liste triée, celle-ci reste triée dans l'ordre croissant. La phrase « la liste est triée » qui est vraie en permanence, est un invariant de la boucle. Comme il est vrai dès le départ (une liste vide est triée) et reste vrai, il est vrai à la fin : c'est une postcondition respectée.
L'algorithme de tri par sélection est correct : il trie bel et bien la liste comme il est censé le faire.
On a vu que pour trouver le minimum de n
éléments, il faut effectuer n
comparaisons.
Par exemple pour 8 cartes,
Cela fait 7+6+5+4+3+2+1+0 = 28 comparaisons. Plus
généralement on effectue n
(n
-1)/2
comparaisons pour une liste de taille initiale n
.
On dit que l'algorithme de tri par sélection est
de coût quadratique.
L'algorithme de tri par insertion est plus rapide que le précédent pour la partie extraction, puisqu'on n'a plus besoin de chercher le minimum. Par contre pour garantir que la nouvelle liste est triée, il faut chercher à quel endroit insérer la carte extraite. C'est assez rapide puisque justement la nouvelle liste est triée, mais est-ce suffisamment rapide pour avoir un coût moins que quadratique ?
def ajouter(liste:list,elt:float): position = 0 for position in range(len(liste)): if liste[position]>elt: break liste.insert(position,elt)
L'instruction break
a pour effet de quitter la
boucle dès qu'on a trouvé où insérer l'élément.
Pour simplifier un peu le script Python, on choisit de
retirer non pas la première carte, mais la dernière. Pour
cela on utilise la fonction pop()
:
def tri_insertion(liste_à_trier:list) -> list: liste_triée = [float('inf')] while not vide(liste_à_trier): carte = liste_à_trier.pop() ajouter(liste_triée,carte) liste_triée.pop() return liste_triée
La boucle n'est jamais parcourue si la liste triée est vide.
Par conséquent on choisit de l'initialiser, non à
[]
mais à [∞]
. Une fois
le tri effectué, on a donc une liste triée du type
[1,1,2,3,5,∞]
dont il reste à enlever le
dernier élément pour que la liste triée contienne les mêmes
éléments que la liste de départ.
Là encore, le nombre de cartes restant à trier est un variant. Ce nombre décroît d'une carte à chaque itération, ce qui prouve la terminaison de l'algorithme.
Chaque fois qu'on insère une carte dans la nouvelle liste, c'est à l'endroit qui garantit que la nouvelle liste reste triée : l'algorithme de tri par insertion a le même invariant que le tri par sélection, à savoir que la nouvelle liste est, et reste, triée.
L'algorithme de tri par insertion est donc bien un algorithme de tri.
Avec un jeu de 8 cartes au départ,
Ce qui fait (au maximum) 0+1+2+3+4+5+6+7=28 comparaisons.
Plus généralement il faut n
(n
-1)/2
soit (n
2-n
)/2
comparaisons (au maximum). D'où l'adjectif quadratique
pour qualifier cet algorithme.