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

Tri par sélection : Lorsque vous commencez à construire 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 aussi par rapport au tableau complet, c'est-à-dire à la fois la 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 choisi dans la deuxième partie et inséré à la position correcte dans la première partie. Cela ne garantit jamais que la première partie est triée par rapport au tableau complet, bien sûr dans le dernier passage chaque élément est à sa position correcte triée.

Answer 2

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 de tout le tableau et le trie.

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

Le tri par insertion peut être représenté comme suit :

    pour(i=1;i0;j--)
            si(arr[j]

`

Le tri par sélection peut être représenté comme suit :

    pour(i=0;i

`

Answer 3

La boucle interne du tri par insertion parcourt les éléments déjà triés (contrairement au tri par sélection). Cela lui permet de interrompre la boucle interne une fois que la bonne position est trouvée. Ce qui signifie que :

1. La boucle interne parcourra seulement la moitié de ses éléments en moyenne.
2. La boucle interne sera interrompue 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é, rendant la complexité du tri par insertion linéaire dans ce cas.

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

Answer 4

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

Answer 5

À la fois le tri par insertion et le tri par sélection ont une liste triée au début et une liste non triée à la fin, et ce que fait l'algorithme est également similaire :

1. Prendre un élément de la liste non triée
2. Le placer dans la liste triée

La différence est :

• Tri par insertion prend le premier élément de la liste non triée, puis compare et échange dans la liste triée pour s'assurer que l'élément se trouve à la bonne position, l'effort est principalement dans l'étape n°2 pour l'insertion

auto insertion_sort(vector& vs)
{
  for(int i=1; i < vs.size(); ++i)
  {
    for(int j=i; j > 0; --j)
    {
      if(vs[j] < vs[j-1]) swap(vs[j], vs[j-1]);
    }
  }
  return vs;
}

• Tri par sélection compare et marque l'élément le plus petit de la liste non triée, puis l'échange avec le premier élément de la liste non triée, incluant en fait cet élément comme partie de la liste triée - l'effort est principalement dans l'étape n°1 pour la sélection

auto selection_sort(vector& vs)
{
  for(int i = 0; i < vs.size(); ++i)
  {
    int iMin = i;
    for(int j=i; j < vs.size(); ++j)
    {
      if(vs[j] < vs[iMin]) iMin = j;
    }
    swap(vs[i], vs[iMin]);
  }
  return vs;
}