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 atribuida a Hamid Sarbazi-Azad quien lo desarrolló en el 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, pues lo describió en sólo cuatro líneas de código. Dick Grune se basó en los gnomos de jardín holandés y la manera en que se colocan dentro de 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 vaivén, o bien puede ser definido como un ordenamiento de burbuja bidireccional, que a su vez son llamados también cocktail shaker (agitador de cócteles), por la forma en que trabaja...

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

1. ↑ url=http://xlinux.nist.gov/dads/HTML/gnomeSort.html
2. ↑ http://dickgrune.com/Programs/gnomesort.html