Tri Combsort

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le tri Combsort ou tri à peigne ou tri de Dobosiewicz est un algorithme de tri assez simple initialement inventé par Wodzimierz Dobosiewicz en 1980[1]. Il a été redécouvert et popularisé plus récemment par Stephen Lacey et Richard Box dans un article publié en avril 1991[2] dans la revue Byte Magazine. Le tri Combsort 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[3], 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 tri Combsort au tri à bulles est analogue à celle qu'apporte le tri de Shell[4],[5] 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 tri Combsort comme une variante du tri de Shell qui utiliserait le tri à bulles comme algorithme de départ[6].

L'idée de base du tri Combsort 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 tri Combsort 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).

Le facteur de réduction[modifier | modifier le code]

Le choix du facteur de réduction a un impact élevé sur l'efficacité du tri Combsort. Dans l'article d'origine, les auteurs proposaient une valeur de \frac{4}{3} ou 1,3.

Une valeur trop petite ralentit l'algorithme parce qu'il faut effectuer plus de comparaisons, alors qu'une valeur trop grande signifie que toutes les tortues ne sont pas éliminées lorsque l'intervalle est réduit à 1, ce qui conduit à plusieurs passes d'un tri à bulles pour compléter le tri. La valeur idéale est sans doute un compromis entre ces deux écueils.

Des auteurs ont proposé d'autres valeurs, telles que 1/\left(1-\frac{1}{e^\varphi}\right) \approx 1,247330950 comme facteur de réduction (avec \varphi égal au nombre d'or, soit environ 1,618034). D'autres auteurs ont proposé 1,2796. Des essais extensifs semblent indiquer que tout facteur de réduction inférieur à \frac{9}{7} \approx 1,2857 suffise à éliminer toutes les tortues, mais cette conjecture paraît difficile à prouver rigoureusement. Dans tous les cas, il semble bien que la valeur idéale soit située quelque part entre 1,25 et 1,33. On choisira une valeur arbitraire de 1,3 pour la suite de cet article.

Propriétés de l'algorithme de tri Combsort[modifier | modifier le code]

Le tri Combsort est un tri "en place" (voir Caractère en place), c'est-à-dire qu'il peut trier les éléments d'un tableau à l'intérieur même de ce tableau, sans devoir allouer de structures de mémoire supplémentaires pour stocker des résultats temporaires. Il est donc peu gourmand en mémoire. De même, contrairement à plusieurs algorithmes de tri rapides, il n'est pas récursif et ne génère donc pas non plus d'occupation mémoire implicite sur la pile d'exécution. Ces propriétés peuvent être intéressantes quand il s'agit de trier de gros volumes de données s'approchant des capacités mémoires de la machine utilisée.

C'est un algorithme instable (voir Caractère stable), c'est-à-dire que si deux enregistrements ont la même clef de tri, il ne garantit pas que les enregistrements se retrouveront dans le même ordre qu'au départ. Toutefois, il est toujours possible de transformer un tri instable en un tri stable, moyennant l'utilisation de O(n) mémoire supplémentaire pour stocker l'ordre initial des éléments.

Comme le tri de Shell, sa complexité algorithmique théorique est très délicate à analyser. On peut facilement montrer qu'elle est au pire de O(n2), mais elle est bien meilleure en réalité, sans que l'on parvienne à le démontrer théoriquement.[7] Dans la pratique (et moyennant le choix d'un Facteur de réduction approprié), il se comporte de la même façon que les algorithmes de tris connus pour être en O(n log n) dans tous les cas, comme le tri fusion.

Variantes[modifier | modifier le code]

Combsort11[modifier | modifier le code]

Avec un facteur de réduction de l'ordre de 1,3, il n'y a que trois manières possibles de terminer la liste des intervalles: (9, 6, 4, 3, 2, 1), (10, 7, 5, 3, 2, 1), ou (11, 8, 6, 4, 3, 2, 1). Les expériences ont montré que l'on obtenait une amélioration notable de la vitesse en choisissant un intervalle de 11 lorsque la valeur calculée serait sinon de 9 ou 10. Cette variante est appelée « Combsort11 ».

Si l'on utilisait l'une des séquences commençant à 9 ou 10, la passe finale avec un intervalle de 1 a moins de chance de trier complètement les données, ce qui nécessite alors au moins une passe supplémentaire avec un intervalle de 1. Les données sont complètement triées quand aucun échange n'a lieu au cours d'une passe avec un intervalle de 1.

Combsort se terminant par une autre méthode de tri[modifier | modifier le code]

Comme de nombreux autres algorithmes de tri (par exemple le tri rapide ou le tri fusion), le tri Combsort est plus efficace dans ses premières passes que dans les dernières, quand il se réduit à un tri à bulles. On peut améliorer les performances du tri Combsort en changeant de méthode de tri quand l'intervalle devient suffisamment petit (par exemple inférieur à 10). On peut par exemple passer au Tri cocktail ou, mieux à un tri par insertion[8].

Un autre avantage de cette méthode est qu'il n'est pas nécessaire de vérifier si un échange a eu lieu au cours de la passe pour savoir s'il faut arrêter le tri.

Comparaison avec d'autres tris rapides[modifier | modifier le code]

Des comparaisons entre l'algorithme du tri Combsort en Perl présenté ci-dessous et des mises en œuvre analogues du tri rapide, du tri fusion et du tri de Shell montrent que, pour des listes de nombres aléatoires ou pseudo-aléatoires, le tri rapide et le tri de Shell sont environ 2,3 fois plus rapides que le tri Combsort (indépendamment de la taille de la liste à trier), alors que ce dernier est à son tour environ 1,35 fois plus rapide que le tri fusion (les valeurs exactes peuvent varier selon les détails de la mise en œuvre, mais elles varient peu en fonction des micro-optimisations de code).

En revanche, si la liste d'origine est presque triée dans l'ordre direct ou dans l'ordre inverse, le tri Comsort est le plus rapide de quatre. Dans ce cas, en effet, le tri rapide et le tri de Shell deviennent très lents. Par exemple, pour un tableau de 5 000 éléments presque triés dans l'ordre, le tri rapide et le tri de Shell sont tous les deux 10 fois plus lents que le tri Combsort, qui reste dans ce cas environ 1,35 fois plus rapide que le tri fusion. Pour des listes de 5 000 éléments triées ou presque triées en ordre inverse, le tri Combsort et le tri fusion sont environ 20 fois plus rapides que le tri rapide ou le tri de Shell. Avec des listes presque triées plus grandes, l'avantage du tri Combsort (et dans une légèrement moindre mesure du tri fusion) est encore plus flagrant. Dans ces cas, le tri rapide et le tri de Shell souffrent d'une complexité quadratique en O(n2), alors que le tri fusion et le tri Combsort semblent continuer à bénéficier d'une complexité bien moins lourde, sans doute en O(n log n).

Statistiquement, les cas où le tri rapide ou le tri de Shell se comportent aussi mal, par rapport au nombre total de cas possibles, sont très rares. Mais dans la réalité, il est assez fréquent d'avoir à trier à nouveau une liste presque triée. Par exemple, il est commun d'avoir un classement d'équipes de sport qu'il faut mettre à jour après chaque journée de compétition, ou de devoir mettre à jour l'index d'une table d'une base de donnée lors de l'ajout ou de la modification de certains enregistrements. Dans ce genre de cas, le tri fusion ou le tri Combsort paraissent plus indiqués que le tri rapide ou le tri de Shell. C'est ce qui a amené de nombreux éditeurs de logiciels, de bases de données ou de langages de programmation à implanter des algorithmes de tri certes un peu moins efficaces que le tri rapide dans la majorité des cas, mais ne souffrant pas d'une explosion quadratique de la complexité dans le pire des cas. C'est ce qui a amené, par exemple, les développeurs du langage Perl à passer du tri rapide au tri fusion pour la fonction interne sort du langage à partir de la version 5.8 du langage. Dans ce genre de cas, le tri Combsort, généralement plus rapide que le tri fusion, pourrait être un candidat[réf. nécessaire] sérieux au remplacement du tri rapide, à condition d'arriver à démontrer qu'il ne souffre pas non plus d'explosion quadratique dans le pire des cas (ce qui semble être le cas au vu des nombreux tests effectués, mais cela n'a apparemment pas été établi formellement).

Exemples[modifier | modifier le code]

Voir aussi : Algorithm Implementation/Sorting/Comb sort sur Wikibooks en anglais.

Pseudocode[modifier | modifier le code]

fonction combsort(tableau liste)
    intervalle := liste.taille //initialisation de l'intervalle
    
    Répéter tant que intervalle > 1 ou échange = vrai
        intervalle := int(intervalle / 1.3)
        si intervalle < 1
          intervalle := 1
        fin si
        
        i := 0
        échange := faux
        
        Répéter tant que i ≤ liste.taille - intervalle
            si liste[i] > liste[i + intervalle]
                échanger liste[i] et liste[i + intervalle]
                échange := vrai
            fin si
            i := i + 1
        fin tant que
       
    fin tant que
fin fonction

Perl[modifier | modifier le code]

sub comb_sort {
  my @v = @_;
  my $max = scalar (@v);
  my $gap = $max;
  while (1) {
     my $swapped = 0;
     $gap = int ($gap / 1.3);
     $gap = 11 if $gap == 10 or $gap == 9; # (optimisation Combsort11)
     $gap = 1 if $gap < 1;
     my $lmax = $max - $gap - 1;
     foreach my $i (0..$lmax) {
          ($v[$i], $v[$i+$gap], $swapped) = ($v[$i+$gap], $v[$i], 1) if $v[$i] > $v[$i+$gap];
     }
     last if $gap == 1 and $swapped == 0;
  }
  return @v;
}

Notes et références[modifier | modifier le code]

  1. W. Dobosiewicz. An efficient variation of bubble sort. Information Processing Letters 11, 1980, 5–6.
  2. http://cs.clackamas.cc.or.us/molatore/cs260Spr03/combsort.htm
  3. Robert Sedgewick. Algorithms, Addison Wesley, 1983, p. 99. ISBN O-201-06672-6.
  4. D. Shell. A high-speed sorting procedure Communications of the ACM 2, 1959, 30–32
  5. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.
  6. Analysis of Shellsort and Related Algorithms, Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, September 1996
  7. Brejová, Bronislava, Analyzing variants of Shellsort.
  8. Donald Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1973, exercise 5.2.1-40.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

  • Tri à bulles, un algorithme généralement bien plus lent, à la base du tri Combsort.
  • Tri cocktail, ou tri Shaker ou tri à bulles bidirectionnel, une variante du tri à bulles qui cherche également à éliminer les tortues, mais le fait moins efficacement.

Liens externes[modifier | modifier le code]