Algoritmos de Ordenamiento en Python: El método de la Burbuja

Hay problemas en los que ordenar los datos de entrada es crucial para poder resolverlos. Como algunos de ustedes sabrán, python tiene un algoritmo poderoso de ordenamiento para listas, que actúa como un método sobre estas, en efecto, dada cualquier lista de números, p.e.,

Lista=[0, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 8, 8, 9, 11, 13, 22]

podemos ordenarla simplemente colocando:

Lista.sort()

Ahora bien, aunque posiblemente este método sobre listas sea la mejor opción para ordenarlas, cuando las entradas de la lista son números, no pasa lo mismo cuando son objetos no numéricos, ordenados mediante alguna función u orden parcial. Les daré un ejemplo que puede que les sea útil.

Supongamos que tenemos una lista de listas, dada por:

Lista2=[[1, 200, 50000],[1,2,3],[1],[100],[2,2,3,4,5,6,3,21],[1,2,5,2,5,7],[1,2,0,8,7,6],[5,6,4,8,3,2],[2,3],[1,2,99]]

y el orden parcial (o score), venga dado por, por ejemplo, el promedio de los valores de las entradas. ¿Podremos usar el método sort en esta lista?, la respuesta es claramente no. Este ordenará la lista utilizando la primera entrada en cada lista como referencia, lo cual no nos permitirá aplicar nuestro orden especial.

Solución:

Implementé el algoritmo de ordenamiento de burbuja (el cual es uno de los más fáciles), para resolver esta cuestión.

Pseudo-Código (Algoritmo de la Burbuja):

Una animación que clarifica bastante la forma en la que este algoritmo trabaja puede verse a continuación:

haga click en la imagen

El código:
### copia desde aquí ###

def orden(E):

    n=len(E)

    score=0

    for i in E:

        score=score+i

    score=float(score)/n

    return score

def ordenamiento(L):

    n=len(L)

    for i in range(1, n):

        for j in range(n-i):

            if orden(L[j])>orden(L[j+1]):

                L[j], L[j+1]=L[j+1], L[j]

    return L

# y ordenamos

Lista2=ordenamiento(Lista2)

### fin del algoritmo ###

Si aún no estas convencido de porque un algoritmo de orden flexible (como este) es importante y útil, no solo en programación, sino en ciencias en general, enunciaré un par de aplicaciones en las que ordenar puede ser crucial:

• Problemas de organización de tareas: Puede que necesites automatizar la realización de tareas, por una maquina, o por personas, y necesites hacerlo de la mejor forma, tomando en cuenta por ejemplo, la prioridad, o las dependencias intra-tareas. En este caso, los ordenes son especiales, y los tipos de datos de entrada no son a priori números.
  
  
• Análisis de Propagación: Dado el origen de una enfermedad en una ciudad, y como datos, todas las ciudades circunvecinas, y como meta-datos las distancias y la cantidad promedio de flujo de personas intra-ciudades. Podemos usar un algoritmo como el explicado, para las ciudades por el riesgo de adquirir la enfermedad, donde dicho riesgo es una función de los datos y los meta-datos.
  
• Y existen muchos mas ejemplos ... creo que en este punto, las palabras sobran, sino, ordena los siguientes libros por temática:

Saludos.

Si te ha gustado este artículo, compártelo en facebook, twitter, google+, coméntalo, envíalo por correo, y si quieres mas información, pídela. Si no te gusta, critícalo. Tu tienes completo control sobre los contenidos de este blog.

Histogramas con Python + Matplotlib

Uno de los paquetes mas completos para graficar con Python es Matplotlib. El día de hoy explicaré como graficar un histograma sencillo utilizando el sub-paquete pylab y las funciones hist y show.

import random
from matplotlib.pylab import hist, show
v=range(0,21)
data=[]
for i in range(1000):
    data.append(random.choice(v))

hist(data,21, (0,20))
show()

Resultado

Explicación linea a linea

Linea 1.  import random

Importamos el paquete random para generar datos de manera aleatoria para el histograma.

Linea 2. from matplotlib.pylab import hist, show

Del subpaquete pylab de matplotlib importamos las funciones hist y show. La función hist es la que crea los datos del histograma, y show muestra en pantalla dicho histograma.

Linea 3. v=range(0,21)

Creamos un vector de posibles resultados del experimento, es decir, en nuestro experimento, los posibles resultados varían entre 0 y 20 (en total 21 datos posibles).

Linea 4. data=[]

Se crea una lista donde guardaremos la frecuencia en la que aparece cada uno de los posibles resultados del experimento.

Linea 5 y 6.
for i in range(1000):
____data.append(random.choice(v))

Generamos los datos de nuestro experimento. Para ello hacemos una elección aleatoria de los posibles resultados de nuestro experimento. En nuestro caso, se está realizando el experimento en el que se elige mil veces un número entre 0 y 20, en cada extracción se repone el número elegido y la probabilidad de elegir cada uno de los números es la misma. Dicho de otra forma, la distribución de probabilidad es uniforme.

Linea 7. hist(data,21, (0,20))

Generamos el histograma con la función hist. Observar que los argumentos de la función hist son: los datos, la cantidad de diferentes valores del experimento, y el rango de dichos valores. 

Linea 8. show()

Por último, usamos el comando show() para graficar el histograma generado.

Si te ha gustado este artículo, compártelo en facebook, twitter, google+, coméntalo, envíalo por correo, y si quieres mas información, pídela. Si no te gusta, critícalo. Tu tienes completo control sobre los contenidos de este blog.