Tri par insertion et tri par sélection

J'essaie de comprendre les différences entre le tri par insertion et le tri par sélection.

Ils semblent tous deux avoir deux composants: une liste non triée et une liste triée. Ils semblent tous les deux prendre un élément de la liste non triée et le mettre dans la liste triée au bon endroit. J'ai vu certains sites / livres dire que le tri par sélection le fait en échangeant un à la fois tandis que le tri par insertion trouve simplement le bon endroit et l'insère. Cependant, j'ai vu d'autres articles dire quelque chose, disant que le tri d'insertion change également. Par conséquent, je suis confus. Existe-t-il une source canonique?

Tri de sélection:

Étant donné une liste, prenez l'élément courant et échangez-le avec le plus petit élément à droite de l'élément courant.

Tri par insertion:

Étant donné une liste, prenez l'élément actuel et insérez-le à la position appropriée de la liste, en ajustant la liste à chaque fois que vous l'insérez. Cela revient à organiser les cartes dans un jeu de cartes.

La complexité temporelle du tri par sélection est toujours n(n - 1)/2, alors que le tri par insertion a une meilleure complexité temporelle que son pire cas n(n - 1)/2. Généralement, il faudra alors des comparaisons moindres ou égales n(n - 1)/2.

Source: http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html

Le tri par insertion et le tri par sélection ont une boucle externe (sur chaque index) et une boucle interne (sur un sous-ensemble d'indices). Chaque passage de la boucle interne étend la région triée d'un élément, aux dépens de la région non triée, jusqu'à ce qu'elle soit à court d'éléments non triés.

La différence réside dans ce que fait la boucle interne:

• Dans le tri par sélection, la boucle interne se trouve sur les éléments non triés . Chaque passe sélectionne un élément et le déplace vers son emplacement final (à la fin actuelle de la région triée).

• Dans le tri par insertion, chaque passage de la boucle interne itère sur les éléments triés . Les éléments triés sont déplacés jusqu'à ce que la boucle trouve le bon emplacement pour insérer l'élément non trié suivant.

Ainsi, dans un tri par sélection, les éléments triés sont trouvés dans l'ordre de sortie et restent en place une fois qu'ils sont trouvés. Inversement, dans un tri par insertion, le non trié éléments restent en place jusqu'à ce qu'ils soient consommés dans l'ordre d'entrée, tandis que les éléments de la région triée continuent à se déplacer.

En ce qui concerne l'échange: le tri par sélection effectue un échange par passage de la boucle interne. Le tri par insertion enregistre généralement l'élément à insérer comme temp avant la boucle interne, laissant la place à la boucle interne pour décaler les éléments triés vers le haut de un, puis les copie tempvers le point d'insertion par la suite.

SÉLECTION TRIER
Supposons qu'il y ait un tableau de nombres écrits d'une manière particulière / aléatoire et disons que nous devons les organiser par ordre croissant ... alors, prenez un nombre à la fois et remplacez-les par le plus petit non. disponible dans la liste. en faisant cette étape, nous obtiendrons finalement le résultat souhaité.

TRI D'INSERTION
En gardant à l'esprit l'hypothèse similaire, mais la seule différence est que cette fois, nous sélectionnons un nombre à la fois et l'insérons dans la partie pré-triée, ce qui réduit les comparaisons et donc est plus efficace.

Il est possible que la confusion soit due au fait que vous comparez une description du tri d'une liste liée avec une description du tri d'un tableau . Mais je ne peux pas être sûr, puisque vous n'avez pas cité vos sources.

Le moyen le plus simple de comprendre les algorithmes de tri est souvent d'obtenir une description détaillée de l'algorithme (pas des choses vagues comme "ce tri utilise swap. Quelque part. Je ne dis pas où"), obtenir des cartes à jouer (5-10 devraient suffire pour les algorithmes de tri simples) et exécutez l'algorithme à la main.

Tri par sélection: parcourez les données non triées à la recherche du plus petit élément restant, puis échangez-le dans la position qui suit immédiatement les données triées. Répétez jusqu'à ce que vous ayez terminé. Si vous triez une liste, vous n'avez pas besoin de permuter le plus petit élément en position, vous pouvez à la place supprimer le nœud de liste de son ancienne position et l'insérer au nouveau.

Tri par insertion: prenez l'élément qui suit immédiatement les données triées, parcourez les données triées pour trouver l'endroit où le mettre et placez-le là. Répétez jusqu'à ce que vous ayez terminé.

Le tri par insertion peut utiliser swap pendant sa phase "scan", mais ce n'est pas obligatoire et ce n'est pas le moyen le plus efficace à moins que vous ne triiez un tableau d'un type de données qui: (a) ne peut pas être déplacé, seulement copié ou échangé; et (b) est plus coûteux à copier qu'à échanger. Si le tri par insertion utilise le swap, la façon dont cela fonctionne est que vous recherchez simultanément le lieu et y placez le nouvel élément, en échangeant à plusieurs reprises le nouvel élément avec l'élément immédiatement avant, tant que l'élément avant est plus grand que il. Une fois que vous atteignez un élément qui n'est pas plus grand, vous avez trouvé le bon emplacement et vous passez au nouvel élément suivant.

La logique des deux algorithmes est assez similaire. Ils ont tous deux un sous-tableau partiellement trié au début du tableau. La seule différence est la manière dont ils recherchent l'élément suivant à placer dans le tableau trié.

• Tri par insertion : insère l'élément suivant à la bonne position;

• Tri par sélection : sélectionne le plus petit élément et l'échange avec l'élément courant;

De plus, le tri par insertion est stable, contrairement au tri par sélection .

J'ai implémenté les deux en python, et il convient de noter à quel point ils sont similaires:

def insertion(data):
    data_size = len(data)
    current = 1
    while current < data_size:
        for i in range(current):
            if data[current] < data[i]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

Avec un petit changement, il est possible de faire l'algorithme de tri par sélection.

def selection(data):
    data_size = len(data)
    current = 0
    while current < data_size:
        for i in range(current, data_size):
            if data[i] < data[current]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

En un mot, je pense que le tri de sélection recherche d'abord la plus petite valeur du tableau, puis effectue l'échange alors que le tri par insertion prend une valeur et la compare à chaque valeur qui lui reste (derrière). Si la valeur est inférieure, elle change. Ensuite, la même valeur est à nouveau comparée et si elle est inférieure à celle qui se trouve derrière elle, elle échange à nouveau. J'espère que cela à du sens!

En bref,

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

Tri par insertion: il est opposé au tri par sélection où il sélectionne le premier élément du sous-tableau non trié et le compare avec le sous-tableau trié et insère le plus petit élément où il a été trouvé et déplace tous les éléments triés de sa droite vers le premier élément non trié.

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

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

Tri par insertion - choisissez le premier élément non trié et essayez de lui trouver une place parmi la partie déjà triée. Puisque vous effectuez une recherche de droite à gauche, il peut très bien arriver que le premier élément trié auquel vous comparez (le plus grand, le plus à droite dans la partie gauche) soit plus petit que l'élément sélectionné afin que vous puissiez immédiatement continuer 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 si vous le souhaitez. Le problème est que, puisque la bonne partie n'est pas triée, vous devez réfléchir à chaque élément à chaque fois, car vous ne pouvez pas être sûr qu'il existe ou non un élément même plus petit que celui choisi.

Btw., C'est exactement ce que le tri de tas améliore le tri par sélection - il est capable de trouver le plus petit élément beaucoup plus rapidement à cause du tas .

Tri par sélection: lorsque vous commencez à créer la sous-liste triée, l'algorithme garantit que la sous-liste triée est toujours complètement triée, non seulement en termes de ses propres éléments, mais également en termes de tableau complet, c'est-à-dire à la fois sous-liste triée et non triée. Ainsi, le nouvel élément le plus petit une fois trouvé dans la sous-liste non triée serait simplement ajouté à la fin de la sous-liste triée.

Tri par insertion: l'algorithme divise à nouveau le tableau en deux parties, mais ici l'élément est sélectionné dans la deuxième partie et inséré à la bonne position dans la première partie. Cela ne garantit jamais que la première partie est triée en fonction du tableau complet, bien que, bien entendu, lors de la passe finale, chaque élément soit à sa position de tri correcte.

Les deux algorithmes fonctionnent généralement comme ceci

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

Étape 2: placez-le au bon endroit dans la liste triée.

L'une des étapes est plus simple pour un algorithme et vice versa.

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

Tri par sélection : nous emportons l'élément quelque part dans la liste non triée, puis nous le plaçons à la dernière position de la liste triée. Nous devons trouver l'élément suivant (il ne se trouve probablement pas dans la première position de la liste non triée, mais plutôt quelque part ), puis le placer juste à la fin de la liste triée. L'étape 2 est simple

La boucle interne du tri d'insertion passe par des éléments déjà triés (contrairement au tri par sélection). Cela lui permet d' interrompre la boucle interne lorsque la bonne position est trouvée . Ce qui signifie que:

1. La boucle intérieure ne passera que par la moitié de ses éléments dans un cas moyen.
2. La boucle interne sera abandonnée encore plus tôt si le tableau est presque trié.
3. La boucle interne s'interrompra immédiatement si le tableau est déjà trié, ce qui rend la complexité du tri par insertion linéaire dans ce cas.

Le tri de sélection devra toujours passer par tous les éléments de la boucle interne. C'est pourquoi le tri par insertion est le plus souvent préféré au tri par sélection. Mais, d'un autre côté, le tri par sélection effectue beaucoup moins de permutations d'éléments, ce qui peut être plus important dans certains cas.

Fondamentalement, le tri par insertion fonctionne en comparant deux éléments à la fois et le tri par sélection sélectionne l'élément minimum dans l'ensemble du tableau et le trie.

Conceptuellement, le tri par insertion continue de trier la sous-liste en comparant deux éléments jusqu'à ce que le tableau entier soit trié tandis que le tri par sélection sélectionne l'élément minimum et le permute vers la première position, deuxième élément minimum vers la deuxième position et ainsi de suite.

Le tri par insertion peut être affiché comme suit:

    for(i=1;i<n;i++)
        for(j=i;j>0;j--)
            if(arr[j]<arr[j-1])
                temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;

Le tri de sélection peut être affiché comme suit:

    for(i=0;i<n;i++)
        min=i;
        for(j=i+1;j<n;j++)
        if(arr[j]<arr[min])
        min=j;
        temp=arr[i];
        arr[i]=arr[min];
        arr[min]=temp;

Le choix de ces 2 algorithmes de tri se résume à la structure de données utilisée.

Lorsque vous utilisez des tableaux, utilisez le tri par sélection (mais pourquoi, quand pouvez-vous utiliser qsort?). Lorsque vous utilisez des listes liées, utilisez le tri par insertion.

Ceci est dû au fait:

• La traversée de liste liée est plus coûteuse que les tableaux.
• L'insertion de liste liée est beaucoup moins chère que 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 tournant 2 pointeurs, vous avez effectivement repoussé toute la liste. Dans un tableau, vous devez effectuer n - i swaps pour repousser les valeurs, ce qui peut être très coûteux.

Le tri de sélection s'ajoute toujours à la fin, il n'y a donc pas ce problème lors de l'utilisation de tableaux. Par conséquent, les données n'ont pas besoin d'être «repoussées».

Une explication simple pourrait être comme ci-dessous:

Donné : Un tableau ou une liste de nombres non triés.

Énoncé du problème : pour trier la liste / le tableau de nombres par ordre croissant pour comprendre la différence entre le tri par sélection et le tri par insertion.

Tri par insertion:Vous voyez la liste de haut en bas pour une compréhension plus facile. Nous considérons le premier élément comme notre valeur minimale initiale. Maintenant, l'idée est que nous parcourons chaque index de cette liste / tableau de manière linéaire pour savoir s'il existe un autre élément à un index qui a une valeur inférieure à la valeur minimale initiale. Si nous trouvons une telle valeur, nous échangeons simplement les valeurs à leurs index, c'est-à-dire que 15 était la valeur initiale minimale à l'index 1 et lors du parcours linéaire des index, nous rencontrons un nombre avec une valeur moindre, disons 7 à l'index 9 Maintenant, cette valeur 7 à l'index 9 est permutée avec l'index 1 ayant 15 comme valeur. Ce parcours continuera à faire la comparaison avec la valeur de l'index actuel avec les index restants à échanger pour la valeur la plus petite. Cela continue jusqu'à l'avant-dernier index de la liste / tableau,

Tri de sélection:Supposons que le premier élément d'index de la liste / du tableau soit trié. Maintenant, à partir de l'élément au deuxième index, nous le comparons avec son index précédent pour voir si la valeur est plus petite. Le parcours peut être visualisé en deux parties, triées et non triées. La première consisterait à visualiser une vérification de comparaison du non trié vers le trié pour un index donné dans la liste / tableau. Supposons que vous ayez la valeur 19 à l'index 1 et la valeur 10 à l'index 3. Nous considérons la traversée du non trié vers le trié, c'est-à-dire de droite à gauche. Donc, disons que nous devons trier à l'index 3. Nous voyons qu'il a une valeur inférieure à l'indice 1 lorsque nous comparons de droite à gauche. Une fois identifié, nous plaçons simplement ce numéro 10 de l'indice 3 à la place de l'indice 1 ayant la valeur 19. La valeur d'origine 19 à l'indice 1 est décalée d'une place vers la droite.

Je n'ai ajouté aucun code car la question semble sur la compréhension du concept de la méthode de traversée.

Le tri par insertion n'échange pas les choses. Même s'il utilise une variable temporaire, l'intérêt d'utiliser temp var est que lorsque nous avons trouvé une valeur à un index inférieure à la valeur de son index précédent, nous déplaçons la valeur la plus élevée à la place de la valeur la plus petite. index qui écraserait les choses. Ensuite, nous utilisons la variable temp pour être substituée à l'index précédent. Exemple: 10, 20, 30, 50, 40. itération 1: 10, 20, 30, 50, 50. [temp = 40] itération 2: 10,20, 30, 40 (valeur de temp), 50. Donc, nous insérez simplement une valeur à la position souhaitée à partir d'une variable.

Mais lorsque nous considérons le tri par sélection, nous trouvons d'abord l'index ayant une valeur inférieure et échangeons cette valeur avec la valeur du premier index et continuons à échanger à plusieurs reprises jusqu'à ce que tous les indices soient triés. C'est exactement la même chose que l'échange traditionnel de deux nombres. Exemple: 30, 20, 10, 40, 50. Itération 1: 10, 20, 30, 40, 50. Ici, temp var est utilisé exclusivement pour l'échange.

Le tri par insertion permet beaucoup plus d'échanger cette sélection. Voici un exemple:

Ce qu'ils ont tous les deux en commun, c'est qu'ils utilisent tous les deux une partition pour différencier la partie triée du tableau de la partie non triée.

La différence est qu'avec le tri par sélection, vous êtes assuré que la partie triée du tableau ne changera pas lors de l'ajout d'éléments à la partition triée.

La raison en est que la sélection recherche le minimum de l'ensemble non trié et l'ajoute juste après le dernier élément de l'ensemble trié, augmentant ainsi l'ensemble trié de 1.

L'insertion, d'autre part, ne se soucie que de l'élément suivant rencontré, qui est le premier élément de la partie non triée du tableau. Il prendra cet élément et le mettra simplement à sa place dans l'ensemble trié.

Le tri par insertion sera généralement toujours un meilleur candidat pour les tableaux qui ne sont triés que partiellement, car vous gaspillez des opérations pour trouver le minimum.

Conclusion:

Le tri par sélection ajoute de manière incrémentielle un élément à la fin en recherchant l'élément minimum dans la section non triée.

Le tri par insertion propage le premier élément trouvé dans la section non triée n'importe où dans la section triée.

Bien que la complexité temporelle du tri par sélection et du tri par insertion soit la même, c'est n (n - 1) / 2. Le tri d'insertion de performance moyenne est meilleur. Testé sur mon processeur i5 avec 30000 entiers aléatoires, le tri par sélection a pris 1,5 s en moyenne, tandis que le tri par insertion prend 0,6 s en moyenne.

En termes simples, (et probablement le moyen le plus simple d'atteindre une compréhension de haut niveau du problème)

Le tri à bulles est similaire à se tenir en ligne et à essayer de se trier par hauteur. Vous continuez à changer avec la personne à côté de vous jusqu'à ce que vous soyez au bon endroit. Cela a lieu tout le chemin de la gauche (ou de la droite selon l'implémentation) et vous continuez à changer jusqu'à ce que tout le monde soit trié.

Dans le tri par sélection, cependant, ce que vous faites est similaire à l'organisation d'une main de cartes. Vous regardez les cartes, prenez la plus petite, placez-la complètement à gauche, et ainsi de suite.

selection -sélectionner un élément particulier (le plus bas) et l'échanger avec le i (pas d'itération) e élément. (c'est-à-dire, premier, deuxième, troisième .......) d'où la liste triée d'un côté.

insertion - comparer le premier avec le deuxième comparer le troisième avec le deuxième et le premier comparer le quatrième avec le troisième, le deuxième et le premier ......

un lien où tous les triages sont comparés