Différence entre le tri par insertion et le tri par sélection

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

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. Lors du tri, les données sont classées selon un ordre numérique ou lexicographique. Si les données sont correctement triées, il serait facile de rechercher des 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 alors 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 disposé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 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 dans le tableau et échange l’élément avec la première position, puis trouve le deuxième élément le plus petit, l’échange avec l’élément situé en deuxième position et poursuit le processus jusqu’à ce que tout le tableau soit trié. . le différence clé 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.

CONTENU

1. Vue d'ensemble et différence clé
2. Qu'est-ce que le tri par insertion?
3. Quel est le tri par sélection
4. Similarités entre le tri par insertion et le tri par sélection
5. Comparaison côte à côte - Tri par insertion vs Tri par sélection sous forme de tableau
6. Résumé

Qu'est-ce que le tri par insertion??

Le tri par insertion est un algorithme de tri sur base de comparaison. Dans cette méthode, le tableau est recherché étape par étape. 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, prenons le tableau initial comme 77,33, 44,11,88. Dans cet algorithme de tri, la première étape consiste à sélectionner l'élément en cours.

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 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. Il est maintenant égal à 1 et l'élément actuel à 33. Si vous le comparez à l'élément de gauche, il est inférieur à 77. Ces deux valeurs sont ensuite permutées. Maintenant 33 est dans l'index 0 et 77 dans l'index1.

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

De nouveau, 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 permutées. Maintenant, le tableau est 33,44,77,11,88. Il est nécessaire de comparer tous les éléments à gauche. Donc, le 44 est comparé à 33. 33 est inférieur à 44. Donc, ces éléments ne doivent pas être échangés.

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

De nouveau, l'index est incrémenté. L'indice est 3 et l'élément actuel est 11. Il est comparé à tous les éléments à gauche. 11 est inférieur à 77, donc ces deux sont échangés. Maintenant, le tableau est 33,44,11,77,88. Quand on compare 11 et 44, 11 est inférieur à 44. Ces deux personnes sont donc permutées. 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'indice à 4. La valeur est 88. Il est supérieur à 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 d'insertion

La mise en œuvre 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.

Quel est 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 les limites d'un tableau non trié d'un élément vers la droite. L'algorithme de tri de sélection peut être expliqué à l'aide de l'exemple suivant.

Par exemple, prenons le tableau initial sous la forme 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é. 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 11,22,44,77,88,33.

Les éléments 11 et 22 sont déjà triés. Parmi les autres, la plus petite valeur est 33. Elle est permutée avec le 2^{Dakota du Nord} élément d'index.

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

Les éléments 11,22 et 33 sont déjà triés. Parmi les autres, la plus petite valeur est 44. Elle est permutée avec le 3^rd élément d'index.

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 échangé avec le 4^th élément d'index.

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

C'est le tableau trié en utilisant l'algorithme de tri par sélection.

Figure 02: Exemple de tri de sélection

La mise en œuvre 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 tous deux 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 dans le tableau et échange l’élément avec la première position, puis trouve le deuxième élément le plus petit, l’échange avec l’élément situé en deuxième position et poursuit le processus jusqu’à ce que tout le tableau soit 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électionne à nouveau le minimum pour le reste et permute entre la deuxième position et poursuit 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é - Insertion Trier vs sélection Trier 

Parfois, il est nécessaire de trier les données. En informatique, il existe des algorithmes pour trier les données. Cet article a présenté les 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 dans le tableau et échange l’élément avec la première position, puis trouve le deuxième élément le plus petit, l’échange avec l’élément situé en deuxième position et poursuit le processus jusqu’à ce que tout le tableau 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écharger 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

Référence:

1.Point, tutoriels. «Tri d'insertion des structures de données et des algorithmes». Www.tutorialspoint.com, Point sur les tutoriels, 8 janvier 2018.Disponible ici
2.Trier de sélection dans les structures de données | Didacticiel sur la structure de données | Studytonight.  Disponible ici
3.Theoryapp. «Sélection, insertion et tri de bulles». TheoryApp, 20 janvier 2014.  Disponible ici
4.Triage par insertion dans les structures de données | Didacticiel sur la structure de données | Studytonight.  Disponible ici