Tri par insertion

6.1 Définition du tri par insertion

Tri par insertion (Insertion Sort) — c'est un algorithme de tri qui construit un tableau trié (ou une liste) un élément à la fois. Il prend chaque élément de la partie non triée et l'insère à sa place correcte dans la partie triée.

Principe de fonctionnement :

1. On commence par le deuxième élément du tableau (le premier élément est considéré comme trié).
2. On compare l'élément actuel avec les précédents et on le déplace vers la gauche jusqu'à ce qu'on trouve le bon endroit.
3. On répète le processus pour tous les éléments du tableau, en insérant chaque nouvel élément à la place correcte dans la partie déjà triée du tableau.

Complexité temporelle et spatiale du tri par insertion

Complexité temporelle :

• Dans le pire des cas: O(n^2) — se produit lorsque les éléments sont initialement ordonnés dans l'ordre inverse.
• Dans le cas moyen: O(n^2) — se produit pour un placement aléatoire des éléments.
• Dans le meilleur des cas: O(n) — se produit lorsque les éléments sont déjà triés.

Complexité spatiale :

O(1) — car l'algorithme utilise une quantité constante de mémoire supplémentaire (seulement quelques variables pour stocker des valeurs temporaires).

6.2 Analyse du fonctionnement de l'algorithme

À chaque étape de l'algorithme, nous avons cette situation :

• Nous avons un élément actuel avec l'index i.
• Tous les éléments à sa gauche sont déjà triés du plus petit au plus grand.
• Nous essayons d'insérer notre élément actuel dans la partie triée du tableau de manière à ce que l'ordre de tri ne soit pas perturbé.

La tentative d'insérer un élément dans la partie triée du tableau ressemble à ceci :

1. La variable j dans la boucle prend les valeurs de i - 1 à 0.
2. Si l'élément actuel (i-ème) est plus petit que le j-ème, alors on déplace la valeur du j-ème élément d'une position à droite.

Exemple : situation actuelle :

• Les éléments verts sont déjà triés.
• En rose — les éléments qui ne sont pas encore triés.
• L'élément actuel avec l'index 5 est marqué en marron.

Nous essayons de trouver la bonne place pour notre élément actuel dans la partie triée du tableau.

Étape 1 — nous mémorisons la valeur de l'élément actuel dans une variable key.

Étape 2 — l'élément No4 est-il plus grand que key? (10 plus grand que 5 ?) Alors on déplace l'élément No4 vers la droite :

Étape 3 — l'élément No3 est-il plus grand que key? (8 plus grand que 5 ?) Alors on déplace l'élément No3 vers la droite :

Étape 4 — l'élément No2 est-il plus grand que key? (6 plus grand que 5 ?) Alors on déplace l'élément No2 vers la droite :

Étape 5 — l'élément No1 est-il plus grand que key? (4 plus grand que 5 ?) Non. Alors nous plaçons l'élément key à l'emplacement de l'élément No2.

Après avoir inséré l'élément No5 à la bonne place, nous passons à l'élément No6 et essayons de lui trouver un endroit dans la partie triée du tableau :

Puis nous prenons le septième élément :

Ensuite, le 8ème :

6.3 Implémentation de l'algorithme de tri par insertion

Voici à quoi cet algorithme ressemblera en Python :

def insertion_sort(arr):
    # On passe sur tous les éléments du tableau, en commençant par le deuxième
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1 # On déplace les éléments arr[0..i - 1] qui sont plus grands que key d'une position vers l'avant while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1
        arr[j + 1] = key # Insérer la clé à la bonne place
    return arr  # Retourne le tableau trié
        
# Exemple d'utilisation :
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Tableau trié :", sorted_arr)
# Résultat : Tableau trié : [5, 6, 11, 12, 13]

Explication :

• On sauvegarde l'élément actuel dans key
• On déplace tous les éléments de la partie triée du tableau vers la droite
• On insère notre élément à la place appropriée

Exemple du fonctionnement de l'algorithme

Prenons un exemple de tableau : [12, 11, 13, 5, 6]

1. Premier passage (i = 1) :

• On compare 11 et 12, on déplace 12 à droite.
• Tableau : [11, 12, 13, 5, 6]

2. Deuxième passage (i = 2) :

• 13 est déjà à sa place.
• Tableau : [11, 12, 13, 5, 6]

3. Troisième passage (i = 3) :

• On compare 5 avec 13, 12 et 11, on déplace tout à droite.
• Tableau : [5, 11, 12, 13, 6]

4. Quatrième passage (i = 4) :

• On compare 6 avec 13, 12 et 11, on déplace tout à droite.
• Tableau : [5, 6, 11, 12, 13]

L'algorithme se termine, car tous les éléments sont triés.