Différence clé - Tri par insertion vs Tri par sélection
Le tri par insertion et le tri par sélection sont deux algorithmes de tri utilisés pour trier une collection de données. Parfois, il est nécessaire d'organiser les données dans un ordre spécifique. Les algorithmes de tri sont des mécanismes permettant de trier un ensemble de données. Dans le tri, les données sont rangées selon un ordre numérique ou lexicographique. Si les données sont triées correctement, il serait facile de rechercher des données plus rapidement. Si les numéros de téléphone dans un annuaire 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 classés par 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 par insertion et le tri par sélection. Le tri par insertion est l'algorithme de tri qui trie le tableau en décalant les éléments un par un. Le tri par 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 trouve le deuxième plus petit élément et l'échange avec l'élément en deuxième position et continue le processus jusqu'à ce que le tableau entier soit trié. La principale différence entre le tri par insertion et le tri par sélection est que le tri par insertion compare deux éléments à la fois, tandis que le tri par sélection sélectionne l'élément minimum dans l'ensemble du tableau et le trie.
Qu'est-ce que le tri par insertion ?
Le tri par insertion est un algorithme de tri basé sur la comparaison sur place. Dans cette méthode, le tableau est parcouru pas à pas. Les éléments non triés sont déplacés et insérés dans la sous-liste triée du tableau. L'algorithme de tri par insertion peut être expliqué à l'aide de l'exemple suivant.
Par exemple, prenez le tableau initial sous la forme 77, 33, 44, 11, 88. Dans cet algorithme de tri, la première étape consiste à sélectionner l'élément actuel.
L'élément courant est 77. L'élément courant est comparé à tous les éléments du côté gauche. Le 77, est le premier élément et il n'y a aucun élément sur le côté gauche. L'index de la position actuelle est 0.
Ensuite, l'index de la position actuelle est incrémenté de 1. Maintenant, l'index est 1 et l'élément actuel est 33. En le comparant avec l'élément de gauche, il est inférieur à 77. Alors ces deux valeurs sont échangés. Maintenant 33 est dans l'index 0, et 77 est dans l'index1.
Maintenant, le tableau est 33, 77, 44, 11, 88.
Encore une fois, l'index 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. Ces deux valeurs sont donc échangées. Maintenant, le tableau est 33, 44, 77, 11, 88. Il est nécessaire de comparer tous les éléments de 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 33, 44, 77, 11, 88.
Encore une fois, l'index 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 33, 44, 11, 77, 88. Lorsque l'on compare 11 et 44, 11 est inférieur à 44. Donc, ces deux sont permutés. Maintenant, les tableaux sont 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 11, 33, 44, 77, 88.
Incrémenter l'index fera passer l'index à 4. La valeur est 88. Elle est supérieure à 77. Il n'est donc pas nécessaire de permuter. Enfin, le tableau trié est 11, 33, 44, 77, 88.
Figure 01: Exemple de tri par insertion
L'implémentation du tri par insertion est comme ci-dessus. Le tableau initial était 77, 33, 44, 11, 88. Après le tri, il donne la sortie 11, 33, 44, 77, 88.
Qu'est-ce que le tri par sélection ?
Le tri par sélection est un algorithme de tri basé sur la comparaison sur place. Les tableaux sont divisés en sections. La partie triée est à l'extrémité gauche. La partie non triée est à l'extrémité droite. Tout d'abord, la plus petite valeur doit être trouvée. Ensuite, il est échangé avec l'élément de gauche. Maintenant, cet élément est dans le tableau trié. Ce processus continue de déplacer la limite de tableau non triée d'un élément vers la droite. L'algorithme de tri par sélection peut être expliqué à l'aide de l'exemple suivant.
Par exemple, prenez le tableau initial comme 77, 33, 44, 11, 88, 22. Dans cet algorithme de tri, le plus petit du tableau est trouvé. Le plus petit élément est 11. Il est échangé avec l'élément dans l'index 0 du tableau.
Maintenant, le tableau est 11, 33, 44, 77, 88, 22.
Le plus petit élément est dans l'index 0, donc 11 est maintenant trié. Parmi les autres éléments, le plus petit est 22. Il est remplacé par l'élément d'index 1st.
Maintenant, le tableau est 11, 22, 44, 77, 88, 33.
Les éléments 11 et 22 sont déjà triés. Du reste, la plus petite valeur est 33. Elle est échangée avec l'élément d'index 2nd.
Maintenant, le tableau est 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. Elle est échangée avec l'élément d'index 3rd.
Maintenant, le tableau est 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 remplacé par l'élément d'index 4th.
Maintenant, le tableau est 11, 22, 33, 44, 66, 88.
C'est le tableau trié utilisant l'algorithme de tri par sélection.
Figure 02: Exemple de tri de sélection
L'implémentation du tri par insertion est comme ci-dessus. Le tableau initial était 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 par insertion et le tri par sélection ?
Le tri par insertion et le tri par sélection sont des algorithmes de tri
Quelle est la différence entre le tri par insertion et le tri par sélection ?
Tri par insertion vs Tri par sélection |
|
| Le tri par insertion est l'algorithme de tri qui trie le tableau en décalant les éléments un par un. | Le tri par 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 trouve le deuxième plus petit élément et l'échange avec l'élément en deuxième position et continue le processus jusqu'à le tableau entier est trié. |
| Processus | |
| Le tri par insertion consiste à trier la sous-liste en comparant deux éléments jusqu'à ce que tout le tableau soit trié. | Le tri par sélection sélectionne l'élément minimum et l'échange avec la première position, sélectionnez à nouveau le minimum pour le reste et échangez-le vers la deuxième position et continuez ce processus jusqu'à la fin. |
| Stabilité | |
| Le tri par insertion est un algorithme de tri stable. | Le tri par sélection n'est pas un algorithme de tri stable. |
Résumé - Tri par insertion vs Tri par 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 par insertion et le tri par sélection. Le tri par insertion est l'algorithme de tri qui trie le tableau en décalant les éléments un par un. Le tri par 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 trouve le deuxième plus petit élément et l'échange avec l'élément en deuxième position et continue le processus jusqu'à ce que le tableau entier soit trié. La différence entre le tri par insertion et le tri par sélection est que le tri par insertion compare deux éléments à la fois tandis que le tri par sélection sélectionne l'élément minimum dans l'ensemble du tableau et le trie.
Téléchargez le PDF de Tri par insertion vs Tri par sélection
Vous pouvez télécharger la version PDF de cet article et l'utiliser à des fins hors ligne conformément à la note de citation. Veuillez télécharger la version PDF ici: Différence entre le tri par insertion et le tri par sélection
