Maîtriser l'algorithme Quick Sort en Python : un guide complet

Introduction

Quicksort est un algorithme de tri efficace qui utilise une approche diviser pour régner pour organiser les données. Simpliste en apparence, ce concept est fondamental pour les complexités de programmation comme la recherche dans des fichiers, la compression de données et le pathfinding. Pour optimiser la vitesse et la qualité du process, il faut prendre en compte le temps d'exécution associé au choix d'une méthode de tri. Dans le cas de Quicksort, le pire des cas est lent, mais ses cas moyen et meilleur restent relativement rapides.

C'est quoi l'algorithme Quick Sort

Imagine que tu ranges une chambre en désordre — Quick Sort, c'est arranger les éléments d'une liste de manière similaire. On va voir comment cet algorithme sépare, trie et recombine les éléments pour produire une liste bien rangé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 est plus grande qu'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 parfait 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 du tri par insertion

En pratique, le tri à bulles 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 :

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 n'as que très peu d'éléments à trier, le tri à bulles reste acceptable.
3. Données déjà presque triées : si tes données sont déjà majoritairement triées, le côté adaptatif du tri à bulles 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).

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 !