Tri de l'enveloppe et tri par insertion

Question

J'ai un problème. Je suis très confus sur les algorithmes de tri et d'insertion d'un shell. Comment devrions-nous nous distinguer les uns des autres?

Answer 1

Vous pouvez implémenter le tri par insertion sous la forme d'une série de comparaisons et d'échanges d'éléments contigus. Cela en fait un "type stable". Le tri Shell compare et échange les éléments éloignés les uns des autres. Cela le rend plus rapide.

Je suppose que votre confusion vient du fait que le tri des coquilles peut être implémenté comme plusieurs sortes d'insertion appliquées à différents sous-ensembles de données. Notez que ces sous-ensembles sont composés d'éléments non contigus de la séquence de données.

Voir Wikipedia pour plus de détails

;-)

Answer 2

Le insertion sort est simple, en place, O tri (N^2). Shell sort est un peu plus complexe et plus difficile à comprendre, et quelque part autour de O (N^(5/4)). Vérifiez les liens pour des exemples - il devrait être facile de voir la différence.

Answer 3

Shell sort est une version généralisée de Insertion sort. Le principe de base est le même pour les deux algorithmes. Vous avez une séquence triée de longueur n et vous insérez l'élément non trié dans celui-ci - et vous obtenez n + 1 séquence de longs éléments triés. La différence est la suivante: alors que le tri par insertion ne fonctionne qu'avec une séquence (initialement le premier élément du tableau) et l'étend (en utilisant l'élément suivant). Cependant, le tri des coquilles a un incrément décroissant , ce qui signifie qu'il y a un écart entre les éléments comparés (initialement n/2). Il y a donc n/2 séquences à trier en utilisant le tri par insertion. Dans chaque étape, l'incrément est réduit (souvent juste divisé par 2,2) et le nombre de séquences est réduit. Dans la dernière étape il n'y a pas d'écart et l'algorithme dégénère en un simple tri par insertion. En raison de l'incrément décroissant, les éléments grands et petits sont déplacés rapidement pour corriger la partie du réseau et que dans la dernière étape triés en utilisant le tri d'insertion très rapidement. Cela conduit à une complexité temporelle réduite O (n^(4/3))