Voir la source de Tri cocktail

{{Infobox Algorithme}}
Le '''tri cocktail''' (''{{lang|en|cocktail sort}}''), ou '''tri shaker''' (''{{lang|en|shaker sort}}'') ou '''tri à bulles bidirectionnel''' (''{{lang|en|bidirectional bubble sort}}'') est une variante du [[tri à bulles]]<ref>Robert Sedgewick. Algorithms, Addison Wesley, 1983, {{p.|99}}. ISBN O-201-06672-6.</ref> 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<ref>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.</ref>. 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é
         échangé := faux
         <br />
          '''Répéter pour tout ''' i entre 0 et liste.taille - 2
             '''si''' liste[i] > liste[i + 1]
                 <nowiki>[[</nowiki>Echanger (liste[i], liste[i+1])
                 échangé := vrai
             '''fin si'''
          '''fin Répéter'''
          '''Répéter pour tout ''' i (décroissant) entre liste.taille-2 et 0
             '''si''' liste[i] > liste[i + 1]
                 <nowiki>[[</nowiki>Echanger (liste[i], liste[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 petit 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 [[tri à bulles#Variantes de l'algorithme|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 - 2
     '''Répéter tant que échangé
         échangé := faux
         <br />
          '''Répéter pour tout ''' i entre début et fin
             '''si''' liste[i] > liste[i + 1]
                 <nowiki>[[</nowiki>Echanger (liste[i], liste[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
             '''si''' liste[i] > liste[i + 1]
                 <nowiki>[[</nowiki>Echanger (liste[i], liste[i+1])
                 échangé := vrai
             '''fin si'''
          '''fin Répéter'''         
         début := début + 1
     '''fin tant que'''
  '''fin fonction'''

=== Perl ===
<syntaxhighlight lang="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; /lmin-axe
	}
	return @v;
}
</syntaxhighlight>



=== Python ===
<syntaxhighlight lang="python">
def tri_cocktail(tab):
    echange=True
    debut=0
    fin=len(tab)-2
    while echange:
        echange=False
        for i in range(0,len(tab)-1):
            if tab[i]>tab[i+1]:
                tab[i],tab[i+1]=tab[i+1],tab[i]
                echange=True
        for i in range(len(tab)-2,-1,-1):
            if tab[i]>tab[i+1]:
                tab[i],tab[i+1]=tab[i+1],tab[i]
                echange=True
</syntaxhighlight>

=== 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.
<syntaxhighlight lang="text">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
</syntaxhighlight>

== 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. En effet, comme le tri à bulles traverse toujours la liste dans la 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 (langage)|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 [[tri à bulles#Variantes de l'algorithme|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]]<ref>W. Dobosiewicz. “An efficient variation of bubble sort.” Information Processing Letters 11, 1980, 5–6.</ref>, permet des gains très largement plus significatifs dès que le nombre d'éléments à trier devient assez élevé.

== Complexité ==
La [[complexité en temps|complexité algorithmique]] du tri cocktail est de <math>O(n^2)</math> dans le pire des cas et dans le cas moyen, mais elle devient plus proche de <math>O(n)</math> 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 <math>O(k*n)</math>.

Dans son livre de référence sur l'algorithmique, ''The Art of Computer Programming''{{note|texte=Donald Knuth, ''{{lang|en|The Art of Computer Programming}}'', {{vol.|3}} : ''{{lang|en|Sorting and Searching}}'', 1973, p. 110.}}, [[Donald Knuth]] discute brièvement du tri cocktail et de quelques autres améliorations du tri à bulles. En conclusion, Knuth écrit que :
{{Citation bloc|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 ==
{{Références}}

== Voir aussi ==

=== Articles connexes ===
* [[Tri à bulles]], l'algorithme dont dérive 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 <math>O(n log n)</math> lui permet de rivaliser plus ou moins avec les tris réputés rapides comme le [[tri rapide]] (''{{lang|en|quick sort}}''), le [[tri fusion]] (''{{lang|en|merge sort}}'') ou le [[tri de Shell]] (''{{lang|en|Shell sort}}'').

=== Liens externes ===
* {{Note autre projet|wikibooks|Algorithm Implementation/Sorting/Cocktail sort|''Cocktail sort''|début=Mise en œuvre de l'algorithme de tri|rôle=lien externe|langue=en}}
* {{en|texte=[http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html Java source code and an animated demo of cocktail sort (called bi-directional bubble sort) and several other algorithms]}}
* {{en|texte=[http://www.sharpdeveloper.net/content/archive/2007/08/14/dot-net-data-structures-and-algorithms.aspx .NET Implementation of cocktail sort and several other algorithms]}}
* {{en|texte=[http://www.hermann-gruber.com/lehre/sorting/Shaker/Shaker.html Interactive demo of cocktail sort]}}

{{Palette|Algorithmes de tri}}
{{Portail|informatique théorique}}

[[Catégorie:Algorithme de tri|Cocktail, Tri]]