Gnome sort

El algoritmo de ordenación conocido como gNome_sort tiene una historia de invención cuasi paralela. Durante un tiempo existió la polémica sobre su invención, finalmente atribuída a Hamid Sarbazi-Azad quien lo desarrolló en en año 2000 y al que llamó Stupid sort (Ordenamiento estúpido).

Cuando Dick Grune lo inventó (más apropiadamente, 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, pués lo describió en solo 4 líneas de código. Dick Grune se basó en los gnomos de jardín holandés, en como se colocan en los maceteros (ver la referencia anterior) y de ahí también el nombre que le dio.

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²).

Descripción

El algoritmo empieza comparando la primera pareja de valores, si están en orden incrementa el puntero y de nuevo realiza la comparación, si no están en orden, se pasa, el menor a la izquierda y el mayor a la derecha, y se reduce el puntero, ahora la comparación es con el elemento anterior, si no hay un elemento anterior se pasa al siguiente elemento. Cuando el puntero alcanza el extremo superior del array ya está totalmente ordenado.

Cuando compara hacia arriba va sin hacer intercambios, es que el par bajo examen está ordenado entre si, y cuando compara hacia abajo, va haciendo intercambios. El proceso aparece como un zigzagueo continuo a un lado y otro.

La operación empieza por el puntero en el punto más bajo y cuando llega al extremo superior ha terminado de ordenar el array.

Para realizar un ordenamiento inverso basta cambiar la decisión de intercambio de los elementos, es decir dejar los mayores abajo y los menores arriba.

Implementaciones

Pseudocódigo

  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
 }

Código en Vb.Net

Module Module1
    Private Sub swap(ByRef a As Integer, ByRef b As Integer)
        Dim temp As Integer
        temp = a
        a = b
        b = temp
    End Sub
 
    Private Sub gnomeSort(ByVal a() As Integer)
        Dim i As Integer
        i = 2
 
        While (i <= UBound(a))
            If (a(i - 1) <= a(i)) Then
                i = i + 1
            Else
                swap(a(i - 1), a(i))
                i = i - 1
                If i = 1 Then
                    i = 2
                End If
            End If
        End While
 
    End Sub
 
    Sub Main()
        Dim vect(50000) As Integer
        Dim X As Integer
 
        For x = 1 To UBound(vect)
            vect(X) = CInt(Rnd() * 50)
        Next
        gnomeSort(vect)
        For X = 1 To UBound(vect)
            Console.WriteLine(vect(X))
        Next
        Console.ReadKey()
    End Sub
End Module