Gnome sort

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 atribuida a Hamid Sarbazi-Azad quien lo desarrolló en el año 2000 y al que llamó Stupid sort (Ordenamiento estúpido).

Ejemplo de la operativa paso a paso

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 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 cocktail shaker (agitador de cocteles), por la forma en que trabaja...

Cumple estrictamente hablando con la complejidad O().


Descripción[editar]

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.

Pseudocódigo[editar]

  i := 1
  mientras i ≤ len- 1
    si a[i-1] ≤ a[i]
        i := i+1
    sino
        intercambiar a[i-1] y a[i]
        i := i - 1
        si i = 0
          i := 1
 }


Referencias[editar]

Enlaces externos[editar]