Tri par insertion : algorithme avec C, C++, Java, Python Exemples

Qu’est-ce que le tri par insertion ?

Le tri par insertion est l'un des algorithmes de tri par comparaison utilisés pour trier les éléments en itérant sur un élément à la fois et en plaçant l'élément dans sa position correcte.

Chaque élément est inséré séquentiellement dans une liste déjà triée. La taille de la liste déjà triée est initialement de un. L'algorithme de tri par insertion garantit que les k premiers éléments sont triés après la kième itération.

Caractéristiques de l'algorithme de tri par insertion

L'algorithme de tri par insertion présente les caractéristiques importantes suivantes :

• Il s’agit d’une technique de tri stable, elle ne modifie donc pas l’ordre relatif des éléments égaux.
• Il est efficace pour les ensembles de données plus petits mais pas pour les listes plus grandes.
• Le tri par insertion est adaptatif, ce qui réduit son nombre total d'étapes s'il est partiellement trié. tableau est fourni en entrée pour le rendre efficace.

Comment Insérer Operatravail ?

Dans l’algorithme de tri par insertion, l’opération d’insertion est utilisée pour trier les éléments non triés. Cela permet d'insérer un nouvel élément dans une liste déjà triée.

Pseudocode de l'opération d'insertion :

Considérons une liste A de N éléments.

A[N-1] is the element to be inserted in the sorted sublist A[0..N-2].
For i = N-1 to 1:
if A[i] < A[i-1], then swap A[i] and A[i-1]
else Stop   

Dans l'exemple ci-dessus, un nouvel élément 6 doit être inséré dans une liste déjà triée.

Étape 1) Par rapport à l'élément adjacent gauche de A[5], 9 > 6, nous échangeons la position de 9 et 6. L'élément 6 est maintenant déplacé vers A[4].

Étape 2) Maintenant, nous comparons A[4] et A[3], et nous constatons que A[3] > A[4], nous échangeons à nouveau la position de 6 et 8.

Étape 3) Comparez maintenant A[3] et A[2], car A[2] > A[3] échange la position de 7 et 6.

Étape 4) Nous comparons A[1] et A[2], et comme A[1] < A[2], c'est à dire que l'élément adjacent gauche n'est plus plus grand. Nous concluons maintenant que 6 est inséré correctement, et nous arrêtons l'algorithme ici.

Comment fonctionne le tri par insertion

L’opération d’insertion décrite ci-dessus constitue l’épine dorsale du tri par insertion. La procédure d'insertion est exécutée sur chaque élément et à la fin, nous obtenons la liste triée.

L'exemple de figure ci-dessus montre le fonctionnement du tri par insertion dans la structure de données. Initialement, un seul élément est présent dans la sous-liste triée, c'est-à-dire 4. Après avoir inséré A[1], c'est-à-dire 3, la taille de la sous-liste triée passe à 2.

C++ Programme de tri par insertion

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
    
    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]); 

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    } 

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){        
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    } 

    return 0;
}

Sortie :

Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

Code C pour le tri par insertion

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

Sortie :

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

Python Programme de tri par insertion

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

Sortie :

Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

Propriétés du tri par insertion

Voici les propriétés importantes du tri par insertion :

• En ligne: Le tri par insertion peut trier les éléments au fur et à mesure de leur réception. Autrement dit, si nous avons déjà trié une liste d’éléments et ajouté quelques éléments supplémentaires aux listes, nous n’avons pas besoin de réexécuter toute la procédure de tri. Au lieu de cela, nous devons uniquement itérer sur les éléments nouvellement ajoutés.
• En place: La complexité spatiale de l'algorithme de tri par insertion est constante et ne nécessite pas d'espace supplémentaire. Cet algorithme trie les éléments sur place.
• Stable: Dans le tri par insertion, nous n'échangeons pas les éléments si leurs valeurs sont égales. Par exemple, deux éléments, x et y, sont égaux et x apparaît avant y dans les listes non triées, puis dans la liste triée, x apparaîtra avant y. Cela rend le tri par insertion stable.
• Adaptatif: A algorithme de tri est adaptatif si cela prend moins de temps si les éléments d'entrée ou le sous-ensemble d'éléments sont déjà triés. Comme nous l'avons vu ci-dessus, le meilleur temps d'exécution du tri par insertion est O(N), et le pire temps d'exécution est O(N^2). Le tri par insertion est l'un des algorithmes de tri adaptatif.

Complexité du tri par insertion

Complexité spatiale

Le tri par insertion ne nécessite pas d'espace supplémentaire pour trier les éléments, la complexité spatiale est constante, c'est-à-dire O(1).

Complexité temporelle

Comme le tri par insertion itère chaque élément simultanément, il nécessite N-1 passes pour trier N éléments. Pour chaque passe, il peut effectuer un échange nul si les éléments sont déjà triés, ou un échange si les éléments sont classés par ordre décroissant.

• Pour le pass 1, les swaps minimum requis sont zéro et les swaps maximum requis sont 1.
• Pour le pass 2, les swaps minimum requis sont zéro et les swaps maximum requis sont 2.
• Pour le pass N, le swap minimum requis est zéro et le swap maximum requis est N.
• Le swap minimum est nul, donc la meilleure complexité temporelle est O(N) pour itérer N passes.
• Le total maximum des swaps est de (1+2+3+4+..+N) i. N(N+1)/2, la pire complexité temporelle est O(N^2).

Voici la complexité temporelle importante du tri par insertion :

• Pire complexité des cas: O(n2) : trier un tableau par ordre décroissant lorsqu'il est par ordre croissant est le pire des cas.
• Meilleur cas de complexité : O(n) : Meilleur La complexité du cas se produit lorsque le tableau est déjà trié, la boucle externe s'exécute n fois alors que la boucle interne ne s'exécute pas du tout. Il n'y a que n nombre de comparaisons. Donc, dans ce cas, la complexité est linéaire.
• Complexité moyenne des cas : O(n2) : Cela se produit lorsque les éléments d'un tableau apparaissent dans un ordre confus, qui n'est ni ascendant ni décroissant.

Résumé

• Le tri par insertion est une méthode d'algorithme de tri basée sur la comparaison.
• Il s’agit d’une technique de tri stable, elle ne modifie donc pas l’ordre relatif des éléments égaux.
• Sur chaque élément, l'opération d'insertion est utilisée pour insérer l'élément dans la sous-liste triée.
• Le tri par insertion est un algorithme de tri sur place.
• La complexité temporelle la plus mauvaise et moyenne du tri par insertion est quadratique, c'est-à-dire O (N ^ 2).
• Le tri par insertion ne nécessite aucun espace auxiliaire.