- 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ó.,[1] no halló evidencias de que existiera y en palabras suyas, dijo de él "the simplest sort algorithm"[2] (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 dió.
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²).
Contenido
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 contínuo 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 ModuleReferencias
Categoría:- Algoritmos de ordenamiento
Wikimedia foundation. 2010.
