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

⚡ Resumen inteligente

Bubble Sort organiza los elementos de la lista en orden ascendente comparando repetidamente valores adyacentes e intercambiándolos.ping cuando el elemento de la izquierda es mayor. Este sencillo método de ordenación por comparación es adecuado para conjuntos de datos pequeños o casi ordenados y enseña eficazmente la lógica básica de ordenación.

🔁 Mecanismo central: BubblEl algoritmo e sort compara cada par de elementos adyacentes y los intercambia, desplazando el valor no ordenado más grande a su posición final después de cada pasada.
⚙️ Variante optimizada: Una variable indicadora detecta cuándo una pasada no realiza ningún intercambio, interrumpiendo el bucle prematuramente para que una lista ya ordenada finalice en un solo escaneo.
🐍 Python Implementación: Dos bucles anidados, junto con una variable temporal, ordenan la lista, y el tutorial muestra cómo relaciona cada línea con su comportamiento exacto.
📊 Perfil de complejidad: La complejidad temporal es O(n²) en los casos peor y promedio, Ω(n) en el mejor de los casos, con un requisito de espacio constante O(1).
🎯 Mejora el ajuste: BubblEl algoritmo e sort es excelente para la enseñanza y para listas casi ordenadas, pero su rendimiento es deficiente en conjuntos de datos grandes en comparación con algoritmos avanzados.

Descubre más

¿Qué es Bubbl¿Clasificar?

Bubble Ordenar es un algoritmo de ordenación que se utiliza para ordenar los elementos de una lista en orden ascendente comparando dos valores adyacentes. Si el primer valor es mayor que el segundo, el primero ocupa la posición del segundo, y el segundo la del primero. Si el primero es menor que el segundo, no hay intercambio.ping está hecho.

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 esta Bubble Ordenar en Python tutoriales Aprenderás el problema que resuelve, su forma optimizada, un recorrido visual paso a paso y un funcionamiento. Python programa y sus características de rendimiento.

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 lenguaje.

El problema

Se proporciona una lista de elementos en orden aleatorio, y nos gustaría ordenarlos de manera ordenada.

Considere la siguiente lista:

[21, 6, 9, 33, 3]

La solución

Itera a través de la lista comparando dos elementos adyacentes e intercámbialos.ping ellos 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 ordenación de burbuja funciona de la siguiente manera:

Paso 1) Obtén el número total de elementos. Obtén el número total de elementos en la lista dada.

Paso 2) Determina el número de pases exteriores (n – 1) que se deben realizar. Su longitud es lista menos uno.

Paso 3) Realiza pasadas internas (n – 1) veces para la pasada externa 1. Obtén el valor del primer elemento y compáralo con el segundo valor. Si el segundo valor es menor que el primero, intercambia las posiciones.

Paso 4) Repita el paso 3 hasta llegar al paso exterior (n – 1). Obtenga el siguiente elemento de la lista y repita el proceso realizado en el paso 3 hasta que todos los valores estén ordenados correctamente de forma ascendente.

Paso 5) Devuelve el resultado cuando se hayan realizado todas las pasadas. 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 siguiendo los siguientes pasos:

Paso 1) Crea una variable de bandera que supervise si hay algún intercambio.ping ha ocurrido en el bucle interno.

Paso 2) Si los valores han intercambiado posiciones, continúe con la siguiente iteración.

Paso 3) Si los valores 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 aquellos que no son necesarios.

Representación visual

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

La siguiente imagen muestra la lista sin ordenar:

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, así que intercambiamos las posiciones de 21 y 9.

La nueva lista es la que aparece arriba.

Paso 3)

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

El valor 33 es mayor que 21, por lo tanto, no hay intercambio.ping se lleva a cabo.

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 que se muestra arriba.

Segunda iteración

La nueva lista tras la segunda iteración es la siguiente:

Tercera iteración

La nueva lista tras la tercera iteración es la siguiente:

Cuarta iteración

La nueva lista tras 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:

[3, 6, 9, 21, 33]

Code Explicación

La explicación para el Python BubblEl código del programa de ordenació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 del array y asigna el valor a una variable n. El código no produce ninguna salida.
Inicia un bucle for que ejecuta el algoritmo de ordenación de burbuja (n – 1) veces. Este es el bucle exterior. El código no genera ninguna salida.
Define una variable de indicador que se utilizará para determinar si se ha producido un intercambio o no. Esto se hace con fines de optimización. El código no genera ninguna salida.
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 produce ninguna salida.
El valor de theSeq[j + 1] se asigna a la posición de theSeq[j]. El código no produce ninguna salida.
El valor de la variable tmp se asigna a la posición theSeq[j + 1]. El código no produce ninguna salida.
La variable de indicador se establece en 1 para indicar que se ha producido un intercambio. El código no muestra ninguna salida.
Utiliza una sentencia if para comprobar si el valor de la variable flag es 0. El código no produce ninguna salida.
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

A continuación se presentan algunas de las ventajas del algoritmo de ordenación de burbuja:

Es facil de entender.
Funciona muy bien cuando la lista ya está ordenada 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.

Bubble ordenar Desventajas

A continuación se presentan algunas de las desventajas del algoritmo de ordenación 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 en el mundo real.
El número de pasos necesarios para ordenar la lista es del orden n².

Análisis de complejidad de Bubble Ordenar

Existen tres tipos de complejidad:

1) Complejidad de clasificación

La complejidad de ordenación se utiliza para expresar la cantidad de tiempo y espacio de ejecución necesarios para ordenar la lista. El algoritmo de ordenación de burbuja realiza (n – 1) iteraciones para ordenar la lista, donde n es el número total de elementos en 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 el número mínimo 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. El algoritmo de ordenación de burbuja solo requiere un (1) espacio adicional para la variable temporal utilizada para el intercambio.ping valores. Por lo tanto, tiene una complejidad espacial de O(1).

Preguntas Frecuentes

BubblEl algoritmo e-sort rara vez se ejecuta en entornos de IA de producción, pero ayuda a enseñar la lógica de ordenación subyacente a la preparación de datos. Los sistemas de aprendizaje automático ordenan características, puntuaciones y predicciones mediante algoritmos más rápidos, pero el algoritmo de ordenación de burbuja aclara el concepto de comparación e intercambio para principiantes.

Sí. Los asistentes de IA pueden escribir ordenamiento de burbuja en Python, Java, o C++ y añaden la optimización de indicadores que detiene el proceso prematuramente en una lista ordenada. También pueden sugerir algoritmos más rápidos cuando el conjunto de datos crece considerablemente.

Se denomina ordenación de burbuja porque los valores más grandes gradualmente "suben" al final de la lista con cada pasada, de forma similar a como las burbujas de aire ascienden a la superficie del agua, mientras que los valores más pequeños se hunden hacia el principio.

Bubble sort se ejecuta en un tiempo de O(n²), que es mucho más lento que quicksort y merge sort en O(n log n). BubblEl algoritmo e-sort es adecuado para ejemplos pequeños o didácticos, mientras que quicksort y merge-sort manejan de manera eficiente grandes conjuntos de datos del mundo real.