Qu'est-ce que le tri par insertion en C ?
La méthode de tri appelée tri par insertion fait correspondre chaque élément avec les éléments adjacents lors de son itération dans un tableau. Un élément plus petit que celui qui le précède est inséré dans le sous-tableau trié à l'emplacement approprié.
Pour illustrer davantage, j'ai démontré un exemple dans lequel j'ai considéré un tableau de quatre éléments dans un tableau tel que tab[]= {5, 4, 60, 9} et nous voulons trier cet élément dans l'ordre croissant en utilisant le tri par insertion. Les interactions suivantes expliquent l'exécution complète du tri par insertion :
Itération 1
| 5 | 4 | 60 | 9 |
Nous avons un tableau comme arr[5, 4, 60, 9] maintenant, dans la première itération du tri par insertion, nous comparons d'abord les deux premiers éléments tels que 5 et 4, Comme le arr[5] est> arr[4] donc nous les échangeons pour trier le tableau par ordre croissant. Maintenant, le tableau sera :
| 4 | 5 | 60 | 9 |
Itération 2
| 4 | 5 | 60 | 9 |
Dans la deuxième itération, nous comparons les deux éléments suivants, tels que arr[5] avec arr[60].
Comme arr[5] < arr[60], l'échange ne se produit pas car il est déjà trié par ordre croissant. Maintenant, le tableau devient :
| 4 | 5 | 60 | 9 |
Itération 3
| 4 | 5 | 60 | 9 |
Comme dans la troisième itération, nous faisons correspondre les troisième et quatrième éléments comme arr[60] avec arr[9].
Maintenant, nous voyons que le arr[60]> arr[9] donc l'échange se produit, alors le tableau sera trié par ordre croissant.
| 4 | 5 | 9 | 60 |
C'est ainsi que fonctionne le tri par insertion en C qui trie facilement un élément de tableau dans l'ordre croissant ou décroissant.
Organigramme du tri par insertion
Voici l'organigramme de l'algorithme du tri par insertion :
Implémentation d'un exemple de tri par insertion en C
Nous avons d'abord besoin d'une collection d'éléments qui doivent être triés par ordre décroissant et croissant pour construire la méthode de tri par insertion en C. Supposons pour les besoins de cet exemple que nous avons affaire à un tableau de nombres {5, 4, 60, 9} :
#includeannuler insertionsort_ascending ( entier arr1 [ ] , entier n ) {
entier je , j , ma clé ;
//la boucle for est utilisée pour itérer les valeurs i de 1 à i
pour ( je = 1 ; je < n ; je ++ ) {
ma clé = arr1 [ je ] ;
j = je - 1 ;
alors que ( j >= 0 && arr1 [ j ] > ma clé ) {
arr1 [ j + 1 ] = arr1 [ j ] ;
j = j - 1 ;
}
arr1 [ j + 1 ] = ma clé ;
}
}
annuler insertionsort_descending ( entier arr2 [ ] , entier m ) {
entier je , j , ma clé ;
//une autre boucle for est créée pour itérer les valeurs i de 1 à i
pour ( je = 1 ; je < m ; je ++ ) {
ma clé = arr2 [ je ] ;
j = je - 1 ;
alors que ( j >= 0 && arr2 [ j ] < ma clé ) {
arr2 [ j + 1 ] = arr2 [ j ] ;
j = j - 1 ;
}
arr2 [ j + 1 ] = ma clé ;
}
}
entier principal ( ) {
//Insertion-Sort avec ordre décroissant
entier mon_arr [ ] = { 5 , 4 , 60 , 9 } ; //initialise un my_arr[] ayant quatre valeurs
entier m = taille de ( mon_arr ) / taille de ( mon_arr [ 0 ] ) ;
insertionsort_descending ( mon_arr , m ) ;
printf ( 'Tableau trié par ordre décroissant :' ) ;
pour ( entier je = 0 ; je < m ; je ++ )
printf ( '%d ' , mon_arr [ je ] ) ;
printf ( ' \n ' ) ;
//Insertion-Sort avec ordre croissant
entier n = taille de ( mon_arr ) / taille de ( mon_arr [ 0 ] ) ;
insertionsort_ascending ( arr2 , n ) ;
printf ( 'Tableau trié par ordre croissant : ' ) ;
pour ( entier je = 0 ; je < n ; je ++ )
printf ( '%d ' , mon_arr [ je ] ) ;
printf ( ' \n ' ) ;
retour 0 ;
}
Dans ce code, deux méthodes insertionsort_descending() , et insertionsort_ascending() prendre les valeurs du tableau de mon_arr[] . Le code utilise alors un pour la boucle pour parcourir les éléments du tableau.
Nous appelons les deux fonctions dans la fonction principale une fois qu'elles ont trié les tableaux dans l'ordre décroissant et croissant. Après cela, les boucles for sont utilisées pour imprimer le tableau trié.
Lorsque nous exécutons ce programme, la sortie attendue est placée ci-dessous :
Conclusion
Le tri par insertion est un moyen simple et rapide de trier un tableau dans l'ordre décroissant ou croissant. Pour les petits ensembles de données, cette technique de tri fonctionne bien. Comme vous pouvez le voir dans le guide ci-dessus, il est simple d'implémenter un exemple de programme C pour comprendre facilement le tri par insertion dans l'ordre décroissant et croissant.