20 - Tris

Généralités sur les tris

Nous nous intéresserons au tri d’une liste d’objets qui sont munis d’un ordre total. C’est à dire que deux éléments sont toujours comparables grâce à une relation d’ordre. Parmi les types en python munis d’un ordre total on peut citer :

• les entiers ;
• les flottants ;
• les chaînes de caractères.

Un algorithme de tri en informatique, est un algorithme qui permet d’organiser une collection d’objets selon une relation d’ordre déterminée. Les objets à trier sont des éléments d’un ensemble muni d’un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d’ordre usuelle « est inférieur ou égal à ». Notre collection d’objet, dans ce chapitre, sera une liste d’éléments.

Exemples

• Voici une liste d’entier [42, 3, 5, 9, 21, 9, 14] qui une fois triée sera [3, 5, 9, 9, 14, 21, 42]. C’est la relation d’ordre \(\leq\) qui est utilisée.
• Dans le cas d’une chaine de caractères, c’est la relation d’ordre lexicographique. Dans le cas de la liste : M = ["salut", "tout", "le", "monde"] la liste triée sera [’le’, ’monde’, ’salut’, ’tout’].
• Attention car la comparaison des chaînes de caractères peut être biaisée par la casse (Majuscule / minuscules).

    >>> 'a' < 'A'
    False
    >>> 'A' < 'a'
    True
    >>> 'B' < 'a'
    True
    >>> 'Z' < 'a'
    True
    >>> 'Bonjour' < 'bonjour'
    True
  

Ainsi, selon vous, quel est le résultat du tri de la liste suivante ?

N = ["Ah !", "Non !", "C’est", "un", "peu", "court", "jeune", "homme !"].

Tri en place

Un tri est dit « en place » s’il est effectué directement dans la structure de donnée initiale, et ne nécessite pas l’allocation d’une nouvelle structure.

Tri stable

Un tri est dit stable s’il préserve l’ordonnancement initial des éléments que l’ordre considère comme égaux.

Par exemple, imaginez que vous vouliez trier la collection de bouteilles ci-dessous par ordre de volume (le volume est indiqué sous la bouteille) :

Si vous obtenez ceci, alors votre tri n’était pas stable :

En effet, la bouteille noire de volume 1 se trouve maintenant avant la bouteille bleue de même volume alors qu’elle devrait être après. Il en est de même pour les deux bouteilles de volume 4 qui sont inversées par rapport à l’ordre initial. Avec un tri stable, on aurait obtenu :

Échange de deux valeurs dans une liste

Écrire une fonction echanger() qui prend en paramètres une liste L et deux entiers i et j et qui renvoie la liste L où les éléments d’indice i et j ont été échangés.

def echanger(L, i, j):
    """Échange les éléments aux indices i et j dans la liste L"""
    L[i], L[j] = L[j], L[i]
    return L

Vérifier qu’une liste est bien triée

Une liste L est bien triée si et seulement si :

\[ \forall i,j \in [0,\dots,n-1], i < j \implies L[i] \leq L[j] \]

Écrire une fonction est_triee() qui prend en paramètre une liste L et renvoie le booléen True si la liste est triée, False sinon.

def est_triee(L):
    """Vérifie si la liste L est triée en ordre croissant"""
    for i in range(len(L) - 1):
        if L[i] > L[i + 1]:
            return False
    return True

Tri par sélection

Le principe du tri par sélection sur une liste d’entiers est le suivant :

• on parcourt l’intégralité de la liste à la recherche du petit élément ;
• une fois sélectionné ce plus petit élément, on le permute avec le tout premier élément de la liste (celui d’indice 0) ; le plus petit élément de la liste est alors en première position ;
• on parcourt alors le reste de la liste pour sélectionner son plus petit élément, que l’on permute alors avec le deuxième élément de la liste (d’indice 1) ;
• on recommence jusqu’à placer l’avant-dernier élément à sa place et la tâche est terminée.

Le tri par sélection se fait en place et est non stable.

Exemple

Voici une illustration du fonctionnement du tri par sélection sur un tableau de 6 éléments :

Trace détaillée :

• Itération 0 : Recherche du minimum dans [12, 9, 3, 7, 14, 11]. Minimum = 3 à l’indice 2. On échange 12 et 3.
• Itération 1 : Recherche du minimum dans [9, 12, 7, 14, 11]. Minimum = 7 à l’indice 3. On échange 9 et 7.
• Itération 2 : Recherche du minimum dans [12, 9, 14, 11]. Minimum = 9 à l’indice 3. On échange 12 et 9.
• Itération 3 : Recherche du minimum dans [12, 14, 11]. Minimum = 11 à l’indice 5. On échange 12 et 11.
• Itération 4 : Recherche du minimum dans [14, 12]. Minimum = 12 à l’indice 5. On échange 14 et 12.
• Résultat final : [3, 7, 9, 11, 12, 14]

Questions :

1. Observer qu’une fois que l’avant-dernier élément est en place, le dernier l’est aussi.
2. À vous de tracer les étapes du tri par sélection sur le tableau suivant : [9, 4, 5, 4, 1, 3]

Programme complet

def tri_selection(L):
    '''Prend en argument une liste et la retourne triée par sélection'''
    assert type(L) is list, "Fournir un type list en argument !"
    for i in range(len(L) - 1):
        indice_du_min = i  # l'indice temporaire du plus petit élément
        for j in range(i + 1, len(L)):
            # parcours de la liste partielle à la recherche de l'indice du plus petit élément
            if L[j] < L[indice_du_min]:
                indice_du_min = j
        # échange l'élément à la position i avec le minimum trouvé
        echanger(L, i, indice_du_min)
    return L

Invariant de boucle : À la fin de l’itération i, les i + 1 premiers éléments de la liste sont triés et à leur position définitive.

Tri par insertion

Le principe du tri par insertion est d’insérer l’élément en cours (d’indice i) à sa place parmi les éléments triés qui le précède.

La plupart des personnes l’utilisent naturellement pour trier des cartes à jouer. Imaginez un paquet de carte sur une table, et dans votre main, des cartes déjà triées. Vous saisissez une carte (l’élément d’indice i) et vous la rangez dans votre main à la bonne place (on trie cet élément parmi les éléments triés qui le précède). Puis on recommence…

En général, le tri par insertion est beaucoup plus lent que d’autres algorithmes comme le tri rapide (ou quicksort) et le tri fusion pour traiter de grandes séquences, car sa complexité pour de grandes données est quadratique. Le tri par insertion est cependant considéré comme le tri le plus efficace sur des entrées de petite taille. Il est aussi très rapide lorsque les données sont déjà presque triées. Pour ces raisons, il est utilisé en pratique en combinaison avec d’autres méthodes comme le tri rapide.

Le tri par insertion est un tri stable (conservant l’ordre d’apparition des éléments égaux) et un tri en place (il n’utilise pas de liste auxiliaire).

Exemple

Voici une illustration du fonctionnement du tri par insertion sur un tableau de 6 éléments :

Trace détaillée :

• Itération i = 1 : Partie triée = [12], élément = 9. 9 < 12, donc décalage. Résultat = [9, 12, 3, 7, 14, 11]
• Itération i = 2 : Partie triée = [9, 12], élément = 3. 3 < 12 puis 3 < 9, décalages. Résultat = [3, 9, 12, 7, 14, 11]
• Itération i = 3 : Partie triée = [3, 9, 12], élément = 7. 7 < 12, décalage, 7 < 9, décalage, 7 ≥ 3, stop. Résultat = [3, 7, 9, 12, 14, 11]
• Itération i = 4 : Partie triée = [3, 7, 9, 12], élément = 14. 14 >= 12, pas de décalage. Résultat = [3, 7, 9, 12, 14, 11]
• Itération i = 5 : Partie triée = [3, 7, 9, 12, 14], élément = 11. 11 < 14, décalage, 11 < 12, décalage, 11 >= 9, stop. Résultat = [3, 7, 9, 11, 12, 14]
• Résultat final : [3, 7, 9, 11, 12, 14]

Questions :

À vous de tracer les étapes du tri par insertion sur le tableau suivant : [9, 4, 5, 4, 1, 3]

Programme complet

def tri_insertion(L):
    """
    Entrée : une liste d'éléments int ou float, ou str
    Sortie : la liste constituée des même éléments, triée par ordre croissant
    """
    for i in range(1, len(L)):
        en_cours = L[i]
        j = i
        # décalage des éléments de la liste vers la droite
        while j > 0 and L[j - 1] > en_cours:
            L[j] = L[j - 1]  # décalage
            j -= 1
        # on insère l'élément à sa place
        L[j] = en_cours
    return L

Invariant de boucle : À la fin de l’itération i, les i + 1 premiers éléments de la liste sont triés (mais pas nécessairement à leur position définitive).

Complexité

La complexité d’un algorithme est une mesure du temps d’exécution (ou de l’espace mémoire) en fonction de la taille de l’entrée.

Tri par sélection

Pour chaque position i de 0 à n − 2 :

• On parcourt les éléments de i + 1 à n - 1 pour trouver le minimum
• Nombre de comparaisons : (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2

Le tri par sélection a toujours une complexité quadratique car il parcourt systématiquement la liste pour chaque position.

Tri par insertion

Pour chaque position i de 1 à n − 1 :

• Dans le pire cas, on décale les i - 1 éléments précédents
• Total : 1 + 2 + ... + (n - 1) = n(n - 1)/2 décalages

Le tri par insertion est linéaire sur une liste presque triée et quadratique en général, ce qui le rend plus efficace que la sélection en pratique.

Comparaison résumée

Comparaison expérimentale

Le code suivant mesure les temps d’exécution des deux algorithmes sur des listes de tailles croissantes :

import time
import random

def tri_selection(L):
    for i in range(len(L) - 1):
        indice_du_min = i
        for j in range(i + 1, len(L)):
            if L[j] < L[indice_du_min]:
                indice_du_min = j
        L[i], L[indice_du_min] = L[indice_du_min], L[i]
    return L

def tri_insertion(L):
    for i in range(1, len(L)):
        en_cours = L[i]
        j = i
        while j > 0 and L[j - 1] > en_cours:
            L[j] = L[j - 1]
            j -= 1
        L[j] = en_cours
    return L

# Tests de performance
tailles = [100, 250, 500, 1000]

for taille in tailles:
    # Génération d'une liste aléatoire
    L_aleatoire = [random.randint(0, 10000) for _ in range(taille)]

    # Test tri par sélection
    L1 = L_aleatoire.copy()
    debut = time.time()
    tri_selection(L1)
    temps_selection = time.time() - debut

    # Test tri par insertion
    L2 = L_aleatoire.copy()
    debut = time.time()
    tri_insertion(L2)
    temps_insertion = time.time() - debut

    print(f"Taille {taille:4d} | Sélection: {temps_selection:.4f}s | Insertion: {temps_insertion:.4f}s | Ratio: {temps_selection/temps_insertion:.2f}")

Résultats attendus : Pour une liste aléatoire, les deux algorithmes ont des performances similaires (\(\Theta(n^2)\)). Cependant, le tri par insertion est plus rapide sur une liste presque triée.

Exercices

Exercice 1 : Traçage manuel du tri par sélection

Tracez pas à pas l’exécution du tri par sélection sur la liste suivante :

Liste initiale : [15, 3, 9, 1, 12]

Pour chaque itération, indiquez :

• La partie triée (en gras)
• Le minimum trouvé dans la partie non triée
• L’état de la liste après l’échange

Exercice 2 : Implémentation de la fonction echanger

Implémenter une fonction echanger(L, i, j) qui :

• Prend une liste L et deux indices i et j
• Échange les éléments aux indices i et j
• Retourne la liste modifiée

Testez votre fonction avec :

L = [5, 2, 8, 1]
echanger(L, 0, 3)  # Doit retourner [1, 2, 8, 5]

Exercice 3 : Comparaison de stabilité

Soit une liste de tuples (nom, score) :

donnees = [("Alice", 85), ("Bob", 85), ("Charlie", 90), ("Diana", 85)]

1. Triez cette liste par score en utilisant le tri par insertion
2. Triez cette liste par score en utilisant le tri par sélection
3. Comparez les résultats. Laquelle des deux ordonnances préserve l’ordre initial des personnes ayant le même score ?

Exercice 4 : Analyse de complexité

Pour un tableau de taille n = 1000 :

1. Calculez le nombre exact de comparaisons effectuées par le tri par sélection.
2. Calculez le nombre exact de comparaisons pour le tri par insertion dans le pire cas.
3. Si le tri par sélection prend 10 millisecondes, combien de temps (approximativement) le tri par sélection prendrait-il pour n = 10000 ?

Exercice 5 : Preuve par invariant

Prouvez que le tri par sélection est correct en utilisant l’invariant :

Invariant : À la fin de l’itération i, les i + 1 premiers éléments de la liste contiennent les i + 1 plus petits éléments de la liste originale, et ils sont triés.

1. Montrez que l’invariant est vrai à l’initialisation (avant la première itération)
2. Montrez que si l’invariant est vrai après l’itération i, il reste vrai après l’itération i + 1
3. Montrez que l’invariant implique la correction de l’algorithme