WhatsApp

  
¿Qué es el algoritmo Bubble Sort (Ordenamiento Burbuja) ?
Bubble Sort (Ordenamiento Burbuja)
¿Qué es el Algoritmo de Bubble Sort ? 

El algoritmo de Bubble Short "Ordenamiento Burbuja" es un algoritmo simple de ordenamiento, recibe su nombre por la táctica que utiliza para ordenar los elementos, que poco a poco burbujean "incrementan" para tomar su adecuada posición, al igual que el aumento de burbujas en un vaso de refresco.    

                    

El algoritmo sigue la siguiente metodología:

1) Recorre repetidamente la lista, comparando cada par de elementos adyacentes y los intercambia si están en el orden incorrecto. 

2) El proceso se repite hasta que no se requieran más intercambios, lo que indica que la lista está ordenada.

Ejemplo de implementación con Python

A continuación se muestra como seria la implementación en el lenguaje python:

def bubble_sort(arr):
    n = len(arr)
    # Recorremos todos los elementos de la lista
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n-i-1):
            # Recorremos la lista de 0 a n-i-1
            # Intercambiamos si el elemento encontrado es mayor que el siguiente elemento
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

Ahora supongamos que desea ordenar los siguientes elementos: 

# Elementos a ordenar.  
arr = [64, 34, 25, 12, 22, 11, 90]

#Nuestra función.
bubble_sort(arr)
#Imprimimos nutra lista final print("Lista ordenada:", end=' ') for i in range(len(arr)): print(arr[i], " ", end=' ')

El resultado que obtenemos al final es el siguiente 

Lista ordenada: 11 12 22 25 34 64 90

 Las iteraciones que sigue el algoritmo son las siguientes:

  1. Iteración 1:

    • Comparación de elementos [64, 34, 25, 12, 22, 11, 90]
      • 64 > 34, se intercambian: [34, 64, 25, 12, 22, 11, 90]
      • 64 > 25, se intercambian: [34, 25, 64, 12, 22, 11, 90]
      • 64 > 12, se intercambian: [34, 25, 12, 64, 22, 11, 90]
      • 64 > 22, se intercambian: [34, 25, 12, 22, 64, 11, 90]
      • 64 > 11, se intercambian:  [34, 25, 12, 22, 11 64, 90]
      • 64 < 90, no se intercambian
  2. Iteración 2:

    • Comparación de elementos [34, 25, 12, 22, 11, 64, 90]
      • 34 > 25, se intercambian: [25, 34, 12, 22, 11, 64, 90]
      • 34 > 12, se intercambian: [25, 12, 34, 22, 11, 64, 90]
      • 34 > 22, se intercambian: [25, 12, 22, 34, 11, 64, 90]
      • 34 > 11, se intercambian: [25, 12, 22, 11, 34, 64, 90]
      • 34 < 64, no se intercambian
  3. Iteración 3:

    • Comparación de elementos [25, 12, 22, 11, 34, 64, 90]
      • 25 > 12, se intercambian: [12, 25, 22, 34, 11, 64, 90]
      • 25 > 22, se intercambian  [12, 22, 25, 34, 11, 64, 90]
      • 25 < 34, no se intercambian
      • 34 > 11, se intercambian: [12, 22, 25, 11, 34, 64, 90]
  4. Iteración 4:

    • Comparación de elementos [12, 22, 25, 11, 34, 64, 90]
      • 12 < 22, no se intercambian
      • 22 < 25, no se intercambian
      • 25 > 11, se intercambian: [12, 22, 11, 25, 34, 64, 90]
  5. Iteración 5:

    • Comparación de elementos [12, 22, 11, 25, 34, 64, 90]
      • 12 < 22, no se intercambian
      • 22 > 11, se intercambian: [12, 11, 22, 25, 34, 64, 90]
  6. Iteración 6:

    • Comparación de elementos [12, 11, 22, 25, 34, 64, 90]
      • 12 > 11, se intercambian: [11, 12, 22, 25, 34, 64, 90
  7. Iteración 7:

    • Comparación de elementos [11, 12, 22, 25, 34, 64, 90]
      • Todos los elementos ya están en su lugar, ninguna comparación ni intercambio necesario.
Ventajas y Desventajas del algoritmo  bubble sort.

Ventajas:

1. Implementación simple: El algoritmo de ordenamiento de burbuja es fácil de implementar y entender. Requiere una cantidad mínima de código, lo que lo hace adecuado para aplicaciones simples y educativas.

2. No requiere memoria adicional: Bubble Sort ordena la lista en su lugar, es decir, no requiere memoria adicional para almacenar elementos temporales o estructuras de datos auxiliares. Esto hace que sea eficiente en términos de uso de memoria.

3. Rendimiento aceptable para listas pequeñas: Para pequeñas listas o arreglos, el algoritmo de ordenamiento de burbuja puede tener un rendimiento aceptable y puede ser competitivo con otros algoritmos de ordenamiento.

Desventajas:

1. Ineficiente para grandes conjuntos de datos: Bubble Sort tiene un peor rendimiento en comparación con otros algoritmos de ordenamiento, especialmente para listas grandes. Su complejidad de tiempo es de O(n^2), lo que significa que su tiempo de ejecución aumenta cuadráticamente con el tamaño de la lista. Esto lo hace poco práctico para conjuntos de datos grandes.

2. No es estable: A pesar de ser simple, Bubble Sort no es estable, lo que significa que no mantiene el orden relativo de elementos con claves iguales. Si dos elementos tienen el mismo valor, pueden intercambiarse durante el proceso de ordenamiento, lo que puede cambiar su orden relativo en la lista ordenada.

3. Complejidad de tiempo: Como se mencionó anteriormente, la complejidad de tiempo de Bubble Sort es cuadrática, lo que significa que puede ser muy ineficiente en términos de tiempo de ejecución para listas grandes. Otros algoritmos de ordenamiento, como Merge Sort o Quick Sort, ofrecen una mejor complejidad de tiempo y rendimiento en general.



En resumen, las listas y las tuplas son estructuras de datos importantes en Python, cada una con sus propias características y casos de uso. La elección entre una lista y una tupla dependerá de los requisitos específicos del programa y la naturaleza de los datos que se están manipulando.
Daniel Ixbalanque 1 abril, 2024
Compartir


Iniciar sesión dejar un comentario

  
¿Qué es la recursividad ?
Recursividad