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.


dimanche 19 avril 2015

Comparatif des algorithmes de tri

Comme j'ai un peu de mal dans les calculs de complexité en moyenne, je me suis bricolé un outil permettant de comparer les algorithmes de tri. Il ressemble à ça :


En gros, c'est un outil tout simple qui génère des suites aléatoires de nombres (entre 1 et 10000) puis les trie en utilisant divers algorithmes. Pendant le tri, il compte le nombre de comparaisons et d'échanges et en fait ensuite un graphique.

L'outil est écrit uniquement en JavaScript.

samedi 18 avril 2015


Je me suis aperçu, l'autre jour, que je n'avais pas mis à jour ce site depuis... 2003. Voilà qui commence à faire un peu long. Et qui trahit tout de même un léger manque de réactivité...
Alors, je me suis dis qu'il était grand temps de faire quelque chose pour mon karma et, partant, de retoucher ces pages perso. Leur présentation était vieillotte (et même franchement dépassée), les applets ne fonctionnaient plus...
Je me suis donc mis au travail. J'ai commencé par revoir le design qui, s'il était dans le ton des années 2000, fait franchement ridicule aujourd'hui. En même temps je ne prétend pas non plus être à la page : la conception de sites web n'est pas mon métier, alors bon, je fais au mieux.
Ces pages perso me servaient, au départ, à déposer mes supports de cours pour qu'ils soient accessibles à tous. Avec le temps j'y ai ajouté des démonstrations d'algorithmes, des applets java, des sharewares... enfin un peu tout et n'importe quoi, en fonction de mes centres d'intérêt du moment. En les revoyant aujourd'hui, j'ai parfois un peu honte des bêtises que j'ai pu y écrire... Et parfois, j'y redécouvre des choses qui, finalement, n'étaient pas si mauvaises. J'ai même eu la surprise de voir certaines de mes pages copiées intégralement sur d'autre sites...
Pour ce qui est des applets Java, je préfère les remplacer par des animations JavaScript/Html5. La société Sun, qui ne semble pas être capable de sécuriser Java, impose la signature des applets. Même pour celles qui – comme les miennes – ne font qu'afficher des informations. Comme je n'ai pas l'intention de dépenser quelques 200 € par an pour un certificat, je préfère laisser tomber. D'autant que l'avenir de Java me semble bien compromis. Et que le support des canvas, de Webgl et du format svg par les navigateurs modernes ouvre des possibilités bien plus intéressantes que ce que permettent les applets Java.
Bon, il me reste pas mal de boulot pour faire de ce truc quelque chose d'à peu-près présentable, mais je garde espoir.