¿Qué es una clasificación de burbujas?
Bubble Sort es un algoritmo de clasificación que se utiliza para clasificar los elementos de la lista en orden ascendente comparando dos valores adyacentes. Si el primer valor es mayor que el segundo valor, el primer valor toma la posición del segundo valor, mientras que el segundo valor toma la posición del primer valor. Si el primer valor es menor que el segundo valor, no se realiza ningún intercambio.
Este proceso se repite hasta que todos los valores de una lista se han comparado y se han intercambiado si es necesario. A cada iteración se le suele llamar pase. El número de pasadas en una clasificación de burbujas es igual al número de elementos de una lista menos uno.
En este tutorial de clasificación de burbujas en Python, aprenderá:
- ¿Qué es una clasificación de burbujas?
- Implementación del algoritmo de clasificación de burbujas
- Algoritmo de clasificación de burbujas optimizado
- Representación visual
- Ejemplos de Python
- Explicación del código
- Ventajas de la clasificación de burbujas
- Desventajas de la clasificación de burbujas
- Análisis de complejidad de la clasificación de burbujas
Implementación del algoritmo de clasificación de burbujas
Desglosaremos la implementación en tres (3) pasos, a saber, el problema, la solución y el algoritmo que podemos usar para escribir código para cualquier idioma.
El problema
Se proporciona una lista de elementos en orden aleatorio y nos gustaría organizar los elementos de manera ordenada
Considere la siguiente lista:
[21,6,9,33,3]
La solución
Repita la lista comparando dos elementos adyacentes e intercambiándolos si el primer valor es mayor que el segundo valor.
El resultado debería ser el siguiente:
[3,6,9,21,33]
Algoritmo
El algoritmo de clasificación de burbujas funciona de la siguiente manera
Paso 1) Obtenga el número total de elementos. Obtenga el número total de elementos en la lista dada
Paso 2) Determine el número de pasadas exteriores (n - 1) a realizar. Su longitud es lista menos uno
Paso 3) Realice pases internos (n - 1) veces para el pase externo 1. Obtenga el valor del primer elemento y compárelo con el segundo valor. Si el segundo valor es menor que el primer valor, intercambie las posiciones
Paso 4) Repita las pasadas del paso 3 hasta llegar a la pasada exterior (n - 1). Obtenga el siguiente elemento de la lista y luego repita el proceso que se realizó en el paso 3 hasta que todos los valores se hayan colocado en su orden ascendente correcto.
Paso 5) Devuelva el resultado cuando se hayan realizado todos los pases. Devuelve los resultados de la lista ordenada
Paso 6) Optimizar el algoritmo
Evite pases internos innecesarios si la lista o los valores adyacentes ya están ordenados. Por ejemplo, si la lista proporcionada ya contiene elementos que se han ordenado en orden ascendente, entonces podemos romper el ciclo antes.
Algoritmo de clasificación de burbujas optimizado
De forma predeterminada, el algoritmo para ordenar burbujas en Python compara todos los elementos de la lista independientemente de si la lista ya está ordenada o no. Si la lista dada ya está ordenada, comparar todos los valores es una pérdida de tiempo y recursos.
Optimizar la clasificación de burbujas nos ayuda a evitar iteraciones innecesarias y ahorrar tiempo y recursos.
Por ejemplo, si el primer y el segundo elemento ya están ordenados, no es necesario recorrer en iteración el resto de los valores. La iteración finaliza y la siguiente se inicia hasta que se completa el proceso, como se muestra en el siguiente ejemplo de clasificación de burbujas.
La optimización se realiza mediante los siguientes pasos
Paso 1) Cree una variable de marca que supervise si se ha producido algún intercambio en el bucle interno
Paso 2) Si los valores han intercambiado posiciones, continúe con la siguiente iteración
Paso 3) Si los beneficios no han intercambiado posiciones, finalice el bucle interno y continúe con el bucle externo.
Una clasificación de burbujas optimizada es más eficiente ya que solo ejecuta los pasos necesarios y omite los que no son necesarios.
Representación visual
Dada una lista de cinco elementos, las siguientes imágenes ilustran cómo la clasificación de burbujas itera a través de los valores al ordenarlos
La siguiente imagen muestra la lista sin clasificar
Primera iteración
Paso 1)
Se comparan los valores 21 y 6 para comprobar cuál es mayor que el otro.
21 es mayor que 6, por lo que 21 toma la posición ocupada por 6 mientras que 6 toma la posición ocupada por 21
Nuestra lista modificada ahora se parece a la de arriba.
Paso 2)
Se comparan los valores 21 y 9.
21 es mayor que 9, por lo que intercambiamos las posiciones de 21 y 9
La nueva lista es ahora como arriba
Paso 3)
Los valores 21 y 33 se comparan para encontrar el mayor.
El valor 33 es mayor que 21, por lo que no se realiza ningún intercambio.
Paso 4)
Los valores 33 y 3 se comparan para encontrar el mayor.
El valor 33 es mayor que 3, por lo que intercambiamos sus posiciones.
La lista ordenada al final de la primera iteración es como la de arriba
Segunda iteración
La nueva lista después de la segunda iteración es la siguiente
Tercera iteración
La nueva lista después de la tercera iteración es la siguiente
Cuarta iteración
La nueva lista después de la cuarta iteración es la siguiente
Ejemplos de Python
El siguiente código muestra cómo implementar el algoritmo Bubble Sort en Python.
def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)
La ejecución del programa de clasificación de burbujas anterior en Python produce los siguientes resultados
[6, 9, 21, 3, 33]
Explicación del código
La explicación del código del programa Python Bubble Sort es la siguiente
AQUÍ,
- Define una función bubbleSort que acepta un parámetro theSeq. El código no genera nada.
- Obtiene la longitud de la matriz y asigna el valor a una variable n. El código no produce nada.
- Inicia un bucle for que ejecuta el algoritmo de clasificación de burbujas (n - 1) veces. Este es el bucle exterior. El código no produce nada.
- Define una variable de marca que se utilizará para determinar si se ha producido un intercambio o no. Esto es con fines de optimización. El código no produce nada.
- Inicia el ciclo interno que compara todos los valores de la lista desde el primero hasta el último. El código no genera nada.
- Utiliza la instrucción if para comprobar si el valor del lado izquierdo es mayor que el del lado derecho inmediato. El código no genera nada.
- Asigna el valor de Seq [j] a una variable temporal tmp si la condición se evalúa como verdadera. El código no produce nada.
- El valor de laSeq [j + 1] se asigna a la posición de laSeq [j]. El código no produce nada.
- El valor de la variable tmp se asigna a la posición Seq [j + 1]. El código no produce nada.
- A la variable de bandera se le asigna el valor 1 para indicar que se ha realizado un intercambio. El código no produce nada.
- Utiliza una instrucción if para verificar si el valor de la bandera de la variable es 0. El código no genera nada
- Si el valor es 0, llamamos a la instrucción break que sale del bucle interno.
- Devuelve el valor de la Seq después de haber sido ordenado. El código genera la lista ordenada.
- Define una variable el que contiene una lista de números aleatorios. El código no genera nada.
- Asigna el valor de la función bubbleSort a un resultado variable.
- Imprime el valor del resultado de la variable.
Ventajas de la clasificación de burbujas
Las siguientes son algunas de las ventajas del algoritmo de clasificación de burbujas
- Es facil de entender
- Funciona muy bien cuando la lista ya está o casi ordenada.
- No requiere mucha memoria.
- Es fácil escribir el código para el algoritmo.
- Los requisitos de espacio son mínimos en comparación con otros algoritmos de clasificación.
Desventajas de la clasificación de burbujas
Las siguientes son algunas de las desventajas del algoritmo de clasificación de burbujas
- No funciona bien al ordenar listas grandes. Requiere demasiado tiempo y recursos.
- Se usa principalmente para fines académicos y no para aplicaciones del mundo real.
- El número de pasos necesarios para ordenar la lista es del orden n 2
Análisis de complejidad de la clasificación de burbujas
Hay tres tipos de complejidad que son:
1) Ordenar complejidad
La complejidad de clasificación se utiliza para expresar la cantidad de tiempos de ejecución y el espacio que se necesita para ordenar la lista. La clasificación de burbujas realiza (n - 1) iteraciones para ordenar la lista, donde n es el número total de elementos de la lista.
2) Complejidad del tiempo
La complejidad temporal del tipo de burbuja es O (n 2 )
Las complejidades del tiempo se pueden clasificar como:
- En el peor de los casos : aquí es donde la lista proporcionada está en orden descendente. El algoritmo realiza el número máximo de ejecuciones que se expresa como [Big-O] O (n 2 )
- Mejor caso : esto ocurre cuando la lista proporcionada ya está ordenada. El algoritmo realiza el número mínimo de ejecuciones que se expresa como [Big-Omega] Ω (n)
- Caso promedio : esto ocurre cuando la lista está en orden aleatorio. La complejidad promedio se representa como [Big-theta] ⊝ (n 2 )
3) Complejidad espacial
La complejidad del espacio mide la cantidad de espacio adicional que se necesita para ordenar la lista. La clasificación de burbujas solo requiere un (1) espacio adicional para la variable temporal utilizada para intercambiar valores. Por tanto, tiene una complejidad espacial de O (1).
Resumen
- El algoritmo de clasificación de burbujas funciona comparando dos valores adyacentes e intercambiándolos si el valor de la izquierda es menor que el valor de la derecha.
- Implementar un algoritmo de clasificación de burbujas es relativamente sencillo con Python. Todo lo que necesita usar son bucles for y declaraciones if.
- El problema que resuelve el algoritmo de clasificación de burbujas es tomar una lista aleatoria de elementos y convertirla en una lista ordenada.
- El algoritmo de clasificación de burbujas en la estructura de datos funciona mejor cuando la lista ya está ordenada, ya que realiza un número mínimo de iteraciones.
- El algoritmo de clasificación de burbujas no funciona bien cuando la lista está en orden inverso.
- El tipo burbujeador tiene una complejidad temporal de O (n 2 ) y una complejidad espacial de O (1)
- El algoritmo de clasificación de burbujeo es más adecuado para fines académicos y no para aplicaciones del mundo real.
- La clasificación de burbujas optimizada hace que el algoritmo sea más eficiente al omitir iteraciones innecesarias al verificar valores que ya se han ordenado.