Oyelami’s Sort

Oyelami’s Sort

Le tri Oyelami

Cet algorithme de tri a été proposé par le Dr Oyelami Olufemi Moses qui l'a - modestement - appelé Oyelami's Sort.

L'idée est, encore une fois, de corriger le problème des "tortues" du tri à bulle. Le Dr Oyelami Olufemi propose d'utiliser un tri cocktail classique mais en le faisant précéder d'une phase inspirée du tri par la méthode de Batcher. Vous en trouverez une description (en anglais) ici.

L'algorithme divise donc les éléments à trier dans des sous-séquences (comme pour un tri de Shell), mais en comparant le premier élément avec le dernier et en les permutant si le premier est supérieur au dernier. Ensuite l'algorithme compare le second avec l'avant dernier et les permutte éventuellement, puis le troisième avec l'antépénultième etc...

Ce processus se poursuit jusqu'à ce que les deux derniers éléments intermédiaires consécutifs soient comparées ou jusqu'à ce qu'il reste un seul élément dans le milieu.

Après cela, c'est un tri bulle bidirectionnel qui est appliquée pour trier les éléments adjacents.

Cette approche réduit légérement le nombre de comparaisons et d'inversions effectuées.

L'animation ci-après détaille le fonctionnement de ce tri :

Visualisation du tri Oyelami

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

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



 



Ce tri n'est pas stable, comme vous pouvez le vérifier ici.

Les performances de ce tri sont certes meilleures que celles d'un tri à bulle classique, et même que celles d'un tri cocktail ou d'un tri Gnome mais restent bien inférieures à celles d'un tri à peigne ou d'un tri Shell.

Vous pouvez vérifier ces performances ici.

L'algorithme du Dr Oyelami Olufemi n'a donc rien de révolutionnaire. Il s'agit d'une petite amélioration du tri bulle dont le principal intérêt réside dans sa facilité de codage.