Différence Entre Le Tri Par Insertion Et Le Tri Par Sélection

2024 Auteur: Mildred Bawerman | [email protected]. Dernière modifié: 2023-12-16 08:38

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 pour trier un ensemble de données. Lors du tri, les données sont disposées selon un ordre numérique ou lexicographique. Si les données sont triées correctement, il serait alors facile de rechercher des données plus rapidement. Si les numéros de téléphone d'un annuaire 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 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 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 trouve le deuxième élément le plus petit 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.puis trouvez le deuxième plus petit élément et échangez-le avec l'élément en deuxième position et continuez 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.puis trouvez le deuxième plus petit élément et échangez-le avec l'élément en deuxième position et continuez 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.

CONTENU

1. Présentation et différence clé

2. Qu'est-ce que le tri par insertion

3. Qu'est-ce que le tri par sélection

4. Similitudes 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 tabulaire

6. Résumé

Qu'est-ce que le tri par insertion?

Le tri par insertion est un algorithme de tri basé sur une comparaison sur place. 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, prenez le tableau initial comme 77,33, 44,11,88. Dans cet algorithme de tri, la première étape consiste à sélectionner l'élément courant.

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'indice de la position actuelle est incrémenté de 1. L'index est maintenant 1 et l'élément actuel est 33. Lorsque vous le comparez avec l'élément de gauche, il est inférieur à 77. Ensuite, ces deux valeurs sont permutées. Maintenant 33 est dans l'index 0 et 77 est dans l'index1.

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

Là encore, 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. Le tableau est maintenant 33,44,77,11,88. Il est nécessaire de comparer tous les éléments sur la gauche. Ainsi, le 44 est comparé à 33. 33 est plus petit que 44. Donc, ces éléments n'ont pas besoin d'être échangés.

Le tableau est maintenant 33,44,77,11,88.

Là encore, l'index est incrémenté. L'index est 3 et l'élément courant est 11. Il est comparé à tous les éléments de gauche. 11 est inférieur à 77, donc ces deux sont échangés. Le tableau est maintenant 33,44,11,77,88. Lorsque l'on compare 11 et 44, 11 est inférieur à 44. Donc, ces deux sont échangés. Maintenant, les tableaux sont 33,11,44,77,88. Là encore, 11 est comparé à 33. 11 est inférieur à 33, donc ces deux valeurs sont permutées.

Le tableau est maintenant 11,33,44,77,88.

L'incrémentation de l'index rendra 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

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.

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

Le tri par sélection est un algorithme de tri basé sur une comparaison sur place. Les tableaux sont séparés en sections. La partie triée se trouve à 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 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.

Le tableau est maintenant 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 le 1 ^er élément d'index.

Le tableau est maintenant 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 le 2 ^ème élément d'index.

Le tableau est maintenant 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 le 3 ^ème é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 ^ème élément de l' index.

Le tableau est maintenant 11,22,33,44,66,88.

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

Figure 02: Exemple de tri par 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 des algorithmes de tri

Quelle est la différence entre le tri par insertion et le tri par sélection?

Diff article au milieu avant la table

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 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 trouve le deuxième élément le plus petit et l'échange avec l'élément en deuxième position et continue le processus jusqu'à ce que le tableau entier 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 de 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 avec 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 décrit 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 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 trouve le deuxième élément le plus petit 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