Bubble Algoritmo de clasificación con Python usando el ejemplo de lista

¿Qué es Bubbl¿Clasificar?

Bubble Ordenar es un algoritmo de clasificación que se utiliza para ordenar elementos de una lista en orden ascendente comparando dos valores adyacentes. Si el primer valor es mayor que el segundo valor, el primer valor ocupa la posición del segundo valor, mientras que el segundo valor ocupa 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 hayan comparado e intercambiado si es necesario. Cada iteración suele denominarse pasada. El número de pasadas en una clasificación de burbujas es igual al número de elementos en una lista menos uno.

En este Bubble Ordenar en Python tutoriales aprenderás:

Implementando el Bubble Algoritmo de clasificación

Dividiremos 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 organizarlos 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) que se realizarán. 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, entonces intercambie las posiciones

Paso 4) Repita los pasos del paso 3 hasta llegar al paso exterior (n – 1). Obtenga el siguiente elemento de la lista y luego repita el proceso realizado en el paso 3 hasta que todos los valores se hayan colocado en el orden ascendente correcto.

Paso 5) Devuelve el resultado cuando se hayan realizado todos los pases. Devuelve los resultados de la lista ordenada.

Paso 6) Optimizar 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.

Optimizado Bubble Algoritmo de clasificación

De forma predeterminada, el algoritmo para la ordenación de burbuja 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 segundo elemento ya están ordenados, no es necesario repetir el resto de los valores. La iteración finaliza y se inicia la siguiente hasta que se completa el proceso como se muestra a continuación. Bubble Ejemplo de ordenación.

La optimización se realiza mediante los siguientes pasos

Paso 1) Cree una variable de bandera que monitoree 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, termine el bucle interior y continúe con el bucle exterior.

Una clasificación de burbujas optimizada es más eficiente ya que solo ejecuta los pasos necesarios y omite aquellos que no son necesarios.

Representación visual

Dada una lista de cinco elementos, las siguientes imágenes ilustran cómo la ordenación de burbuja itera a través de los valores al ordenarlos.

La siguiente imagen muestra la lista desordenada

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 ocupa la posición que ocupaba 6 mientras que 6 ocupa la posición que ocupaba 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, entonces intercambiamos las posiciones de 21 y 9

La nueva lista ahora es como la anterior.

Paso 3)

Se comparan los valores 21 y 33 para encontrar el mayor.

El valor 33 es mayor que 21, por lo que no se realiza ningún intercambio.

Paso 4)

Se comparan los valores 33 y 3 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

Python Ejemplos

El siguiente código muestra cómo implementar el Bubble Ordenar algoritmo en Python.

def bubbleSort( theSeq ):
    n = len( theSeq )

    for i in range( n - 1 ) :
        flag = 0

        for j in range(n - 1) :
            
            if theSeq[j] > theSeq[j + 1] : 
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21,6,9,33,3] 

result = bubbleSort(el)

print (result)

Ejecutando el programa de ordenamiento de burbuja anterior en Python produce los siguientes resultados

[6, 9, 21, 3, 33]

Explicación del código

La explicación para el Python BubblEl código del programa de clasificación es el 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 genera 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 genera nada.
Define una variable de bandera que se utilizará para determinar si se ha producido un intercambio o no. Esto es con fines de optimización. El código no genera nada.
Inicia el bucle interno que compara todos los valores de la lista desde el primero hasta el último. El código no genera ningún resultado.
Utiliza la declaració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 theSeq[j] a una variable temporal tmp si la condición se evalúa como verdadera. El código no genera nada.
El valor de theSeq[j + 1] se asigna a la posición de theSeq[j]. El código no genera nada.
El valor de la variable tmp se asigna a la posición theSeq[j + 1]. El código no genera nada.
A la variable de bandera se le asigna el valor 1 para indicar que se ha realizado un intercambio. El código no genera nada.
Utiliza una declaración if para verificar si el valor de la bandera variable es 0. El código no genera nada
Si el valor es 0, entonces llamamos a la declaración break que sale del bucle interno.
Devuelve el valor de theSeq 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 de la variable resultado.

Bubblventajas de clasificación electrónica

Las siguientes son algunas de las ventajas del algoritmo de ordenamiento de burbuja

es fácil de entender
Funciona muy bien cuando la lista ya está o casi ordenada.
No requiere mucha memoria.
Es fácil escribir el código del algoritmo.
Los requisitos de espacio son mínimos en comparación con otros algoritmos de clasificación.

Bubble ordenar Desventajas

Las siguientes son algunas de las desventajas del algoritmo de ordenamiento de burbuja

No funciona bien al ordenar listas grandes. Requiere demasiado tiempo y recursos.
Se utiliza principalmente con fines académicos y no para aplicaciones del mundo real.
El número de pasos necesarios para ordenar la lista es del orden n²

Análisis de complejidad de Bubble Ordenar

Hay tres tipos de complejidad que son:

1) Complejidad de clasificación

La complejidad de ordenación se utiliza para expresar la cantidad de tiempo de ejecución y espacio que se necesita para ordenar la lista. La ordenación de burbuja realiza (n – 1) iteraciones para ordenar la lista, donde n es la cantidad total de elementos de la lista.

2) Complejidad temporal

La complejidad temporal de la ordenación de burbuja es O(n²)

Las complejidades temporales se pueden clasificar de la siguiente manera:

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²)
Mejores casos – esto ocurre cuando la lista proporcionada ya está ordenada. El algoritmo realiza la cantidad mínima de ejecuciones, que se expresa como [Big-Omega] Ω(n)
Caso medio – esto ocurre cuando la lista está en orden aleatorio. La complejidad promedio se representa como [Big-theta] ⊝(n²)

3) Complejidad espacial

La complejidad espacial mide la cantidad de espacio adicional que se necesita para ordenar la lista. La ordenación de burbuja solo requiere un (1) espacio adicional para la variable temporal utilizada para intercambiar valores. Por lo 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 ordenamiento de burbuja es relativamente sencillo. Python. Todo lo que necesitas usar son bucles for y sentencias 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.
La ordenación por burbujeo tiene una complejidad temporal de O (n²) y una complejidad espacial de O (1)
El algoritmo de clasificación de burbujas 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 han sido ordenados.