Gnome Sort

Ordenación "Gnome"

El algoritmo de ordenación conocido como Gnome_sort fue inventada por Hamid Sarbazi-Azad, (profesor de la universidad de Sharif, una de las mayores universidades de Irán) quien lo desarrolló en el año 2000 y al que llamó Stupid sort (Ordenamiento estúpido).

Cuando Dick Grune lo reinventó y documentó, no halló evidencias de que existiera y en palabras suyas, dijo de él "the simplest sort algorithm" (es el algoritmo más simple) y quizás tenga razón, pues lo describió en sólo cuatro líneas de código. Dick Grune se basó en los gnomos de jardín holandés, en como se colocan en los maceteros y de ahí también el nombre que le dio.

El algoritmo es similar a la ordenación por inserción , excepto que , en lugar de insertar directamente el elemento a su lugar apropiado , el algoritmo realiza una serie de permutaciones , como en el ordenamiento de burbuja.

Representación animada del algoritmo :

Representación animada de la ordenación gnome

  1. PROCEDIMIENTO Gnome_sort(vector[])
  2.     pos := 1
  3.     MIENTRAS pos < longitud(vector)
  4.         SI (vector[pos] >= vector[pos-1])
  5.             pos := pos + 1
  6.         SI NO
  7.             intercambiar vector[pos] Y vector[pos-1]
  8.             SI (pos > 1)
  9.                 pos := pos - 1
  10.             FIN SI
  11.         FIN SI
  12.     FIN MIENTRAS
  13. FIN PROCEDIMIENTO
  1. let burbuja vector p =
  2.     let i_b = ref p in
  3.     while (!i_b>0) && (vector.(!i_b) < vector.(!i_b - 1)) do
  4.         let t = vector.(!i_b) in
  5.         begin
  6.             vector.(!i_b) <- vector.(!i_b - 1);
  7.             vector.(!i_b - 1) <- t;
  8.         end;
  9.         i_b := !i_b - 1;
  10.     done;;
  11.  
  12.  
  13. let  Gnome_sort vector =
  14.     for i_i = 1 to (Array.length vector) - 1 do
  15.         if vector.(i_i) < vector.(i_i - 1) then burbuja vector i_i;
  16.     done;
  17.     vector;;
  1. type tab = array[1..20] of integer;
  2.  
  3. PROCEDURE Gnome_sort(var vector : tab);
  4. var
  5.    i_b, i_i, t  : Integer;
  6.     (* i_b : Índice utilizado para la ordenación de burbuja
  7.     i_i : Índice utilizado para el ordenamiento por inserción *)
  8. begin
  9.     i_b := 1;
  10.     i_i := 2;
  11.     while i_b <= 20 do
  12.     begin
  13.         if vector[i_b-1] <= vector[i_b] then
  14.         begin
  15.             i_b := i_i;
  16.             i_i := i_i + 1
  17.         end else
  18.         begin
  19.             t := vector[i_b-1];
  20.             vector[i_b-1] := vector[i_b];
  21.             vector[i_b] := t;
  22.             i_b := i_b - 1;
  23.             if i_b = 0 then
  24.             begin
  25.                 i_b := i_i;
  26.                 i_i := i_i + 1
  27.             end
  28.         end
  29.     end;
  30. end;
  31.  
  1. def Gnome_sort(vector):
  2.     i_b,i_i,taille = 1,2,len(vector)
  3.     while i_b < taille:
  4.         if vector[i_b-1] <= vector[i_b]:
  5.             i_b,i_i = i_i, i_i+1
  6.         else:
  7.             vector[i_b-1],vector[i_b] = vector[i_b],vector[i_b-1]
  8.             i_b -= 1
  9.             if i_b == 0:
  10.                 i_b,i_i = i_i, i_i+1
  11.     return vector
  1. void burbuja(int* vector, int p) {
  2.     int i_b = p;
  3.     while ((i_b>0) && (vector[i_b]<vector[i_b - 1])) {
  4.         int t = vector[i_b -1];
  5.         vector[i_b - 1]= vector[i_b];
  6.         vector[i_b ] = t;
  7.         i_b --;
  8.     }
  9. }
  10.  
  11. void Gnome_sort (int* vector) {
  12.     for (int i_i=0;i_i<20;i_i++) burbuja(vector,i_i);
  13. }

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



 


Los siguientes gráficos muestran el aumento en el número de transacciones en relación con el número de elementos a ser ordenados.

Rendimiento del algoritmo

En el caso óptimo, con los datos ya ordenados, el algoritmo sólo effectura n comparaciones. Por lo tanto la complejidad en el caso óptimo es en Θ(n).

Rendimiento en el caso óptimo Número de operaciones Número de términos Θ(n)

En el caso desfavorable, con los datos ordenados a la inversa, la complejidad es en Θ(n2).

Rendimiento en el caso desfavorable Número de operaciones Número de términos Θ(n2)

En el caso medio, la complejidad de este algoritmo es también en Θ(n2)

Rendimiento en el caso medio Número de operaciones Número de términos Θ(n2)