Algorithmes de tri par insertion et de tri à bulles

Question

J'essaie de comprendre quelques algorithmes de tri, mais j'ai du mal à voir la différence entre l'algorithme du tri à bulles et celui du tri par insertion.

Je sais que les deux sont O(n 2 ), mais il me semble que le tri à bulles fait juste remonter la valeur maximale du tableau vers le haut à chaque passage, alors que le tri par insertion fait juste descendre la valeur la plus basse vers le bas à chaque passage. Ne font-ils pas exactement la même chose mais dans des directions différentes ?

Pour le tri par insertion, le nombre de comparaisons/échanges potentiels commence à zéro et augmente à chaque fois (c'est-à-dire 0, 1, 2, 3, 4, ..., n) mais pour le tri à bulles, le même comportement se produit, mais à la fin du tri (c'est-à-dire n, n-1, n-2, ... 0) car le tri à bulles n'a plus besoin de comparer avec les derniers éléments au fur et à mesure qu'ils sont triés.

Pour autant, il semble qu'un consensus se dégage pour dire que le tri par insertion est meilleur en général. Quelqu'un peut-il me dire pourquoi ?

Edit : Je suis principalement intéressé par les différences dans la façon dont les algorithmes fonctionnent, pas tellement par leur efficacité ou leur complexité asymptotique.

Answer 1

Tri par insertion

Après i itérations, la première i les éléments sont ordonnés.

À chaque itération, l'élément suivant est mis en bulle dans le fichier trié jusqu'à ce qu'il atteigne le bon endroit :

sorted  | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2

Le 4 est mis en bulle dans la section triée

Pseudocode :

for i in 1 to n
    for j in i downto 2
        if array[j - 1] > array[j]
            swap(array[j - 1], array[j])
        else
            break

Tri à bulles

Après i itérations les dernières i Les éléments sont les plus grands, et ordonnés.

A chaque itération, passez au crible les non trié pour trouver le maximum.

unsorted  | biggest
3 1 5 4 2 | 6 7 8 9
1 3 4 2 | 5 6 7 8 9

Le 5 est sorti de la section non triée.

Pseudocode :

for i in 1 to n
    for j in 1 to n - i
         if array[j] > array[j + 1]
             swap(array[j], array[j + 1])

Notez que les implémentations typiques se terminent prématurément si aucun échange n'est effectué pendant l'une des itérations de la boucle externe (puisque cela signifie que le tableau est trié).

Différence

Dans le tri par insertion, les éléments sont mis en bulles dans la section triée, tandis que dans le tri à bulles, les maximums sont mis en bulles dans la section non triée.

Answer 2

Dans le tri à bulles, à la ième itération, vous avez n-i-1 itérations internes (n^2)/2 au total, mais dans le tri par insertion, vous avez au maximum i itérations à la iième étape, mais i/2 en moyenne, car vous pouvez arrêter la boucle interne plus tôt, après avoir trouvé la position correcte pour l'élément actuel. Vous avez donc (somme de 0 à n) / 2, soit (n^2) / 4 au total ;

C'est pourquoi le tri par insertion est plus rapide que le tri à bulles.

Answer 3

Une autre différence, que je n'ai pas vue ici :

Tri à bulles a 3 affectations de valeur par swap : vous devez d'abord construire une variable temporaire pour sauvegarder la valeur que vous voulez faire avancer (no.1), puis vous devez écrire l'autre variable d'échange dans le point dont vous venez de sauvegarder la valeur (no.2) et enfin vous devez écrire votre variable temporaire dans l'autre point (no.3). Vous devez faire cela pour chaque point - vous voulez avancer - pour classer votre variable au bon endroit.

Avec tri par insertion vous mettez votre variable à trier dans une variable temporaire et ensuite vous mettez toutes les variables devant cette place 1 place en arrière, tant que vous atteignez la place correcte pour votre variable. Cela fait 1 attribution de valeur par spot . A la fin, vous écrivez votre variable temporaire dans l'emplacement.

Cela fait aussi beaucoup moins d'affectations de valeur.

Ce n'est pas le plus grand avantage en termes de vitesse, mais je pense qu'il peut être mentionné.

J'espère m'être exprimé de manière compréhensible, sinon, désolé, je ne suis pas natif de Grande-Bretagne.

Answer 4

Le principal avantage du tri par insertion est qu'il s'agit d'un algorithme en ligne. Il n'est pas nécessaire de disposer de toutes les valeurs au départ. Cela peut être utile lorsque l'on traite des données provenant d'un réseau ou d'un capteur.

J'ai le sentiment que ce serait plus rapide que les autres méthodes conventionnelles. n log(n) algorithmes. Parce que la complexité serait n*(n log(n)) par exemple, lire/stocker chaque valeur du flux ( O(n) ) et ensuite trier toutes les valeurs ( O(n log(n)) ), ce qui donne O(n^2 log(n))

Au contraire, l'utilisation d'Insert Sort nécessite O(n) pour lire les valeurs du flux et O(n) pour mettre la valeur au bon endroit, donc c'est O(n^2) seulement. L'autre avantage est que vous n'avez pas besoin de tampons pour stocker les valeurs, vous les triez dans la destination finale.

Answer 5

Le tri à bulles n'est pas en ligne (il ne peut pas trier un flux d'entrées sans savoir combien d'éléments il y aura) car il ne garde pas vraiment trace d'un maximum global des éléments triés. Lorsqu'un élément est inséré, vous devez recommencer le tri à bulles depuis le début.