Tri cocktail

Le tri cocktail (cocktail sort), ou tri shaker (shaker sort) ou tri à bulles bidirectionnel (bidirectional bubble sort) est une variante du tri à bulles^[1] qui est à la fois un algorithme de tri et un tri par comparaison. La différence entre cet algorithme et le tri à bulles est qu'il exécute un tri dans chaque direction à chaque passe le long de la liste à trier^[2]. Cet algorithme de tri n'est que légèrement plus difficile à comprendre et à mettre en œuvre que le tri à bulles, et il résout en partie le problème des tortues du tri à bulles (les tortues sont les petits éléments situés près de la fin de la liste d'origine, qui ne remontent que très lentement, un emplacement par itération, vers leur emplacement définitif).

Exemples

Pseudocode

Dans sa forme la plus simple, le tri cocktail parcourt l'ensemble de la liste à chaque passe.

fonction tri_cocktail (array liste)
    échangé  := vrai
    Répéter tant que échangé = vrai
        échangé = faux
        

         Répéter pour tout  i entre 0 et liste.taille - 2
            if liste[i] > liste[i + 1]
                [[Echanger (liste[i], list[i+1])
                échangé  := vrai
            fin si
         fin Répéter
         Répéter pour tout  i (décroissant) entre liste.taille-2 et 0
            if liste[i] > liste[i + 1]
                [[Echanger (liste[i], list[i+1])
                échangé  := vrai
            fin si
         fin Répéter         
     fin tant que
 fin fonction

Lors de la première passe, le premier parcours vers la droite déplace des éléments plus grands que leur voisin immédiat vers la droite, et, en particulier, va déplacer de proche en proche le plus grand élément de la liste à son emplacement définitif en fin de liste. Ensuite, le second parcours vers la gauche va déplacer les éléments plus petits que leur voisin immédiat vers la gauche, et, en particulier, déplacera l'élément le plus petit de la liste à son emplacement définitif en tête de liste. vers la gauche. De même, lors de la seconde passe, le second élément le plus grand et le second élément le plus petits rejoindront à leur tour leur emplacement définitif, et ainsi de suite. Après i passes, les i premiers éléments et les i derniers éléments sont à leur emplacement définitif. Ils n'ont donc plus besoin d'être vérifiés. Il est donc possible d'optimiser cet algorithme en ne vérifiant à chaque passe que la partie centrale de la liste non encore triée définitivement. Ceci permet de réduire de moitié le nombre de comparaisons à effectuer (voir Optimisation en ignorant la partie déjà triée).

Pseudocode (variante optimisée)

fonction tri_cocktail (array liste)
    échangé := vrai
    début = 0
    fin = liste.taille - 1
    Répéter tant que échangé = vrai
        échangé = faux
        

        Répéter pour tout  i entre début et fin
            if liste[i] > liste[i + 1]
                [[Echanger (liste[i], list[i+1])
                échangé := vrai
            fin si
        fin Répéter
        fin := fin - 1
        Répéter pour tout  i (décroissant) entre fin et début
            if liste[i] > liste[i + 1]
                [[Echanger (liste[i], list[i+1])
                échangé := vrai
            fin si
        fin Répéter         
        début := début + 1
    fin tant que
fin fonction

Perl

sub cocktail_sort {
	my @v = @_;
	my $lmax = $scalar (@v) -1;
	my $lmin = 0;
	while (1) {
		$nf = 0;
		foreach my $i ($lmin..$lmax) {
			($v[$i], $v[$i+1]) = ($v[$i+1], $v[$i]) and $nf=$i if $v[$i] > $v[$i+1];
		}
		last unless $nf;
		$lmax = $nf-1;
		$nf = 0;
		foreach my $i (reverse $lmin..$lmax) {
			($v[$i], $v[$i+1]) = ($v[$i+1], $v[$i]) and $nf=$i+1 if $v[$i] > $v[$i+1];
		}
		last unless $nf;
		$lmin = $nf;
	}
	return @v;
}

Exemple de déroulement de l'algorithme

Ci-dessous l'état d'un tableau de 21 éléments, initialement triés en ordre inverse, après chaque itération de l'algorithme.

40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2 0
0 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2 40
0 2 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 38 40
0 2 4 34 32 30 28 26 24 22 20 18 16 14 12 10 8 6 36 38 40
0 2 4 6 32 30 28 26 24 22 20 18 16 14 12 10 8 34 36 38 40
0 2 4 6 8 30 28 26 24 22 20 18 16 14 12 10 32 34 36 38 40
0 2 4 6 8 10 28 26 24 22 20 18 16 14 12 30 32 34 36 38 40
0 2 4 6 8 10 12 26 24 22 20 18 16 14 28 30 32 34 36 38 40
0 2 4 6 8 10 12 14 24 22 20 18 16 26 28 30 32 34 36 38 40
0 2 4 6 8 10 12 14 16 22 20 18 24 26 28 30 32 34 36 38 40
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40

Différences avec le tri à bulles

Le tri cocktail est une légère modification du tri à bulles. La différence est qu'au lieu de traverser la liste de façon répétée de gauche à droite (ou de bas en haut), le tri cocktail passe alternativement de gauche à droite et de droite à gauche. Il permet d'obtenir des performances légèrement meilleures que le tri à bulles standard, parce, comme le tri à bulles traverse toujours la liste dans le même direction, il ne peut faire redescendre les petits éléments vers le début de la liste que d'un seul emplacement à la fois à chaque itération.

Un exemple de liste illustrant cette caractéristique est la liste (2,3,4,5,1), qui n'a besoin que d'une seule passe du tri cocktail pour devenir complètement triée, alors qu'en utilisant un tri à bulles ascendant standard, il faudrait quatre passes (à noter cependant qu'une passe du tri cocktail doit être décomptée comme deux passes du tri à bulles ordinaire).

Une optimisation complémentaire (utilisée dans le code Perl ci-dessus) est de se souvenir de l'endroit où a eu lieu le dernier échange. Lors de la passe suivante, il est inutile d'aller plus loin (dans un sens ou dans l'autre), ce qui permet d'avoir des passes légèrement plus courtes et donc de réduire la durée totale d'exécution.

D'une façon générale, le tri cocktail n'apporte pas de grand gain de performance par rapport au tri à bulles optimisé ignorant la partie déjà triée (voir Optimisation en ignorant la partie déjà triée). Sur des données aléatoires ou pseudo-aléatoires, le tri à bulles optimisé ignorant la partie déjà triée permet de gagner environ 30 % sur la durée d'exécution d'un tri à bulles standard, alors que le tri cocktail ne permet de gagner qu'un facteur de 5 à 10 % de plus. Toutefois, pour des données non-aléatoires. Par exemple, une liste aux trois premiers quarts presque triés et dont le dernier quart ne l'est pas du tout peut conduire à des gains nettement plus élevés du tri cocktail par rapport au tri à bulles optimisé ignorant la partie déjà triée (de l'ordre de 40 %). Mais ce genre de cas est peu fréquent et ne paraît pas justifier un intérêt majeur pour le tri cocktail, d'autant qu'une variante guère plus complexe du tri à bulles, le tri Combsort^[3], permet des gains très largement plus significatifs dès que le nombre d'éléments à trier devient assez élevé.

Complexité

La complexité algorithmique du tri cocktail est de $O(n^{2})$ dans le pire des cas et dans le cas moyen, mais elle devient plus proche de $O(n)$ si la liste initiale est presque ordonnée. En particulier, si chaque élément de la liste initiale est à une position qui diffère au plus de k (k >= 1) de sa position finale, alors la complexité du tri cocktail est alors de $O(k*n)$ .

Dans son livre de référence sur l'algorithmique, The Art of Computer Programming^[4], Donald Knuth discute brièvement du tri cocktail et de quelques autres améliorations du tri à bulles. En conclusion, Knuth écrit que :

« Mais aucune de ces améliorations ne conduit à un algorithme meilleur que la simple insertion [c'est-à-dire, le tri par insertion] [...] Bref, rien ne paraît devoir recommander le tri à bulles, si ce n'est son nom original et le fait qu'il débouche sur quelques problèmes théoriques intéressants. »

Niklaus Wirth reprend les mêmes conclusions presque dans les mêmes termes dans l'ouvrage cité en référence.

Notes et références

↑ Robert Sedgewick. Algorithms, Addison Wesley, 1983, p. 99. ISBN O-201-06672-6.
↑ De nombreux auteurs ont décrit différentes optimisations du tri à bulles, dont celle du tri cocktail ou tri shaker. Voir par exemple N. Wirth, Algorithms and Data Structure (1985 ou 2004), paragraphe 2.2.3.
↑ W. Dobosiewicz. “An efficient variation of bubble sort.” Information Processing Letters 11, 1980, 5–6.
↑ Donald Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1973, p. 110.

Voir aussi

Articles connexes

Tri à bulles, l'algorithme dont dérve le tri cocktail.
Tri Combsort, ou tri à peigne, une variante bien plus efficace du tri à bulles dès lors que le nombre d'éléments à trier est un tant soit peu élevé (supérieur à 20), car sa complexité en $O(nlogn)$ lui permet de rivaliser plus ou moins avec les tris réputés rapides comme le tri rapide (quick sort), le tri fusion (merge sort) ou le tri de Shell (Shell sort).