Google+ Seguidores

sábado, 25 de agosto de 2018

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:

Ejemplo de la operativa paso a paso

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.

3 comentarios :
Write comentarios
  1. 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.

    ResponderEliminar
    Respuestas
    1. 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.

      Eliminar

Tu comentario es importante y nos motiva a seguir escribiendo...

Powered by Blogger .