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

Qu’est-ce que le tri par insertion ?

Le tri par insertion fait partie du tri par comparaison algorithms utilisé 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 a suiviwing Caractéristiques importantes :

  • 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'insertion operation 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 d'insertion operation:

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   

insérer Operatravail de travail

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'insert operaLa tion évoquée 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.

Travaux de tri par insertion

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.

Programme C++ pour le 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

Programme Python pour le 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: L'espace complexLa qualité 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 tris adaptatifs algorithms.

Avecplexité du tri par insertion

Espace Complexity

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

Temps Complexity

Comme le tri par insertion itère chaque élément simultanémentneogénéralement, il faut 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 zéro, donc le meilleur moment est venuplexity 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, le pire moment complexla ville est O(N^2).

Voici le moment importantplexité du tri par insertion :

  • Dans le pire des casplexity: O(n2) : trier un tableau par ordre décroissant lorsqu'il est par ordre croissant est le pire des cas.
  • Meilleur cas Complexité: O(n) : Meilleur cas ComplexCela 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 qu’un nombre n de comparaisons. Donc, dans ce cas, complexla ville est linéaire.
  • Cas moyen Complexité: 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'insert operation permet d'insérer l'élément dans la sous-liste triée.
  • Le tri par insertion est un algorithme de tri sur place.
  • Le pire et le temps moyenplexLa nature du tri par insertion est quadratique, c'est-à-dire O(N^2).
  • Le tri par insertion ne nécessite aucun espace auxiliaire.