Triage par insertion vs. Tri par sélection

Question

Je cherche à comprendre les différences entre le tri par insertion et le tri par sélection.

Il semble qu'ils aient tous les deux deux composants : une sous-liste non triée et une sous-liste triée. Il semble qu'ils prennent tous les deux un élément de la sous-liste non triée et le placent dans la liste triée à la bonne place. J'ai vu certains sites/livres dire que le tri par sélection le fait en échangeant une paire d'éléments à la fois tandis que le tri par insertion trouve simplement le bon emplacement et l'insère. Cependant, j'ai vu d'autres articles dire quelque chose de différent, en disant que le tri par insertion fait également des échanges. En conséquence, je suis confus. Y a-t-il une source canonique?

Answer 1

En bref,

Tri par sélection : Sélectionnez le premier élément du tableau non trié et comparez-le aux autres éléments non triés. Il est similaire au tri à bulles, mais au lieu d'échanger chaque élément plus petit, garde l'indice de l'élément le plus petit mis à jour et l'échange à la fin de chaque boucle.

Tri par insertion : C'est le contraire du tri par sélection où il choisit le premier élément de la sous-array non triée et le compare avec la sous-array triée et insère l'élément le plus petit là où il est trouvé et décale tous les éléments triés de sa droite vers le premier élément non trié.

Answer 2

Les deux algorithmes fonctionnent généralement de cette manière

Étape 1: prendre le prochain élément non trié de la liste non triée puis

Étape 2: le mettre à la bonne place dans la liste triée.

Une des étapes est plus facile pour un algorithme et vice versa.

Tri par insertion: Nous prenons le premier élément de la liste non triée, le mettons dans la liste triée, quelque part. Nous savons où prendre le prochain élément (la première position dans la liste non triée), mais cela nécessite un peu de travail pour trouver où le mettre (quelque part). L'étape 1 est facile.

Tri par sélection: Nous prenons l'élément quelque part de la liste non triée, puis le mettons à la dernière position de la liste triée. Nous devons trouver le prochain élément (il est très probablement pas dans la première position de la liste non triée, mais plutôt, quelque part) puis le mettre tout de suite à la fin de la liste triée. L'étape 2 est facile.

Answer 3

Le choix de ces 2 algorithmes de tri dépend de la structure de données utilisée.

Lorsque vous utilisez des tableaux, utilisez le tri par sélection (bien que pourquoi, quand vous pouvez utiliser qsort?). Lorsque vous utilisez des listes chaînées, utilisez le tri par insertion.

Cela est dû à :

• Le parcours des listes chaînées est plus coûteux que celui des tableaux.
• L'insertion dans une liste chaînée est bien moins chère que dans les tableaux.

Le tri par insertion injecte la nouvelle valeur au milieu du segment trié. Par conséquent, les données doivent être "repoussées". Cependant, lorsque vous utilisez une liste chaînée, en tordant 2 pointeurs, vous avez effectivement repoussé toute la liste en arrière. Dans un tableau, vous devez effectuer n - i échanges pour repousser les valeurs, ce qui peut être très coûteux.

Le tri par sélection ajoute toujours à la fin, alors il n'a pas ce problème lorsque vous utilisez des tableaux. Par conséquent, les données n'ont pas besoin d'être "repoussées".

Answer 4

En résumé, je pense que le tri par sélection recherche d'abord la plus petite valeur dans le tableau, puis effectue l'échange, tandis que le tri par insertion prend une valeur et la compare à chaque valeur qui lui reste (derrière elle). Si la valeur est plus petite, elle est échangée. Ensuite, la même valeur est à nouveau comparée et si elle est plus petite que celle qui est derrière, un nouvel échange est effectué. J'espère que cela a du sens!

Answer 5

Je vais essayer une fois de plus : considérons ce qui se passe dans le cas chanceux d'un tableau presque trié.

Pendant le tri, le tableau peut être considéré comme ayant deux parties : le côté gauche - trié, le côté droit - non trié.

Tri par insertion - choisissez d'abord l'élément non trié et essayez de trouver une place pour lui parmi la partie déjà triée. Comme vous cherchez de droite à gauche, il se peut très bien que le premier élément trié que vous comparez (le plus grand, le plus à droite dans la partie gauche) soit plus petit que l'élément choisi, vous pouvez donc continuer immédiatement avec le prochain élément non trié.

Tri par sélection - choisissez le premier élément non trié et essayez de trouver le plus petit élément de toute la partie non triée, et échangez les deux si nécessaire. Le problème est, comme la partie droite est non triée, vous devez passer par chaque élément à chaque fois, car vous ne pouvez pas être sûr s'il y a ou non un élément encore plus petit que celui choisi.

À propos, c'est exactement ce sur quoi heapsort s'améliore par rapport au tri par sélection - il est capable de trouver le plus petit élément bien plus rapidement grâce au tas.