Python tipo burbuja

Funciones y métodos de Python

Una clasificación de burbujas de Python recorre una lista y compara elementos uno al lado del otro. Si un elemento de la derecha es mayor que uno de la izquierda, los elementos se intercambian. Esto sucede hasta que se ordena la lista.

¿Necesita ordenar una lista? El tipo de burbuja te respalda. La clasificación de burbujas es un tipo de algoritmo estándar que clasifica listas. Es quizás el tipo más simple que existe, por lo que es perfecto para principiantes que son nuevos en los algoritmos de clasificación. 

En esta guía, vamos a discutir cómo funcionan los ordenamientos de burbujas y cómo se puede implementar un algoritmo de ordenamiento de burbujas de Python. Veremos un ejemplo para que comprenda cómo funciona cada parte de una clasificación de burbujas.




Clasificaciones de burbujas de Python

Una clasificación de burbujas compara pares de elementos adyacentes e intercambia esos elementos si no están en orden. Se implementa comúnmente en Python para ordenar listas de números sin clasificar. Las clasificaciones de burbujas son un algoritmo informático estándar.

Al utilizar una clasificación de burbujas, puede clasificar los datos en orden ascendente o descendente. A partir del primer elemento de una lista, una clasificación de burbujas comparará el primer y el segundo elemento. Si el primer elemento es mayor que el segundo, se produce un intercambio. 

Este proceso se repite hasta que se comprueban todos los elementos de una lista. Luego, una clasificación de burbujas recorrerá la lista nuevamente. Esto ocurre hasta que no es necesario realizar más intercambios.




¿Cuándo debería usar una clasificación de burbujas en Python?

Las clasificaciones de burbujas son un buen método de clasificación para usar cuando recién está comenzando para aprender acerca de los algoritmos de clasificación. Una clasificación de burbujas es una forma sencilla de ordenar una lista de elementos que no aparecen en orden. 

Los tipos de burbujas funcionan mejor cuando tienes una lista con solo unos pocos objetos. Esto se debe a que cuando una clasificación de burbujas solo tiene que hacer algunas comparaciones, es muy rápida. Cuando necesite ordenar una lista más grande, existen algoritmos más eficientes que puede utilizar. La mayoría de los desarrolladores optarían por utilizar un método como el ordenamiento por inserción para ordenar una lista más larga de elementos.

El 81% de los participantes afirmaron que se sentían más seguros acerca de sus perspectivas laborales después de asistir a un campamento de entrenamiento. Asigne a un bootcamp hoy mismo.

El graduado promedio de bootcamp pasó menos de seis meses en la transición de carrera, desde comenzar un bootcamp hasta encontrar su primer trabajo.

Entremos en el malezas y empezar a entender cómo funciona un tipo de burbuja. Comenzaremos con la siguiente lista, cuyos elementos aparecen en el orden incorrecto:


7 19 4 12

Nuestra clasificación de burbujas comienza comparando el primer y segundo elemento de nuestra lista. Si el primer elemento es mayor que el segundo, luego intercambiamos estos dos elementos.

En este ejemplo, vamos a comparar 7 y 19. 7 no es mayor que 19, por lo que permanece en el mismo lugar . Nuestra lista ahora luce igual que antes:

7 19 4 12

Pasaremos ahora a comparar el segundo y tercer elemento en nuestra lista. 19 es mayor que 4, lo que significa que debemos intercambiarlos. Nuestra lista ahora se ve así:

 7 4 19 12

Ahora podemos comparar el tercero y cuartos elementos de nuestra lista. 19 es mayor que 12, así que intercambiamos los dos números:

7 4 12 19

Llegando al final de una lista

Nuestra lista ya está empezando a verse ordenada. Pero hemos llegado al final de nuestra lista y no está ordenada. ¿Qué está pasando? Las clasificaciones de burbujas realizan varias pasadas a través de una lista, lo que significa que siguen ejecutándose hasta que se clasifican todos los elementos de una lista. 

Nuestra clasificación de burbujas comenzará de nuevo desde el principio hasta que se ordene la lista. Cada vez que la lista comienza a ordenar valores desde el principio, llamamos un pase . En este ejemplo, nuestra clasificación de burbujas comparará 7 y 4. 7 es mayor que 4, por lo que intercambiamos los elementos:

Nuestro algoritmo compara 7 y 12. No es necesario intercambiar, así que seguiremos adelante. . Comparamos 12 y 19. Nuevamente, no es necesario ningún intercambio. Ahora que hemos llegado al final de nuestra lista, está claro que no es necesario realizar más cambios. 

¿Notó que nuestro algoritmo siguió funcionando incluso después de ordenar nuestra lista? Eso se debe a que una clasificación de burbujas continuará intercambiando elementos hasta que compare todos los elementos de una lista para cada elemento de la lista. Nuestro algoritmo no se detendrá hasta que se hayan realizado todos los cambios.




Programa Python de clasificación de burbujas

Hasta ahora, hemos estado intercambiando números en una tabla. Es cierto que logramos ordenar nuestra lista, pero no tenemos que hacerlo manualmente. Después de todo, los tipos de burbujas son un algoritmo informático; Consigamos una computadora para ejecutar el algoritmo por nosotros.


Comencemos escribiendo una función Python que ordena una lista de números en orden ascendente:

 def sortList (matriz): para el elemento en rango (len (matriz)): para j en rango (0, (len (matriz) ) - elemento - 1)): si matriz [j] & gt; matriz [j + 1]: (matriz [j], matriz [j + 1]) = (matriz [j + 1], matriz [j]) 

Nuestro algoritmo comienza con un bucle for. Este bucle itera a través de cada elemento de nuestra matriz. Luego, usamos otro bucle for para comparar todos los elementos de nuestra matriz entre sí.

En nuestro código, hemos definido una declaración Python & ldquo; if & rdquo; que verifica si un elemento dado es más grande que el siguiente elemento en la lista. Esta declaración & ldquo; if & rdquo; realizará comparaciones como:

  • ¿Es el primer elemento en t ¿La lista es mayor que el segundo?
  • ¿El segundo elemento de la lista es mayor que el tercero?

Nuestro código aún no está terminado. Si intenta ejecutar el programa Python anterior, no sucederá nada. Tenemos que llamar a nuestra función y darle algunos datos:

 números = [7, 19, 4 , 12] sortList (números) print ("Lista en orden:", números) 

Nuestro código devuelve:

 Lista en orden: [4, 7, 12, 19] 

¡Lo logramos! Nuestra matriz de Python está ordenada en orden ascendente. Puede utilizar una clasificación de burbujas para ordenar una lista en orden descendente. Para hacerlo, cambie el signo mayor que por un signo menor que en Python & ldquo; if & rdquo; declaración:

 if array [j] & lt; array [j + 1]: 

Cuando ejecutamos nuestro programa con esta línea de código revisada, se devuelve lo siguiente:

 Lista en orden: [19, 12, 7, 4] 



Optimización de la clasificación de burbujas

Anteriormente hablamos sobre cómo se hacen todas las comparaciones posibles incluso si nuestra lista está ordenada. Esto hace que nuestra clasificación de burbujas sea bastante ineficiente: continúa incluso después de que se ordena la lista. 

"Career Karma entró en mi vida cuando más lo necesitaba y rápidamente me ayudó a combinar con un bootcamp. ¡Dos meses después de graduarme, encontré el trabajo de mis sueños que se alineaba con mis valores y metas en la vida!"

Venus, ingeniero de software de Rockbot

Si bien no hace una gran diferencia en este ejemplo, a escala esto podría afectar el tiempo de ejecución de un programa. Ahí es donde entra en juego la clasificación de burbujas optimizada.

Podemos optimizar nuestra clasificación de burbujas escribiendo una nueva variable. Llamémoslo intercambio . Esta variable hará un seguimiento de si se han realizado cambios en un Python for loop . Si esta variable se establece en falso, significa que nuestra lista está ordenada. No es necesario que sucedan más iteraciones. 

Revisemos nuestra función sortList de antes:

 def sortList (matriz): para elemento en rango (len (matriz)): swap = True para j en rango (0, (len (matriz) - elemento - 1)): si matriz [j] & gt; matriz [j + 1]: (matriz [j], matriz [j + 1]) = (matriz [j + 1], matriz [j]) swap = False if swap == True: break 

Hemos definido una variable llamada swap que tiene el valor predeterminado: True. Está contenida en nuestro primer bucle for porque realiza un seguimiento de si un swap ha ocurrido en cada paso a través de la lista. Si nuestra matriz hace una comparación, el valor de swap se establece en False.

Si no se realizó ningún intercambio en el último intercambio, entonces la matriz ya está ordenada. Nuestra lista verificará si swap es igual a True. Si es s, nuestro programa dejará de ejecutarse. 

Ejecutemos nuestro código nuevamente:

 Enumere en orden: [4, 7, 12, 19] 

Nuestros datos se han ordenado de la misma manera, pero nuestro algoritmo ahora es más rápido y más eficiente. Nuestro algoritmo ahora se detiene tan pronto como se hayan ordenado todos los elementos de la lista.




Análisis de complejidad

La complejidad de tiempo promedio de la clasificación de burbujas es O (n ^ 2). Esto sucede cuando los elementos de una matriz no están ordenados.

En el peor de los casos, una clasificación de burbujas se realiza en O (n ^ 2). Esto sucede cuando una matriz ya está en orden ascendente o descendente y debe ordenarse de manera opuesta. En el mejor de los casos, este algoritmo funcionará en O (n). Esto sucede si una matriz ya está ordenada.

Para obtener más información sobre la complejidad del algoritmo, consulte nuestra guía de Karma profesional guía de notación Big O .




Conclusión

Las clasificaciones de burbujas proporcionan una forma sencilla de ordenar una lista de datos. Se pueden utilizar para clasificar datos en orden ascendente o descendente. 

Este algoritmo se usa más comúnmente cuando necesita ordenar una lista pequeña. Los tipos de burbujas son una buena introducción a los algoritmos de clasificación. Puede usarlos para familiarizarse con los algoritmos antes de aprender sobre métodos de clasificación más avanzados, como la ordenación por inserción.

Para obtener orientación experta sobre los recursos y cursos de Python, consulte nuestro Guía de cómo aprender Python .





Python tipo burbuja: StackOverflow Questions

Tutorials