Tri cocktail

Problèmes liés	Algorithme de tri, tri stable (en)
Structure des données	Tableau
Basé sur	Tri à bulles

Complexité en temps

Pire cas	${\displaystyle O(n^{2})}$
Moyenne	${\displaystyle O(n^{2})}$
Meilleur cas	${\displaystyle O(n)}$

Complexité en espace

Pire cas	${\displaystyle O(1)}$

modifier - modifier le code - modifier Wikidata

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).

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
        

         Répéter pour tout  i entre 0 et liste.taille - 2
            si liste[i] > liste[i + 1]
                [[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]
                [[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 Optimisation en ignorant la partie déjà triée).

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

         Répéter pour tout  i entre début et fin
            si liste[i] > liste[i + 1]
                [[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]
                [[Echanger (liste[i], liste[i+1])
                échangé := vrai
            fin si
         fin Répéter         
        début := début + 1
    fin tant que
 fin fonction

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;
}

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

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

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 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é.

La complexité algorithmique du tri cocktail est de ${\displaystyle O(n^{2})}$ dans le pire des cas et dans le cas moyen, mais elle devient plus proche de ${\displaystyle 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 ${\displaystyle 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.

• 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 ${\displaystyle 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).

• (en) Mise en œuvre de l'algorithme de tri Cocktail sort, sur Wikibooks en anglais
• (en) Java source code and an animated demo of cocktail sort (called bi-directional bubble sort) and several other algorithms
• (en) .NET Implementation of cocktail sort and several other algorithms
• (en) Interactive demo of cocktail sort

v · m Algorithmes de tri
Tris par comparaisons	Sans hypothèse autre Complexité moyenne ${\displaystyle {\mathcal {O}}(n\log n)}$ Tri rapide Tri fusion Tri par tas Introsort Smoothsort Timsort Tri arborescent Tri à peigne (?) Tri de Shell (?) Complexité moyenne ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri à bulles Tri par insertion Tri par sélection Tri cocktail Complexité moyenne moins bonne que ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri spaghetti Tri stupide Tri faire-valoir Avec hypothèse supplémentaire Tri comptage Tri par base Tri par paquets Réseau de tri Tri bitonique Tri pair-impair
Tri utilisant d'autres opérations	Tri de crêpes Algorithme de tri externe Tri topologique
Applications	Problème du drapeau hollandais Recherche dichotomique

• Portail de l'informatique théorique