Algorithme de tri par insertion en 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 à sa position correcte dans une région déjà ordonnée.

Chaque élément est inséré séquentiellement dans une liste triée. Initialement, cette liste contient un seul élément. L'algorithme de tri par insertion garantit que les k premiers éléments sont triés après la k-ième itération de la boucle externe.

Le tri par insertion, qui construit le résultat de manière incrémentale, est intuitif à enseigner, facile à déboguer et constitue une base solide pour les très petites entrées, là où des algorithmes plus complexes ajouteraient une surcharge sans gains mesurables.

Caractéristiques de l'algorithme de tri par insertion

L'algorithme de tri par insertion possède les caractéristiques importantes suivantes qui expliquent son comportement sur des charges de travail réelles :

• 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 petits ensembles de données, mais inefficace pour les listes plus importantes où la croissance quadratique domine.
• Le tri par insertion est adaptatif, ce qui réduit son nombre total d'étapes si les données d'entrée sont partiellement triées. tableau est fourni en entrée pour le rendre efficace car l'accès aléatoire permet des décalages à temps constant pendant la boucle interne.
• Il s'agit d'un algorithme sur place, il ne nécessite donc pas de stockage auxiliaire proportionnel à la taille des données d'entrée.

En tenant compte de ces caractéristiques, la section suivante explique l'opération d'insertion principale qui sous-tend chaque itération de l'algorithme.

Comment Insérer Operatravail ?

Dans l'algorithme de tri par insertion, l'opération d'insertion sert à trier les éléments non triés. Elle permet d'insérer un nouvel élément dans une liste déjà triée tout en préservant l'ordre existant de la partie triée.

Pseudocode de l'opération d'insertion :

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

// Insert A[N-1] into 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, est inséré dans une liste déjà triée. Les étapes suivantes trace la boucle interne à mesure que le nouvel élément migre vers la gauche, en direction de sa position correcte.

É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], donc nous échangeons à nouveau la position de 6 et 8.

Étape 3) Comparons maintenant A[3] et A[2]. Comme A[2] > A[3], nous échangeons la position de 7 et 6.

Étape 4) Nous comparons A[1] et A[2]. Comme A[1] < A[2], l'élément adjacent à gauche n'est plus supérieur. Nous en concluons que 6 est correctement inséré et nous arrêtons la boucle interne.

Comment fonctionne le tri par insertion

L'opération d'insertion décrite ci-dessus est la base du tri par insertion. La procédure d'insertion est exécutée sur chaque élément, et à la fin, on obtient la liste triée, la zone de tri s'enrichissant d'un élément à chaque passage externe.

La figure ci-dessus illustre le fonctionnement du tri par insertion dans une structure de données. Initialement, la sous-liste triée ne contient qu'un seul élément, soit 4. Après l'insertion de A[1], soit 3, la taille de la sous-liste triée passe à 2, et l'algorithme poursuit ce processus jusqu'à ce que tous les éléments aient été insérés.

Une fois le cadre conceptuel établi, les sections suivantes présentent des implémentations concrètes dans C++, C et Python Vous pouvez ainsi comparer les structures de boucles entre les langages.

C++ Programme de tri par insertion

Le C++ L'implémentation ci-dessous utilise deux boucles imbriquées : la boucle externe sélectionne l'élément non trié suivant, et la boucle interne le décale vers la gauche jusqu'à ce que la position correcte soit trouvée.

#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

C Code pour le tri par insertion

La même logique se transpose directement en C. La norme printf Les appels remplacent la sortie du flux, mais le modèle d'échange à l'intérieur de la boucle interne est identique à celui du C++ version.

#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

Python prend en charge l'échange de tuplesping dans une seule expression, la boucle interne est donc plus compacte que son C et C++ homologues tout en préservant le même comportement algorithmique.

#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 qui vous aideront à déterminer quand il s'agit de l'outil approprié :

• En ligne: Le tri par insertion trie les éléments au fur et à mesure de leur réception. Si une liste d'éléments a déjà été triée et que l'on y ajoute de nouveaux éléments, il n'est pas nécessaire de relancer toute la procédure de tri. On itère uniquement 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, on ne permute pas les éléments si leurs valeurs sont égales. Par exemple, si deux éléments, x et y, sont égaux et que x précède y dans la liste non triée, alors dans la liste triée, x précédera toujours y. C'est ce qui rend le tri par insertion stable.
• Adaptatif: A algorithme de tri Un algorithme est dit adaptatif s'il est plus rapide lorsque les éléments d'entrée, ou un sous-ensemble d'éléments, sont déjà triés. Comme indiqué précédemment, sa complexité temporelle optimale est O(N) et sa complexité temporelle maximale est O(N²). Le tri par insertion fait partie des algorithmes de tri adaptatifs.

Complexité du tri par insertion

L'analyse de complexité ci-dessous aborde à la fois l'utilisation de la mémoire et le temps d'exécution, ce qui vous permet de comparer le tri par insertion à des alternatives telles que Bubble Trier et Tri rapide.

Complexité spatiale

Le tri par insertion ne nécessite pas d'espace supplémentaire pour trier les éléments. Sa complexité spatiale est constante, soit O(1), car seules quelques variables temporaires sont utilisées, quelle que soit la taille des données d'entrée.

Complexité temporelle

Le tri par insertion traitant un élément à la fois, il nécessite N-1 passages pour trier N éléments. À chaque passage, aucun échange n'est nécessaire si les éléments sont déjà triés ; de nombreux échanges peuvent être nécessaires si les éléments sont trié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 nombre total d'échanges maximum est (1+2+3+4+…+N) c'est-à-dire N(N+1)/2, donc la pire complexité temporelle est O(N^2).

Voici la complexité temporelle importante du tri par insertion :

• Pire complexité des cas: O(n^2) : Trier un tableau en ordre décroissant alors qu'il doit être en ordre croissant est le pire des cas.
• Meilleur cas de complexité : O(n) : Le cas optimal se présente lorsque le tableau est déjà trié ; la boucle externe s’exécute n fois, tandis que la boucle interne ne s’exécute pas du tout. Il n’y a que n comparaisons, la complexité est donc linéaire.
• Complexité moyenne des cas : O(n^2) : Cela se produit lorsque les éléments du tableau apparaissent dans un ordre aléatoire qui n'est ni croissant ni décroissant.

FAQ