Ordenamiento de Oyelami

Ordonamiento de Oyelami

Este algoritmo de ordonamiento fue propuesta por el Dr. Moisés Olufemi Oyelami que - con modestia - llama Oyelami's Sort.

La idea es corregir el problema de "los Tortugas " del ordonamiento de burbuja. Dr. Olufemi Oyelami propone el uso de ordonamiento cocktail pero precediendo una fase inspirado en el método de ordonamiento de Batcher. Puede encontrar una descripción ( en Inglés ) aquí.

Este método reduce ligeramente el número de comparaciones realizadas.

Representación animada del ordenación de Oyelami :

Representación animada del ordenación de Oyelami

  1. PROCEDIMIENTO oyelami_sort ( VECTOR a[1:n])
  2.  
  3. dirección ← 'delantera', principio ← 1, fin ← n-1, actual ← 1
  4.  
  5. PARA i VARIANDO DE 1 HASTA n/2 HACER
  6.   SI a[i] > a|n-i] ENTONCES intercambiar a[i] y a[n-i]
  7. FIN PARA
  8. REPETIR
  9.    permut ← FALSO
  10.    REPETIR
  11.        SI a[actual] > a[actual + 1] ENTONCES
  12.            intercambiar a[actual] et a[actual + 1]
  13.            permut ← VERDADERO
  14.        FIN SI  
  15.        SI (dirección='delantera') ENTONCES
  16.            actual ← actual + 1            
  17.        SI NO
  18.            actual ← actual - 1
  19.        FIN SI
  20.    MIENTRAS QUE ((dirección='delantera') Y (actual<fin)) O ((dirección='trasera') Y (actual>principio))
  21.    SI (dirección='delantera') ENTONCES
  22.        dirección ← 'trasera'
  23.        fin ← fin - 1
  24.    SI NO
  25.        dirección ← 'delantera'
  26.        principio ← principio + 1
  27.    FIN SI
  28. MIENTRAS QUE permut = VERDADERO
  29.  
  30. FIN PROCEDIMIENTO
  1. let oyelami_sort vector =
  2.     let l = (Array.length vector) - 1 in
  3.     for i=0 to (l / 2) do
  4.         if vector.(i) > vector.(l - i) then
  5.         begin
  6.             let temp = vector.(i) in
  7.             begin
  8.                    vector.(i) <- vector.(l - i);
  9.                    vector.(l - i) <- temp;            
  10.             end;
  11.         end;
  12.     done;
  13.     let permut = ref true and actual = ref 0 and dirección = ref 1
  14.     and principio = ref 0 and fin = ref ((Array.length vector) - 2)  in
  15.     while (!permut = true) do
  16.         permut := false;
  17.         while ((!dirección=1) && (!actual < !fin)) || ((!dirección = -1) && (!actual > !principio)) do
  18.             actual := !actual + !dirección;
  19.             if vector.(!actual) > vector.(!actual + 1) then
  20.             begin
  21.                 (* Intercambiamos los dos elementos *)
  22.                 permut := true;
  23.                 let temp = vector.(!actual) in
  24.                 begin
  25.                    vector.(!actual) <- vector.(!actual + 1);
  26.                    vector.(!actual + 1) <- temp;
  27.                 end
  28.             end
  29.         done;
  30.         if (!dirección = 1) then fin := !fin - 1 else principio := !principio + 1;
  31.         dirección := - !dirección;
  32.     done;
  33. vector;;
  1. type tab = array[1..20] of integer;
  2. procedure oyelami_sort(var vector : tab);
  3.  
  4. var permut : boolean;
  5.     actual, temp : integer;
  6.     dirección : integer;
  7.     principio,fin : integer;
  8.  
  9. begin
  10.     for actual:=1 to 10 do
  11.     begin
  12.         if vector[actual]>vector[21 - actual] then
  13.         begin
  14.             temp:=vector[actual];
  15.             vector[actual]:=vector[21 - actual];
  16.             vector[21 - actual] := temp;
  17.         end;
  18.     end;
  19.     actual:=1;dirección:=1;
  20.     principio:=0;fin:=20;
  21.     REPEAT
  22.         permut := false;
  23.         while ((actual<fin) and (dirección=1)) or
  24.         ((dirección=-1) and (actual>principio)) do
  25.         begin
  26.             actual:=actual+dirección;
  27.             if vector[actual]<vector[actual-1] then
  28.             begin
  29.                 temp:=vector[actual];
  30.                 vector[actual]:=vector[actual - 1];
  31.                 vector[actual - 1] := temp;
  32.                 permut:=true;
  33.             end;
  34.         end;
  35.         if dirección=1 then fin:=fin - 1 else principio:=principio + 1;
  36.         dirección:=-dirección;
  37.     UNTIL (not permut);
  38. end;
  1. def oyelami_sort(vector):
  2.     fin = len(vector)
  3.     for i in range(fin // 2):
  4.         if vector[i] > vector[fin - i - 1]:
  5.             vector[i], vector[fin - i - 1] = vector[fin - i - 1],vector[i]
  6.     permut,dirección,actual = True,1,0
  7.     principio,fin = 0,len(vector)-2
  8.     while permut == True:
  9.         permut = False
  10.         while (actual<fin and dirección==1) or \
  11.         (actual>principio and dirección==-1) :
  12.             # prueba si intercambio
  13.             if vector[actual] > vector[actual + 1]:
  14.                 permut = True
  15.                 # Intercambiamos los dos elementos
  16.                 vector[actual], vector[actual + 1] = \
  17.                 vector[actual + 1],vector[actual]
  18.             actual = actual + dirección
  19.         # Cambiamos el sentido
  20.         if dirección==1:
  21.             fin = fin - 1
  22.         else:
  23.             principio = principio + 1
  24.         dirección = -dirección
  25.     return vector  
  26.  
  1. typedef int bool;
  2. enum { false, true };
  3.  
  4. void oyelami_sort(int* vector) {
  5.     bool permut;
  6.     int actual=0, dirección=1;
  7.     int principio=1, fin=19;
  8.     for (actual=0;actual<=fin/2;actual++) {
  9.         if (vector[actual]>vector[fin - actual]) {
  10.                 int temp = vector[actual];
  11.                 vector[actual]=vector[fin - actual];
  12.                 vector[fin - actual]=temp;        
  13.         }
  14.     }
  15.     actual=0;
  16.     do {
  17.         permut=false;
  18.         while (((dirección==1) && (actual<fin)) || ((dirección==-1) && (actual>principio))) {
  19.             actual += dirección;
  20.             if (vector[actual]<vector[actual-1]) {
  21.                 int temp = vector[actual];
  22.                 vector[actual]=vector[actual-1];
  23.                 vector[actual-1]=temp;
  24.                 permut=true;
  25.             }
  26.         }
  27.         if (dirección==1) fin--; else principio++;
  28.         dirección = -dirección;
  29.     } while (permut);
  30. }

Use este algoritmo para resolver el pequeño conjunto de la página anterior :



 


Esta ordonamiento no es estable, como se puede comprobar aquí.

El rendimiento del ordonamiento de Oyelami es sin duda mejor que los de una ordonamiento de burbuja, e incluso como una de ordonamiento cocktail o ordonamiento Gnome pero siguen siendo muy inferiores a los de una Comb Sort ou e ordonamiento de Shell.

Usted lo puede verificar aquí.

El algoritmo Dr. Olufemi Oyelami por lo tanto no revolucionario. Esta es una pequeña mejora del ordonamiento de burbuja.