Différence entre le tri de l'insertion et le tri de sélection

Différence clé - insertion Trier vs trie de sélection
 

Le tri de l'insertion et le tri de sélection sont deux algorithmes de tri utilisés pour trier une collection de données. Parfois, il est nécessaire d'organiser des données dans un ordre spécifique. Les algorithmes de tri sont des mécanismes pour trier un ensemble de données. En tri, les données sont organisées selon un ordre numérique ou lexicographique. Si les données sont triées correctement, il serait facile de rechercher les données plus rapidement. Si les numéros de téléphone d'un répertoire téléphonique ne sont pas triés, il serait difficile de trouver un numéro de téléphone spécifique. De la même manière, si les mots du dictionnaire ne sont pas organisés dans l'ordre alphabétique, il serait très difficile de trouver des mots. Par conséquent, le tri est utile dans la vie quotidienne. En informatique, il existe des algorithmes de tri pour trier une collection de données. Deux de ces algorithmes sont le tri et le tri de sélection de l'insertion. Le tri d'insertion est l'algorithme de tri qui trie le tableau en changeant les éléments un par un. Le tri de sélection est l'algorithme de tri qui trouve le plus petit élément du tableau et échange l'élément avec la première position, puis trouvez le deuxième plus petit élément et l'échangez avec l'élément de la deuxième position et continue le processus jusqu'à ce que le tableau entier soit trié. Le différence clé Entre le tri et le tri de sélection de l'insertion est que Le tri d'insertion compare deux éléments à la fois tandis que le tri de sélection sélectionne l'élément minimum dans l'ensemble du tableau et le trie.

CONTENU

1. Aperçu et différence clé
2. Qu'est-ce que le tri de l'insertion
3. Qu'est-ce que le tri de sélection
4. Similitudes entre le tri de l'insertion et le tri de sélection
5. Comparaison côte à côte - Tri d'insertion vs tri de sélection sous forme tabulaire
6. Résumé

Qu'est-ce que le tri de l'insertion?

Le tri de l'insertion est un algorithme de tri basé sur la comparaison sur place.  Dans cette méthode, le tableau est fouillé étape par étape. Les articles non triés sont déplacés et insérés dans la subliste triée du tableau. L'algorithme de tri d'insertion peut être expliqué en utilisant l'exemple suivant.

Par exemple, prenez le tableau initial de 77,33, 44,11,88.  Dans cet algorithme de tri, la première étape consiste à sélectionner l'élément actuel.

L'élément actuel est 77. L'élément actuel est comparé à tous les éléments du côté gauche. Le 77, est le premier élément et il n'y a pas d'éléments sur le côté gauche. L'indice de la position actuelle est 0.

Alors l'indice de la position actuelle est incrémenté de 1. Maintenant, l'index est 1, et l'élément actuel est 33. Lorsque vous le comparez avec l'élément à gauche, il est inférieur à 77. Ensuite, ces deux valeurs sont échangées. Maintenant 33 est dans l'index 0, et 77 est dans l'index1.

Maintenant, le tableau est de 33, 77, 44, 11, 88.

Encore une fois, l'indice est incrémenté. L'indice est 2 et l'élément actuel est 44. Il est comparé aux éléments du côté gauche. 44 est inférieur à 77. Donc ces deux valeurs sont échangées. Maintenant, le tableau est de 33,44,77,11,88. Il est nécessaire de comparer tous les éléments à gauche. Ainsi, le 44 est comparé à 33. 33 est plus petit que 44. Ces éléments n'ont donc pas besoin d'être échangés.

Maintenant, le tableau est de 33,44,77,11,88.

Encore une fois, l'indice est incrémenté. L'indice est 3 et l'élément actuel est 11. Il est comparé à tous les éléments de gauche. 11 est inférieur à 77, donc ces deux sont échangés. Maintenant, le tableau est de 33,44,11,77,88. En comparant 11 et 44, 11 est inférieur à 44. Donc ces deux sont échangés. Maintenant, les tableaux sont de 33,11,44,77,88. Encore une fois, 11 est comparé à 33. 11 est inférieur à 33, donc ces deux valeurs sont échangées.

Maintenant, le tableau est de 11,33,44,77,88.

L'incrémentation de l'indice fera l'index à 4.  La valeur est 88. Il est supérieur à 77. Donc, il n'y a pas besoin d'échanger. Enfin, le tableau trié est de 11,33,44,77,88.

Figure 01: Exemple de tri d'insertion

La mise en œuvre du type d'insertion est comme ci-dessus. Le tableau initial était de 77,33, 44,11,88. Après le tri, il donne à la sortie 11,33,44,77,88.

Qu'est-ce que le tri de sélection?

Le tri de sélection est un algorithme de tri basé sur la comparaison sur place. Les tableaux sont séparés dans des sections. La partie triée est à l'extrémité gauche. La partie non triée est à la droite. Premièrement, la plus petite valeur doit être trouvée. Ensuite, il est échangé avec l'élément gauche. Maintenant cet élément est dans le tableau trié. Ce processus continue de déplacer la limite du tableau non triée d'un élément vers la droite. L'algorithme de tri de sélection peut être expliqué en utilisant l'exemple suivant.

Par exemple, prenez le tableau initial de 77,33, 44,11,88,22.  Dans cet algorithme de tri, le plus petit du tableau se trouve. Le plus petit élément est 11. Il est échangé avec l'élément dans l'index 0 du tableau.

Maintenant, le tableau est de 11,33,44,77,88,22.

Le plus petit élément est dans l'index 0, donc 11 est maintenant trié. Du reste des éléments, le plus petit est 22. Il est échangé avec le 1^St élément d'index.

Maintenant, le tableau est de 11,22,44,77,88,33.

Les éléments 11 et 22 sont déjà triés. Du reste, la plus petite valeur est de 33. Il est échangé avec le 2^nd élément d'index.

Maintenant, le tableau est de 11,22,33,77,88,44.

Les éléments 11,22 et 33 sont déjà triés. Du reste, la plus petite valeur est 44. Il est échangé avec le 3^rd élément d'index.

Maintenant, le tableau est de 11,22,33,44,88,66.

Les éléments 11,22,33,44 sont déjà triés. Les éléments restants sont 88 et 66. L'élément 66 est échangé avec le 4^e élément d'index.

Maintenant, le tableau est de 11,22,33,44,66,88.

C'est le tableau trié à l'aide de l'algorithme de tri de sélection.

Figure 02: Exemple de tri de sélection

La mise en œuvre du type d'insertion est comme ci-dessus. Le tableau initial était de 77,33, 44,11,88. Après le tri, il donne à la sortie 11,33,44,77,88.

Quelle est la similitude entre le tri de l'insertion et le tri de sélection?

• Le tri d'insertion et le tri de sélection sont des algorithmes de tri.

Quelle est la différence entre le tri et le tri de sélection de l'insertion?

Résumé - Insertion Trier vs trie de sélection 

Parfois, il est nécessaire de trier les données. En informatique, il existe des algorithmes pour trier les données. Cet article a discuté des deux algorithmes de tri qui sont le tri et le tri de sélection de l'insertion. Le tri d'insertion est l'algorithme de tri qui trie le tableau en changeant les éléments un par un. Le tri de sélection est l'algorithme de tri qui trouve le plus petit élément du tableau et échange l'élément avec la première position, puis trouvez le deuxième plus petit élément et l'échangez avec l'élément de la deuxième position et continue le processus jusqu'à ce que le tableau entier soit trié. La différence entre le tri et le tri de sélection de l'insertion est que le tri d'insertion compare deux éléments à la fois tandis que le tri de sélection sélectionne l'élément minimum dans l'ensemble du tableau et le trie.

Téléchargez le tri du PDF de l'insertion vs le tri de sélection

Vous pouvez télécharger la version PDF de cet article et l'utiliser à des fins hors ligne selon la note de citation. Veuillez télécharger la version PDF ici: différence entre le tri de l'insertion et le tri de sélection

Référence:

1.Point, tutoriels. «Tri d'insertion des structures de données et des algorithmes.»Www.tutorielpoint.com, Tutorials Point, 8 janvier. 2018.Disponible ici
2.Tri de sélection dans les structures de données | Tutoriel de structure de données | StudyTonight.  Disponible ici
3.ThéorieApp. «Sélection, insertion et bulle.”TheoryApp, 20 janvier. 2014.  Disponible ici
4.Tri de l'insertion dans les structures de données | Tutoriel de structure de données | StudyTonight.  Disponible ici