Algorithmes de tri

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.

I/ Par sélection

1) Principe

2) Code Python

a) Le tri

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

b) Test de liste vide

def vide(liste:list) -> bool:
    return len(liste)==0

c) Minimum d'une liste

Voir le chapitre sur les listes en Python

d) Retrait d'une carte

def enlever(liste:list,elt:float):
    liste.remove(elt)

e) Ajout d'une carte

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)

3) Propriétés

a) Variant

À 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.

b) Invariant

À 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.

c) Coût

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.

II/ Par insertion

1) Principe

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 ?

2) Code Python

a) Insertion

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.

b) Tri par insertion

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.

3) Propriétés

a) Variant

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.

b) Invariant

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.

c) Coût

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 (n2-n)/2 comparaisons (au maximum). D'où l'adjectif quadratique pour qualifier cet algorithme.