Menu

Tri par insertion en C ++ avec des exemples

insertion sort c with examples

Un examen approfondi du tri par insertion avec des exemples classiques.

Le tri par insertion est une technique de tri qui peut être visualisée d'une manière dont nous jouons aux cartes à portée de main. La façon dont nous insérons une carte dans un jeu ou la supprimons, les tris d'insertion fonctionnent de la même manière.

La technique de l'algorithme de tri par insertion est plus efficace que les techniques de tri à bulles et de tri par sélection, mais elle est moins efficace que les autres techniques comme le tri rapide et le tri par fusion.

=> Découvrez les meilleurs didacticiels de formation C ++ ici.

TRI PAR INSERTION

Ce que vous apprendrez:

Aperçu

Dans la technique du tri par insertion, nous partons du deuxième élément et le comparons avec le premier élément et le plaçons au bon endroit. Ensuite, nous effectuons ce processus pour les éléments suivants.

Nous comparons chaque élément avec tous ses éléments précédents et mettons ou insérons l'élément dans sa bonne position. La technique de tri par insertion est plus pratique pour les tableaux avec un plus petit nombre d'éléments. Il est également utile pour trier les listes chaînées.

Les listes liées ont un pointeur vers l'élément suivant (dans le cas d'une liste liée à un seul lien) et un pointeur vers l'élément précédent également (dans le cas d'une liste doublement liée). Par conséquent, il devient plus facile d'implémenter le tri par insertion pour une liste liée.

jointure gauche vs jointure externe gauche

Explorons tout sur le tri par insertion dans ce didacticiel.

Algorithme général

Étape 1 : Répétez les étapes 2 à 5 pour K = 1 à N-1
Étape 2 : set temp = A [K]
Étape 3 : mettre J = K - 1
Étape 4 : Répéter pendant que la température<=A[J]
définir A [J + 1] = A [J]
définir J = J - 1
[fin de la boucle intérieure]
Étape 5 : régler A [J + 1] = temp
[fin de boucle]
Étape 6 : sortir

Ainsi, dans la technique de tri par insertion, nous partons du deuxième élément car nous supposons que le premier élément est toujours trié. Ensuite, du deuxième élément au dernier élément, nous comparons chaque élément à tous ses éléments précédents et mettons cet élément dans la bonne position.

Pseudocode

Le pseudo code pour le tri par insertion est donné ci-dessous.

procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //locate free position to insert the element whilefreePosition> 0 and array[freePosition -1] >insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //insert the number at free position array [freePosition] = insert_val end for end procedure

Le pseudo-code pour le tri par insertion est donné ci-dessus. Ensuite, nous illustrerons cette technique dans l'exemple suivant.

Illustration

Le tableau à trier est le suivant:

tableau à trier

Maintenant, pour chaque passage, nous comparons l'élément actuel à tous ses éléments précédents. Donc dans la première passe, nous commençons par le deuxième élément.

Tri par insertion - Illustration

Ainsi, nous avons besoin de N nombre de passes pour trier complètement un tableau contenant N nombre d'éléments.

L'illustration ci-dessus peut être résumée sous forme de tableau:

PasseListe non triéeComparaisonListe triée
1{12,3,5,10,8,1}{12,3}{3,12,5,10,8,1}
deux{3,12,5,10,8,1}{3,12,5}{3,5,12,10,8,1}
3{3,5,12,10,8,1}{3,5,12,10}{3,5,10,12,8,1}
4{3,5,10,12,8,1}{3,5,10,12,8}{3,5,8,10,12,1}
5{3,5,8,10,12,1}{3,5,8,10,12,1}{1,3,5,8,10,12}
6{}{}{1,3,5,8,10,12}

Comme le montre l'illustration ci-dessus, nous commençons par le 2ndélément car nous supposons que le premier élément est toujours trié. Nous commençons donc par comparer le deuxième élément avec le premier et inversons la position si le deuxième élément est inférieur au premier.

Ce processus de comparaison et d'échange positionne deux éléments à leur place. Ensuite, nous comparons le troisième élément à ses éléments précédents (premier et deuxième) et exécutons la même procédure pour placer le troisième élément au bon endroit.

De cette manière, pour chaque passage, nous plaçons un élément à sa place. Pour la première passe, nous remettons le deuxième élément à sa place. Ainsi en général, pour placer N éléments à leur place, il faut N-1 passes.

moyen le plus simple de convertir youtube en mp3

Ensuite, nous allons démontrer l'implémentation de la technique de tri par insertion en langage C ++.

Exemple C ++

#include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout<<' Input list is '; for(int i=0;i<10;i++) { cout <

Production:

La liste d'entrée est

12 4 3 1 15 45 33 21 10 2

La liste triée est

1 2 3 4 10 12 15 21 33 45

Ensuite, nous verrons l'implémentation Java de la technique de tri par insertion.

Exemple Java

public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println('Input list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray[i] + ' '); } for(int k=1; k=0 && temp <= myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } System.out.println(' sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray[i] + ' '); } } }

Production:

Liste d’entrée des éléments…

12 4 3 1 15 45 33 21 10 2

liste triée des éléments…

où puis-je regarder l'anime gratuitement

1 2 3 4 10 12 15 21 33 45

Dans les deux implémentations, nous pouvons voir que nous commençons à trier à partir du 2ndélément du tableau (variable de boucle j = 1) et comparez à plusieurs reprises l'élément courant à tous ses éléments précédents, puis triez l'élément pour le placer dans sa position correcte si l'élément courant n'est pas en ordre avec tous ses éléments précédents.

Le tri par insertion fonctionne le mieux et peut être effectué en moins de passes si le tableau est partiellement trié. Mais à mesure que la liste s'allonge, ses performances diminuent. Un autre avantage du tri par insertion est qu'il s'agit d'un tri stable, ce qui signifie qu'il maintient l'ordre des éléments égaux dans la liste.

Analyse de complexité de l'algorithme de tri par insertion

D'après le pseudo code et l'illustration ci-dessus, le tri par insertion est l'algorithme efficace par rapport au tri à bulles ou au tri par sélection. Au lieu d'utiliser la boucle for et les conditions présentes, il utilise une boucle while qui n'effectue plus d'étapes supplémentaires lorsque le tableau est trié.

Cependant, même si nous passons le tableau trié à la technique de tri par insertion, il exécutera toujours la boucle for externe, ce qui nécessitera n nombre d'étapes pour trier un tableau déjà trié. Cela fait de la meilleure complexité temporelle du tri par insertion une fonction linéaire de N où N est le nombre d'éléments dans le tableau.

Ainsi, les différentes complexités de la technique de tri par insertion sont données ci-dessous:

Pire complexité temporelle des casO (n 2)
Meilleure complexité temporelleSur)
Complexité temporelle moyenneO (n 2)
Complexité spatialeO (1)

Malgré ces complexités, nous pouvons toujours conclure que le tri par insertion est l'algorithme le plus efficace par rapport aux autres techniques de tri comme le tri à bulles et le tri par sélection.

Conclusion

Le tri par insertion est la plus efficace des trois techniques évoquées jusqu'à présent. Ici, nous supposons que le premier élément est trié, puis comparons à plusieurs reprises chaque élément à tous ses éléments précédents, puis plaçons l'élément actuel à sa position correcte dans le tableau.

Dans ce didacticiel, tout en discutant du tri par insertion, nous avons remarqué que nous comparons les éléments en utilisant un incrément de 1 et qu'ils sont également contigus. Cette fonctionnalité nécessite plus de passes pour obtenir la liste triée.

Dans notre prochain didacticiel, nous discuterons du «tri Shell» qui est une amélioration par rapport au tri de sélection.

Dans le tri shell, nous introduisons une variable appelée «incrément» ou «intervalle» à l'aide de laquelle nous divisons la liste en sous-listes contenant des éléments non contigus qui «séparent». Le tri Shell nécessite moins de passes par rapport au tri par insertion et est également plus rapide.

Dans nos prochains tutoriels, nous découvrirons deux techniques de tri, «Quicksort» et «Mergesort», qui utilisent la stratégie «Divide and conquer» pour trier les listes de données.

=> Regardez le guide de formation C ++ pour débutants ici.

lecture recommandée

^