Gnome sort (apodado stupid sort ) es una variación del algoritmo de ordenamiento por inserción que no utiliza bucles anidados. Gnome sort fue propuesto originalmente por el informático iraní Hamid Sarbazi-Azad (profesor de Ciencias Informáticas e Ingeniería en la Universidad Tecnológica Sharif ) [1] en 2000. El ordenamiento se llamó primero stupid sort [2] (que no debe confundirse con bogosort ), y luego fue descrito por Dick Grune y llamado gnome sort . [3]
Gnome sort realiza al menos tantas comparaciones como el ordenamiento por inserción y tiene las mismas características de tiempo de ejecución asintótica . Gnome sort funciona construyendo una lista ordenada elemento por elemento, colocando cada elemento en el lugar adecuado en una serie de intercambios. El tiempo de ejecución promedio es O ( n 2 ) pero tiende a O ( n ) si la lista está inicialmente casi ordenada. [4] [nota 1]
Dick Grune describió el método de clasificación con la siguiente historia: [3]
El método Gnome Sort se basa en la técnica utilizada por el gnomo de jardín holandés estándar (en holandés: tuinkabouter).
Así es como un gnomo de jardín clasifica una fila de macetas .
Básicamente, mira la maceta que está a su lado y la anterior; si están en el orden correcto, avanza una maceta hacia adelante; de lo contrario, las intercambia y retrocede una maceta.
Condiciones límite: si no hay ninguna maceta anterior, avanza; si no hay ninguna maceta a su lado, ya está.— "Gnome Sort: el algoritmo de ordenación más simple". Dickgrune.com
Aquí hay un pseudocódigo para la ordenación de gnome utilizando una matriz basada en cero :
procedimiento gnomeSort(a[]): posición := 0 mientras pos < longitud(a): si (pos == 0 o a[pos] >= a[pos-1]): posición := posición + 1 De lo contrario : intercambia a[pos] y a[pos-1] posición := posición - 1
Dada una matriz no ordenada, a = [5, 3, 2, 4], la ordenación de gnome realiza los siguientes pasos durante el bucle while. La posición actual se resalta en negrita y se indica como un valor de la variable pos.
