samedi 25 avril 2015

Le tri à peigne ou tri de Dobosiewicz

On m'a toujours dit (et j'ai toujours bêtement répété) que le tri bulle était l'un des pires algorithmes qui soit. C'est sûr qu'il est très lent (surtout pour sa version de base qui se limite à deux boucles imbriquées) et qu'il n'a rien de particulièrement excitant à coder. Rien à voir en tout cas avec l'estimable tri rapide.

C'est sûr que cet algorithme ne donne pas vraiment envie :
  
PROCEDURE tri_bulle ( TABLEAU a[1:n])

REPETER
    permut = FAUX 
    POUR i VARIANT DE 1 A n - 1 FAIRE
        SI a[i] > a[i+1] ALORS
            echanger a[i] ET a[i+1]
            permut = VRAI
        FIN SI
    FIN POUR   
TANT QUE permut = VRAI
    

Pourtant, avec quelques petites modifications, toutes simples, on obtient quelque chose de bien plus performant, avec des performances approchant celles du tri rapide :

PROCEDURE tri_peigne ( TABLEAU a[1:n])
gap = n
REPETER
    permut = FAUX
    gap = gap / 1.3
    SI gap < 1 ALORS gap = 1
    POUR i VARIANT DE 1 A n AVEC UN PAS gap FAIRE
        SI a[i] > a[i+gap] ALORS
            echanger a[i] et a[i+gap]
            permut = VRAI
        FIN SI
    FIN POUR
TANT QUE permut = VRAI OU gap > 1

Le principe de cet algorithme fut exposé pour la première fois en 1973 par Donald Knuth dans un exercice de son livre "The Art of Computer Programming", vol. 3, Sorting and Searching. L'exercice consistait à construire une variante du tri de Shell en en simplifiant la boucle interne.

Un peu plus tard, en 1980, Wlodzimierz Dobosiewicz écrivit un court article intitulé "An Efficient Variation of Bubble Sort", Information Processing Letters, vol. 11, num. 1, 1980. On peut y lire : "Bubble sort can be improved in yet another way, which is similar to Shell’s version of the insertion sort" (le tri à bulle peut être amélioré d'une manière similaire à celle appliquée par Shell au tri par insertion).

L'idée était de ne plus comparer uniquement des éléments adjacents comme dans un tri bulle classique mais de commencer par un intervalle plus grand puis de réduire à chaque boucle cet intervalle. Avec cette méthode les éléments étaient déplacés plus rapidement vers une position proche de leur place définitive, puis, à mesure que l'intervalle se rapproche de un, ils se rapprochent de leur position définitive. Le problème du tri bulle ce sont effectivement les "tortues", ces éléments en fin de tableau qui doivent rejoindre le début du tableau lors du tri. La méthode de Dobosiewicz permet de les déplacer bien plus rapidement.

Dobosiewicz suggérait  de commencer par un intervalle de  N/2 (N étant la taille de la liste à trier) et de multiplier l'intervalle par 3/4 pour calculer les suivants (ce qui équivaut à une bête division par 1.3), puis de terminer avec un intervalle de un, donc par un tri bulle classique.

En 1991, Stephen Lacey et Richard Box décrivirent le même algorithme sous le nom "Combsort" (tri à peigne) dans leur article "A fast, easy sort" Byte, vol. 16, numéro 4, Avril 1991. Ils optèrent pour la valeur 1.3 comme facteur de réduction idéal. Ils firent également quelques expériences avec des progressions non géométriques avant de les abandonner. Il semble que le facteur de réduction idéal se situe entre 1.25 et 1.35.

Lacey et Box suggérèrent également de forcer, lors des dernières passes, la séquence d'intervalles 11, 8, 6, 4, 3, 2, 1. Cette séquence favorise la probabilité de trier plus rapidement la totalité de la séquence. La variante de l'algorithme implémentant cette modification est appelée "COMB11".

 Une démonstration de l'algorithme ainsi que son code en Pascal, Caml, Python et C est disponible ici. En voici un petit aperçu :


Une très importante partie de cet article est directement inspirée (voire traduite) de Martín Knoblauch Revuelta, professeur à l'université de Alcalá de Henares, près de Madrid.


Aucun commentaire:

Enregistrer un commentaire