tri au peigne

L'idée principale est d'éliminer les « tortues » , c'est-à-dire les petites valeurs en fin de liste, car elles ralentissent considérablement le tri à bulles. Les « lapins » , c'est-à-dire les grandes valeurs en début de liste, ne posent aucun problème pour le tri à bulles.

Dans le tri à bulles, lorsque deux éléments quelconques sont comparés, ils ont toujours un écart (distance l'un par rapport à l'autre) de 1. L'idée de base du tri en peigne est que l'écart peut être beaucoup plus grand que 1. La boucle interne du tri à bulles, qui effectue l' échange réel , est modifiée de sorte que l'écart entre les éléments échangés diminue (pour chaque itération de la boucle externe) par étapes d'un « facteur de rétrécissement » k : n / k ⁠ , ⁠ n / k ² ⁠ , ⁠ n / k ³ ⁠ , ..., 1] .

L'écart initial correspond à la longueur n de la liste à trier divisée par le facteur de réduction k (généralement 1,3 ; voir ci-dessous). Une première itération du tri à bulles modifié mentionné précédemment est alors effectuée avec cet écart. L'écart est ensuite à nouveau divisé par le facteur de réduction, la liste est triée avec ce nouvel écart, et le processus se répète jusqu'à ce que l'écart soit égal à 1. À ce stade, le tri en peigne se poursuit avec un écart de 1 jusqu'à ce que la liste soit entièrement triée. L'étape finale du tri est donc équivalente à un tri à bulles, mais à ce stade, la plupart des erreurs de tri importantes ont été résolues, rendant ainsi le tri à bulles plus efficace.

Le facteur de réduction a une grande influence sur l'efficacité du tri en peigne. Dobosiewicz a suggéré k = 4/3 = 1,333…, tandis que Lacey et Box proposent 1,3 comme valeur idéale après des tests empiriques sur plus de 200 000 listes aléatoires d'environ 1 000 éléments. Une valeur trop faible ralentit l'algorithme en effectuant un nombre excessif de comparaisons, tandis qu'une valeur trop élevée ne permet pas de gérer efficacement les tortues, ce qui nécessite de nombreux passages avec un intervalle de 1.

Le schéma de passages de tri répétés avec des intervalles décroissants est similaire à celui de Shellsort, mais dans Shellsort, le tableau est entièrement trié à chaque passage avant de passer au prochain intervalle plus petit. Les passages de tri en peigne ne trient pas complètement les éléments. C'est pourquoi les séquences d'intervalles de Shellsort ont un facteur de réduction optimal plus élevé, d'environ 2,25.

Une autre amélioration suggérée par Lacey et Box est la « règle de 11 » : toujours utiliser une taille d'espace de 11, en arrondissant les tailles d'espace de 9 ou 10 (obtenues en divisant les espaces de 12, 13 ou 14 par 1,3) à 11. Cela empêche les tortues de survivre jusqu'au dernier passage de l'espace 1.

la fonction combsort( tableau d'entrée) est gap := input.size // Initialiser la taille de l'espace shrink := 1.3 // Définir le facteur de réduction de l'espace trié := faux boucle tant que sorted = false // Mettre à jour la valeur d'écart pour le peigne suivant écart := plancher(écart / rétrécissement) si l'écart ≤ 1 alors écart := 1 sorted := true // S'il n'y a pas d'échanges à ce passage, on a terminé. Sinon, si gap = 9 ou gap = 10, alors gap := 11 // La « règle de 11 » fin si// Un seul « peigne » sur la liste d'entrée i := 0 boucle tant que i + gap < input.size // Voir le tri Shell pour une idée similaire si input[i] > input[i+gap] alors échanger (input[i], input[i+gap]) trié := faux // Si cette affectation n'a jamais lieu dans la boucle, // Alors il n'y a eu aucun échange et la liste est triée. fin si i := i + 1 fin de boucle fin de boucle fin de fonction