Gnome Sort - Algoritmos de Ordenamiento con Python
introducción:
Hola amigos de Internet. Les doy la bienvenida a Mi Diario Python, el mejor blog en español para Aprender Python.
En este corto y sencillo articulo, veremos que es el Gnome Sort y realizaremos una sencilla implementación en Python.
¿Interesado? Sigue leyendo.
Gnome Sort:
El Gnome_Sort se puede decir que es el algoritmo más simple de todos. Dick Grune, su inventor, lo describió en 4 lineas de código.
Si se analiza con atención, se puede observar que es un algoritmo de burbuja, con la peculiaridad de que recorre el array a ordenar como una cremallera, de la siguiente manera:
Sí, efectivamente, es como un algoritmo de burbuja bidireccional.
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.
El pseudocódigo del algoritmo es el siguiente:
i ← 1
Mientras i ≤ len- 1
Si i=1 o a[i-1] ≤ a[i]
i ← i+1
Sino
temp ← a[i-1]
a[i-1] ← a[i]
a[i] ← temp
i ← i-1
Si i = 0
i ← 1
Finsi
Finsi
FinMientras
Para implementarlo a Python tuve que cambiarlo un poco. Así me ha quedado:
def gnome_sort(lista): i = 0 n = len(lista) while i < n: if i == 0 or lista[i] >= lista[i-1]: i = i+1 else: temp = lista[i-1] lista[i-1] = lista[i] lista[i] = temp i = i-1 return lista lista = [4,1,2,6,3,77,456,33,992] resultado = gnome_sort(lista) print(resultado)
[1, 2, 3, 4, 6, 33, 77, 456, 992]
Muy fácil e informativo.
¿Alguna duda? No dudes en dejar tu comentario.
Mi nombres es Luis, y fue un placer compartir mis conocimientos con todos ustedes :D.
-
-
Luis Salcedo dice: Hola Israel. Sí, porsupuesto, es valido. Lo hice de esta manera por que estamos usando el pseudocódigo como base. Otra es que de esta manera cualuiera con pocos conocimientos del lenguaje puede entender mejor como funciona.
-
Luis Salcedo Deja una respuesta
Curioso algoritmo de ordenación, creo que nunca lo he visto y me parece sencillo de entender y potente.
Tengo una duda y es cuando intercambias los valores, teniendo en cuenta que estás en Python no te hace falta una variable temporal, puedes hacer simplemente:
lista[i-1], lista[i] = lista[i], lista[i-1]
Un saludo.