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).
| Problèmes liés |
Algorithme de tri, tri stable (en) |
|---|---|
| Structure des données | |
| Basé sur |
| Pire cas | |
|---|---|
| Moyenne | |
| Meilleur cas |
| Pire cas |
|---|
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
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).
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
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
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;
}
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
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. 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é.
Complexité
La complexité algorithmique du tri cocktail est de dans le pire des cas et dans le cas moyen, mais elle devient plus proche de 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 .
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é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 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).
Liens externes
- (en) Mise en œuvre de l'algorithme de tri 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