Tri à peigne

Carte Commune · n° 365059

Le comb sort ou tri à peigne ou tri de Dobosiewicz est un algorithme de tri assez simple initialement inventé par Wodzimierz Dobosiewicz en 1980. Il a été redécouvert et popularisé plus récemment par Stephen Lacey et Richard Box 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...

Lire sur Wikipédia · Image Jerejesse, CC BY-SA 3.0