Le tri shaker ou tri cocktail

Attention ! cette page va être migrée vers https://lwh-21.github.io/Algos/

Le tri shaker

Le tri "Shaker", également appelé tri "Cocktail", tri "Shuttle", tri "boustrophédon" ou tri à bulles bidirectionnel est une variante du tri à bulles.

Son principe est identique à celui du tri à bulles, sauf qu'il change de direction à chaque passe. C'est une légère amélioration car il permet non seulement aux plus grands éléments de migrer vers la fin de la série mais également aux plus petits éléments de migrer vers le début.

L'animation ci-après détaille le fonctionnement du tri shaker :

Démonstration du tri shaker

  1. PROCEDURE tri_shaker ( TABLEAU a[1:n])
  2.  
  3. sens ← 'avant', debut ← 1, fin ← n-1, en_cours ← 1
  4.  
  5. REPETER
  6.    permut ← FAUX
  7.    REPETER
  8.        SI a[en_cours] > a[en_cours + 1] ALORS
  9.            echanger a[en_cours] et a[en_cours + 1]
  10.            permut ← VRAI
  11.        FIN SI  
  12.        SI (sens='avant') ALORS
  13.            en_cours ← en_cours + 1            
  14.        SINON
  15.            en_cours ← en_cours - 1
  16.        FIN SI
  17.    TANT QUE ((sens='avant') ET (en_cours<fin)) OU ((sens='arriere) ET (en_cours>debut))
  18.    SI (sens='avant') ALORS
  19.        sens ← 'arriere'
  20.        fin ← fin - 1
  21.    SINON
  22.        sens ← 'avant'
  23.        debut ← debut + 1
  24.    FIN SI
  25. TANT QUE permut = VRAI
  26.  
  27. FIN PROCEDURE
  1. let tri_shaker tableau =
  2.     let permutation = ref true and en_cours = ref 0 and sens = ref 1
  3.     and debut = ref 0 and fin = ref ((Array.length tableau) - 2)  in
  4.     while (!permutation = true) do
  5.         permutation := false;
  6.         while ((!sens=1) && (!en_cours < !fin)) || ((!sens = -1) && (!en_cours > !debut)) do
  7.             en_cours := !en_cours + !sens;
  8.             if tableau.(!en_cours) > tableau.(!en_cours + 1) then
  9.             begin
  10.                 (* On echange les deux elements *)
  11.                 permutation := true;
  12.                 let temp = tableau.(!en_cours) in
  13.                 begin
  14.                    tableau.(!en_cours) <- tableau.(!en_cours + 1);
  15.                    tableau.(!en_cours + 1) <- temp;
  16.                 end
  17.             end
  18.         done;
  19.         if (!sens = 1) then fin := !fin - 1 else debut := !debut + 1;
  20.         sens := - !sens;
  21.     done;
  22. tableau;;
  1. type tab = array[1..20] of integer;
  2. procedure tri_shaker(var tableau : tab);
  3.  
  4. var permutation : boolean;
  5.     en_cours, temp : integer;
  6.     sens : integer;
  7.     debut,fin : integer;
  8.  
  9. begin
  10.     en_cours:=1;sens:=1;
  11.     debut:=0;fin:=20;
  12.     REPEAT
  13.         permutation := false;
  14.         while ((en_cours<fin) and (sens=1)) or
  15.         ((sens=-1) and (en_cours>debut)) do
  16.         begin
  17.             en_cours:=en_cours+sens;
  18.             if tableau[en_cours]<tableau[en_cours-1] then
  19.             begin
  20.                 temp:=tableau[en_cours];
  21.                 tableau[en_cours]:=tableau[en_cours - 1];
  22.                 tableau[en_cours - 1] := temp;
  23.                 permutation:=true;
  24.             end;
  25.         end;
  26.         if sens=1 then fin:=fin - 1 else debut:=debut + 1;
  27.         sens:=-sens;
  28.     UNTIL (not permutation);
  29. end;
  1. def tri_shaker(tableau):
  2.     permutation,sens,en_cours = True,1,0
  3.     debut,fin = 0,len(tableau)-2
  4.     while permutation == True:
  5.         permutation = False
  6.         while (en_cours<fin and sens==1) or \
  7.         (en_cours>debut and sens==-1) :
  8.             # Test si echange
  9.             if tableau[en_cours] > tableau[en_cours + 1]:
  10.                 permutation = True
  11.                 # On echange les deux elements
  12.                 tableau[en_cours], tableau[en_cours + 1] = \
  13.                 tableau[en_cours + 1],tableau[en_cours]
  14.             en_cours = en_cours + sens
  15.         # On change le sens du parcours
  16.         if sens==1:
  17.             fin = fin - 1
  18.         else:
  19.             debut = debut + 1
  20.         sens = -sens
  21.     return tableau  
  22.  
  1. typedef int bool;
  2. enum { false, true };
  3.  
  4. void tri_shaker(int* tableau) {
  5.     bool permutation;
  6.     int en_cours=0, sens=1;
  7.     int debut=1, fin=19;
  8.     do {
  9.         permutation=false;
  10.         while (((sens==1) && (en_cours<fin)) || ((sens==-1) && (en_cours>debut))) {
  11.             en_cours += sens;
  12.             if (tableau[en_cours]<tableau[en_cours-1]) {
  13.                 int temp = tableau[en_cours];
  14.                 tableau[en_cours]=tableau[en_cours-1];
  15.                 tableau[en_cours-1]=temp;
  16.                 permutation=true;
  17.             }
  18.         }
  19.         if (sens==1) fin--; else debut++;
  20.         sens = -sens;
  21.     } while (permutation);
  22. }

Si on retient la méthode du tri shaker pour le petit jeu page précédente, on a :



 


Complexité du tri shaker

Dans le meilleur des cas, avec des données déjà triées, l'algorithme ne parcourer qu'une seule fois le tableu en n'effectuant seulement que n - 1 comparaisons. Sa complexité dans le meilleur des cas est donc linéaire, en Θ(n).

Complexite du tri shaker dans le meilleur des cas Nombre d'opérations Nombre d'elements à trier Θ(n)

Dans le pire des cas, avec des données triées à l'envers, on a une complexité du tri shaker en Θ(n2).

Complexite du tri shaker le pire des cas Nombre d'opérations Nombre d'elements à trier Θ(n2)

Si tous les éléments de la série à trier sont distincts et que toutes leurs permutations sont équiprobables, la complexité du tri shaker est également en Θ(n2)

Complexite du tri shaker en moyenne Nombre d'opérations Nombre d'elements à trier Θ(n2)