Gnome sort

De Wikipedia, la enciclopedia libre

El algoritmo de ordenación conocido como gNome_sort fue inventado por Dick Grune y en palabras suyas "the simplest sort algorithm" (es el algoritmo más simple) y quizás tenga razón.

Netamente es un algoritmo de burbuja con una clara particularidad: recorre el array a ordenar como una cremallera, en un va y ven, o bien puede ser definido como un ordenamiento de burbuja bidireccional, que a su vez son llamados también cokctail shaker (agitador de cocteles), por la forma en que trabaja...

Cumple estrictamente hablando con la complejidad O(n²).

[editar] Descripción

Tras iniciarse el array compara parejas de elementos e intercambia el menor por el mayor, al alcanzar el extremo del array, deposita el mayor, marca un puntero final en una unidad menos e invierte el sentido de las comparaciones, va descendiendo desde el penúltimo hasta el primer elemento, allí deposita el menor hallado aumenta puntero de inicio con valor 1, y nuevamente vuelve a realizar comparaciones ascendiendo... el bucle termina cuando los dos punteros se diferencian en una unidad, es decir acaba en el centro del array o subarray.

[editar] Implementaciones

[editar] Pseudocódigo

  función gnomeSort(a[0..tam-1]) {
  i := 1
  j := 2
  mientras i ≤ tam - 1
    si a[i-1] ≤ a[i]
        i := j
        j := j + 1 
    sino
        intercambiar a[i-1] y a[i]
        i := i - 1
        if i = 0
          i := 1
 }

[editar] Código en Java

public class gnome
{
    public static void gnomeSort(int[] v)
    {
        int i = 1, aux= 0;
        while(i < v.length)
        {
            if (i == 0 || v [i-1] <= v [i])
                i++;
            else
            {
                aux = v [i - 1];
                v[i - 1] = v[i];
                v[i] = aux ;
                i --;
            }
        }
    }
 
    public static void main (String [] aaa)
    {
        gnomeSort(int[]);
    }
}

[editar] Código en Visual Basic

Se asume un array público y a la función se le pasan 2 parámetros, que indican 2 elementos dentro del array, si los elementos son los extremos del array, ordenaría completamente el array, si los elementos son índices internedios, ordenaría el tramo de array comprendido entre ambos elementos inclusive

Ordena un array de ámbito público con el método gNome, realiza previamente un control de desbordamiento:

NOTA: cambiada la cabecera de los comentarios para no reñirse con wiki

Function fOrdenGnome(ordMin As Long, ordMax As Long) As string
   if ordMin < Lbound(array) or ordMin > Ubound(array) then return "ordMin fuera de límites"        
   if ordMax < Lbound(array) or ordMax > Ubound(array) then return "ordMax fuera de límites" 
                                                        -
   Dim topIni As Integer       -puntero indicador de elementos ordenados al inicio
   Dim topFin As Integer       -puntero indicador de elementos ordenados al fin
   Dim indices As Long         -cantidad de itemes en juego 
   Dim dir As Integer          -especifica al puntero la dirección de avance
   Dim dirL As Integer         -puntero que transforma un elemento absoluto en su antecesor cuando avanza hacia abajo
   Dim dirU As Integer         -puntero que transforma un elemento absoluto en su sucesor cuando avanza hacia arriba
   Dim i As Long               -el puntero base
                                                        -
   topIni = ordMin                         -valores previos
   topFin = ordMax
   indices = ordMax - ordMin + 1
   dir = 1
   dirU = 1
   dirL = 0
                                                         -
   Do          
       Do
           If array(i + dirL) > array(i + dirU) Then
               call fSwap2(i + dirL, i + dirU)
           End If
           i = i + dir                                   -incrementa el puntero local
       Loop Until i = topIni Or i = topFin   -comprueba si se llegó a un extremo u otro
       If dir = 1 Then                       -si la dirección era hacia arriba se aumenta el tope superior 
           topFin = topFin - 1
           dirL = -1: dirU = 0                           -invertimos los punteros locales para hacer la comparacón en la forma: i-1 > i
       Else                                        -si la dirección era hacia abajo se aumenta el tope inferior 
           topIni = topIni + 1                     
           dirL = 0: dirU = 1                            -invertimos los punteros locales para hacer la comparacón en la forma: i > i+1
       End If
       dir = dir * (-1)                                  -tras alcanzar un tope rebotamos hacia el otro lado
       i = i + dir                                       -y ajustamos el puntero en la nueva dirección  
   Loop While (topFin - topIni) > 2                -vamos estrechando el cerco, acaba cuando se llega al centro fin-ini=1
                                                         -
   return "OK"
End Function

-intercambia el valor de 2 variables, de un array de ámbito público entre si
function fSwap2(indiceA as long,indiceB as long) as string  
   dim temp as long
                                            -
   -if indiceA < Lbound(array) or indiceA> Ubound(array) then return "indiceA fuera de límites" 'comprueba integridad de límites 
   -if indiceB < Lbound(array) or indiceB> Lbound(array) then return "indiceB fuera de límites" 
                                            -
   temp=array(indiceA)                      -una variable temporal contiene el valor de indiceA
   array(indiceA)=array(indiceB)            -indiceA adopta el valor de indiceB
   array(indiceB)=temp                      -indiceB toma el valor que originalmente estaba en indiceA 
                                            -
   return "OK"                        -devuelve sin errores
end function

[editar] Código en Python

def gnomesort(a):
    n = len(a) - 1
    while n:
        if a[n - 1] > a[n]:
            a[n - 1], a[n] = a[n], a[n - 1]
            if n + 1 < len(a): n += 1
            else: n -= 1
        else: n -= 1