| dbo:abstract
|
- Le comb sort ou tri à peigne ou tri de Dobosiewicz est un algorithme de tri assez simple initialement inventé par en 1980. Il a été redécouvert et popularisé plus récemment par et dans un article publié en avril 1991 dans la revue Byte Magazine. Le comb sort améliore notablement les performances du tri à bulles, et peut rivaliser avec des algorithmes de tri réputés rapides comme le tri rapide (quick sort), le tri fusion (merge sort) ou le tri de Shell (Shell sort). Dans le tri à bulles ascendant classique, chacun des éléments de la liste à trier est comparé avec son voisin immédiat et interverti s'il est plus grand que l'élément suivant. Dans ce type de tri, les grandes valeurs situées à l'origine près du début de la liste à trier montent rapidement vers la fin de la liste (on parle de « lièvres »), alors que les petits éléments proches de la fin de la liste ne redescendent que très lentement vers le début de la liste (ce sont les « tortues »). C'est l'existence de ces « tortues » qui pénalise fortement les performances du tri à bulles. L'idée de base est d'éliminer ces « tortues » (les « lièvres » ne posent pas de problème de performance) en les déplaçant plus rapidement vers le début de la liste. L'amélioration apportée par le comb sort au tri à bulles est analogue à celle qu'apporte le tri de Shell au tri par insertion. Robert Sedgewick, l'un des spécialistes les plus réputés des algorithmes de tri, inverse en quelque sorte le point de vue en considérant (dans certains au moins de ses écrits) le comb sort comme une variante du tri de Shell qui utiliserait le tri à bulles comme algorithme de départ. L'idée de base du comb sort est de comparer un élément avec un autre élément plus lointain, espacé de celui-ci d'un certain intervalle. Au départ, cet intervalle est relativement grand, puis on le réduit progressivement à chaque passe de l'algorithme jusqu'à ce qui ne soit plus que de 1 en fin de traitement. Le tri à bulles peut être considéré comme une variante du comb sort dans lequel l'intervalle est toujours de 1. Autrement dit, la boucle interne du tri à bulle (celle qui fait la comparaison de deux éléments voisins et l'échange des valeurs si nécessaire) est modifiée pour comparer d'abord des éléments distants de la valeur de l'intervalle, puis, à chaque passe, cet intervalle est divisé par un certain coefficient, le facteur de réduction jusqu'à ce qu'il tombe à 1. La valeur d'origine de l'intervalle est généralement la taille de la liste à trier divisée par le facteur de réduction. Des essais empiriques ont montré que la valeur idéale de ce facteur de réduction est voisine de 1,3 (voir ci-dessous). (fr)
- Le comb sort ou tri à peigne ou tri de Dobosiewicz est un algorithme de tri assez simple initialement inventé par en 1980. Il a été redécouvert et popularisé plus récemment par et dans un article publié en avril 1991 dans la revue Byte Magazine. Le comb sort améliore notablement les performances du tri à bulles, et peut rivaliser avec des algorithmes de tri réputés rapides comme le tri rapide (quick sort), le tri fusion (merge sort) ou le tri de Shell (Shell sort). Dans le tri à bulles ascendant classique, chacun des éléments de la liste à trier est comparé avec son voisin immédiat et interverti s'il est plus grand que l'élément suivant. Dans ce type de tri, les grandes valeurs situées à l'origine près du début de la liste à trier montent rapidement vers la fin de la liste (on parle de « lièvres »), alors que les petits éléments proches de la fin de la liste ne redescendent que très lentement vers le début de la liste (ce sont les « tortues »). C'est l'existence de ces « tortues » qui pénalise fortement les performances du tri à bulles. L'idée de base est d'éliminer ces « tortues » (les « lièvres » ne posent pas de problème de performance) en les déplaçant plus rapidement vers le début de la liste. L'amélioration apportée par le comb sort au tri à bulles est analogue à celle qu'apporte le tri de Shell au tri par insertion. Robert Sedgewick, l'un des spécialistes les plus réputés des algorithmes de tri, inverse en quelque sorte le point de vue en considérant (dans certains au moins de ses écrits) le comb sort comme une variante du tri de Shell qui utiliserait le tri à bulles comme algorithme de départ. L'idée de base du comb sort est de comparer un élément avec un autre élément plus lointain, espacé de celui-ci d'un certain intervalle. Au départ, cet intervalle est relativement grand, puis on le réduit progressivement à chaque passe de l'algorithme jusqu'à ce qui ne soit plus que de 1 en fin de traitement. Le tri à bulles peut être considéré comme une variante du comb sort dans lequel l'intervalle est toujours de 1. Autrement dit, la boucle interne du tri à bulle (celle qui fait la comparaison de deux éléments voisins et l'échange des valeurs si nécessaire) est modifiée pour comparer d'abord des éléments distants de la valeur de l'intervalle, puis, à chaque passe, cet intervalle est divisé par un certain coefficient, le facteur de réduction jusqu'à ce qu'il tombe à 1. La valeur d'origine de l'intervalle est généralement la taille de la liste à trier divisée par le facteur de réduction. Des essais empiriques ont montré que la valeur idéale de ce facteur de réduction est voisine de 1,3 (voir ci-dessous). (fr)
|
