Trier des listes efficacement : maîtriser l'algorithme de tri par insertion en Python

Introduction

Dans le monde des algorithmes de tri, où efficacité et performance sont reines, il y a un héros discret qu'on oublie souvent : l'algorithme de tri par insertion. Il n'a pas la réputation clinquante de ses pairs, mais cet algorithme a une simplicité et une élégance qu'on ne peut ignorer. Dans cet article, on démystifie le tri par insertion avec Python, en explorant son fonctionnement interne, ses avantages, et ses applications pratiques.

La beauté du tri par insertion

À sa base, l'algorithme suit un mantra simple : prendre chaque élément de la liste et l'insérer à sa bonne position dans la portion déjà triée de la liste. Cette approche en fait un excellent choix pour les petits jeux de données ou les listes partiellement triées. Imagine que tu joues aux cartes et que tu tries ta main de gauche à droite — c'est essentiellement ce que fait le tri par insertion sur tes données.

L'idée centrale est de construire progressivement une liste triée en insérant à chaque itération un élément de la portion non triée à sa bonne position dans la portion déjà triée. Ce process d'« insertion » maintient l'ordre trié et finit par produire une liste entièrement triée.

L'algorithme tire parti du fait qu'une liste à un seul élément est triée par nature. Il étend ensuite cette portion triée en considérant un élément à la fois depuis la portion non triée et en le plaçant où il doit aller dans la portion triée.

Comment fonctionne le tri par insertion

Deux versions : pour un enfant, et pour un adulte.

Expliqué à un enfant

Imagine que tu as une ligne de cartes numérotées toutes mélangées, et qu'il faut les remettre en ordre. On va utiliser une méthode spéciale appelée le « tri par insertion ».

Imagine que tu joues à un jeu où tu as quelques cartes en main et que tu veux les ranger du plus petit au plus grand. Tu commences par regarder la première carte et tu fais comme si elle était déjà bien placée (parce qu'une seule carte est déjà ordonnée).

Tu prends la deuxième carte et tu la compares à la première. Si la deuxième est plus petite, tu la mets avant la première. Si elle est plus grande, tu la laisses où elle est.

Puis tu prends la troisième carte et tu la compares aux deux premières. Si elle est plus petite que les deux, tu lui trouves une place avant elles. Si elle n'est plus petite que d'une seule, tu la mets là. Et si elle est plus grande que les deux, tu la laisses où elle est.

Tu continues comme ça pour chaque carte. À chaque fois, tu regardes la carte, tu la compares à celles déjà rangées, et tu lui trouves la bonne place. Tu continues jusqu'à ce que toutes les cartes soient rangées.

Comme ça, tu tries les cartes en « insérant » chaque carte à la bonne place parmi celles déjà rangées. C'est un peu comme placer les pièces d'un puzzle au bon endroit pour compléter l'image !

Le tri par insertion peut prendre un peu plus de temps si tu as beaucoup de cartes, mais il est vraiment efficace quand tu n'en as que peu, ou quand certaines sont déjà presque à la bonne place. C'est une façon patiente de trier qui marche bien pour les petites quantités.

Expliqué à un adulte

Voyons comment le tri par insertion fonctionne avec un exemple pas à pas. Soit la liste non triée suivante :

Liste non triée : 5, 2, 9, 3, 1

Voici comment l'algorithme la trie :

1. Initialisation : le premier élément, 5, est considéré comme la portion triée initiale.
2. Itération sur la portion non triée :
   • On prend le deuxième élément, 2, comme « clé » courante.
   • On compare la clé (2) à l'élément de la portion triée (5). Comme 5 > 2, on décale 5 d'une position vers la droite.
   • On insère la clé (2) à la bonne position dans la portion triée, c'est-à-dire en première position.
   • La liste devient : 2, 5, 9, 3, 1
3. Suite de l'itération :
   • On prend le troisième élément, 9, comme clé.
   • On compare la clé (9) au dernier élément de la portion triée (5). Comme 5 < 9, la clé reste à sa place.
   • La liste reste inchangée : 2, 5, 9, 3, 1
4. Suite de l'itération :
   • On prend le cinquième élément, 1, comme clé.
   • On compare la clé (1) aux éléments de la portion triée (9, 5, 3, 2). On décale tous ces éléments d'une position vers la droite pour faire de la place à la clé.
   • On insère la clé (1) à la bonne position dans la portion triée, c'est-à-dire en première position.
   • La liste devient : 1, 2, 3, 5, 9
5. Fin : tous les éléments ont été parcourus et insérés à leurs bonnes positions. La liste est maintenant entièrement triée : 1, 2, 3, 5, 9

En substance, le tri par insertion prend un élément à la fois depuis la portion non triée, le compare aux éléments de la portion triée, et l'insère à la bonne position. La portion triée grandit à chaque itération jusqu'à ce que tous les éléments soient dans leur ordre final. Ce n'est pas l'algorithme de tri le plus rapide, mais sa simplicité et son adéquation aux petits jeux de données en font un outil précieux dans certains scénarios.

Implémentation en Python

Voici une implémentation pas à pas du tri par insertion en Python, qui réduit le nombre d'assignations dans la boucle interne en utilisant une seule assignation après la boucle. Cela évite les assignations inutiles quand les éléments sont déjà à leurs bonnes positions.

from typing import List

def insertion_sort(arr: List[int]) -> List[int]:
    """
    Sorts a list of integers in ascending order using the Insertion Sort algorithm.

    Args:
        arr (List[int]): The list of integers to be sorted.

    Returns:
            List[int]: The sorted list of integers.
    """
    for i in range(1, len(arr)):
        key = arr[i]  # Current element to be inserted into the sorted portion
        j = i - 1     # Index of the last element in the sorted portion

        # Compare the key with elements in the sorted portion and shift as needed
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key  # Insert the key in its correct position

    return arr

def main():
    # Input collection from the user
    input_str = input("Enter a list of integers separated by a commas: ")
    input_list = [int(x) for x in input_str.split(',')]

    # Print sorted collection
    print(*insertion_sort(input_list), sep=",")

if __name__ == "__main__":
    main()

Cette optimisation réduit le nombre d'assignations dans la boucle interne, ce qui peut améliorer légèrement la performance, surtout sur de plus grands jeux de données. Il faut noter que la complexité temporelle fondamentale de l'algorithme reste la même.

Applications dans le monde réel

En pratique, le tri par insertion est rarement utilisé en production à cause de son inefficacité par rapport à d'autres algorithmes. Il garde quelques cas d'usage limités et reste précieux sur le plan pédagogique. Quelques scénarios :

1. Apprentissage : utilisé en cours d'algorithmique pour introduire les concepts de tri. Sa simplicité aide les débutants à comprendre.
2. Petits jeux de données : si tu as très peu d'éléments à trier, le tri par insertion reste acceptable — ses problèmes de performance ne se voient pas sur les petits tableaux.
3. Données déjà presque triées : si tes données sont déjà majoritairement triées, le côté adaptatif du tri par insertion peut convenir.
4. Tremplin vers d'autres algorithmes : c'est un bon point de départ avant d'attaquer des techniques plus complexes.

Pour la majorité des cas réels — surtout sur de grandes données — on préfère Quick Sort, Merge Sort, ou les fonctions de tri intégrées au langage (par ex. sorted() en Python). Elles offrent des performances bien supérieures.

Conclusion

Dans un monde captivé par la vitesse et la complexité de divers algorithmes de tri, le tri par insertion brille comme un symbole d'élégance et de simplicité. Ce n'est pas l'option la plus rapide pour de grandes données, mais ses qualités uniques en font un ajout précieux à la boîte à outils de tout développeur. La prochaine fois que tu auras une liste modeste à trier, pense au héros discret des algorithmes de tri — le tri par insertion.

Souviens-toi : maîtriser les bases mène souvent à une compréhension plus profonde et à une plus grande appréciation des complexités qui sous-tendent le monde des algorithmes. Bon code !