Tri par sélection et tri par insertion

Le tri est une opération fondamentale en informatique. Parmi les algorithmes classiques les plus accessibles pour débuter, on trouve le tri par sélection (selection sort) et le tri par insertion (insertion sort). Bien qu’ils ne soient pas les plus efficaces pour de grands ensembles de données, ils sont parfaits pour comprendre les bases du tri et des algorithmes en général.

Tri par sélection

Le tri par sélection fonctionne en parcourant la liste à trier, en recherchant l’élément le plus petit (ou le plus grand, selon l’ordre souhaité), puis en l’échangeant avec l’élément en cours. Ce processus est répété en ignorant les éléments déjà triés.

Prenons un exemple concret. Imaginons que l’on souhaite trier la liste suivante : [29, 10, 14, 37, 13]

À la première étape, on cherche le plus petit élément de toute la liste : c’est 10. On échange 10 avec le premier élément (29). Liste après la première itération : [10, 29, 14, 37, 13]

On répète ensuite le processus sur la sous-liste [29, 14, 37, 13], et ainsi de suite.

def tri_par_selection(tab):
    # Récupère la longueur du tableau
    n = len(tab)
    
    # Parcourt chaque élément du tableau
    for i in range(n):
        # Suppose que l'élément courant est le plus petit
        min_index = i
        
        # Parcourt les éléments restants pour trouver le minimum
        for j in range(i + 1, n):
            if tab[j] < tab[min_index]:
                min_index = j  # Met à jour l'index du plus petit élément
        
        # Échange l'élément courant avec le plus petit trouvé
        tab[i], tab[min_index] = tab[min_index], tab[i]
    
    # Retourne le tableau trié
    return tab

Cet algorithme est simple à comprendre, mais il n’est pas très performant sur de grandes données : sa complexité est de $O(n^2)$, car il faut parcourir la liste à chaque étape pour trouver le minimum.

Tri par insertion

Le tri par insertion s’inspire du geste qu’on fait lorsqu’on trie des cartes à jouer à la main. On prend les éléments un par un et on les insère à la bonne position dans une portion déjà triée.

L’algorithme commence par considérer que le premier élément est déjà trié. Ensuite, il prend le second élément et le place à la bonne position par rapport au premier. Puis il prend le troisième et l’insère au bon endroit par rapport aux deux premiers, etc.

Voici un exemple avec la liste [29, 10, 14, 37, 13] :

On commence avec 29, considéré comme trié.
On prend 10, on le compare avec 29, et on l’insère avant. Liste : [10, 29, 14, 37, 13]
Ensuite 14 est comparé à 29, puis à 10. Il finit entre les deux. Liste : [10, 14, 29, 37, 13]
On continue de cette manière jusqu’à ce que la liste soit entièrement triée.

def tri_par_insertion(tab):
    # Parcourt le tableau à partir du deuxième élément
    for i in range(1, len(tab)):
        # Stocke l'élément courant (la clé à insérer)
        cle = tab[i]
        j = i - 1
        
        # Déplace les éléments du tableau qui sont plus grands que la clé
        # vers la droite pour faire de la place à la clé
        while j >= 0 and tab[j] > cle:
            tab[j + 1] = tab[j]
            j -= 1
        
        # Insère la clé à sa position correcte
        tab[j + 1] = cle

    # Retourne le tableau trié
    return tab

Cet algorithme a lui aussi une complexité de $O(n^2)$ dans le pire des cas, mais il peut être plus efficace que le tri par sélection sur des listes presque triées. Il est également plus stable (c’est-à-dire qu’il conserve l’ordre des éléments égaux).

Pour manipuler de grands volumes de données, on privilégiera des algorithmes plus performants comme le tri rapide (quicksort), le tri fusion (merge sort), ou encore on utilisera les fonctions de tri optimisées intégrées à Python comme sorted() ou .sort().

Tri par sélection et insertion

All work licensed under CC BY-NC-SA 4.0