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

Trier par sélection :

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

Trier 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 insertion. C'est similaire à arranger les cartes dans un jeu de cartes.

La complexité temporelle du tri par sélection est toujours n(n - 1)/2, tandis que le tri par insertion a une meilleure complexité temporelle car son pire cas de complexité est n(n - 1)/2. En général, il effectuera un nombre inférieur ou égal de comparaisons que n(n - 1)/2.

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

Answer 2

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 agrandit la région triée d'un élément, au détriment de la région non triée, jusqu'à épuisement des éléments non triés.

La différence se situe dans ce que fait la boucle interne:

• Dans le tri par sélection, la boucle interne porte sur les éléments non triés. À chaque passage, un élément est sélectionné et déplacé à sa position finale (à l'extrémité 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 la place correcte pour insérer le prochain élément non trié.

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 trouvés. En revanche, dans un tri par insertion, les éléments non triés 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 d'être déplacés.

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

Answer 3

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

TRI PAR INSERTION
En gardant à l'esprit la même hypothèse mais la seule différence est que cette fois, nous sélectionnons un nombre à la fois et le plaçons dans la partie pré-triée, ce qui réduit les comparaisons et est donc plus efficace.

Answer 4

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

La manière la 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 un échange. Quelque part. Je ne dis pas où"), prendre quelques cartes à jouer (5-10 devraient suffire pour les algorithmes de tri simples), et exécuter l'algorithme manuellement.

Tri par sélection: parcourir les données non triées à la recherche du plus petit élément restant, puis le placer à la position immédiatement après les données triées. Répéter jusqu'à ce que ce soit fini. Si vous triez une liste, vous n'avez pas besoin d'échanger le plus petit élément à sa position, vous pourriez plutôt retirer le nœud de la liste de sa vieille position et l'insérer à la nouvelle.

Tri par insertion: prendre l'élément immédiatement après les données triées, parcourir les données triées pour trouver l'endroit où le placer, et le mettre là. Répéter jusqu'à ce que ce soit fini.

Le tri par insertion peut utiliser un échange pendant sa phase de "balayage", mais ce n'est pas nécessaire et ce n'est pas la façon la plus efficace à moins que vous triez 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 un échange, la manière dont il fonctionne est que vous recherchez simultanément l'endroit et placez le nouvel élément là-bas, en échangeant à plusieurs reprises le nouvel élément avec l'élément immédiatement avant lui, tant que l'élément avant lui est plus grand que lui. Une fois que vous atteignez un élément qui n'est pas plus grand, vous avez trouvé l'emplacement correct et passez au prochain nouvel élément.

Answer 5

La logique des deux algorithmes est assez similaire. Ils ont tous les deux un sous-tableau partiellement trié au début du tableau. La seule différence est la façon dont ils cherchent l'élément suivant à mettre dans le tableau trié.

• Tri par insertion : insère le prochain élément à la position correcte ;

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

En outre, le Tri par Insertion est stable, contrairement à le Tri par Sélection.

J'ai implémenté les deux en python, et il est intéressant 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