Ventajas y desventajas de la ordenación por burbuja

Programadores que pasan de desarrollo web y PC a codificación para dispositivos móviles o sistemas embebidos descubren que dedican más tiempo a seleccionar y programar sus propias estructuras de datos y algoritmos. Con menos memoria y almacenamiento limitado, no hay espacio para librerías o frameworks preconstruidos. Para quienes necesitan escribir sus propias rutinas de ordenación, aquí hay consideraciones sobre la ordenación por burbuja.

Contexto

La ordenación por burbuja es un algoritmo simple que ordena una lista de elementos en memoria. Dado un array, el código compara repetidamente cada par de elementos adyacentes e intercambia si no están en orden. El proceso se repite hasta que no hay más intercambios. Si se pudiera ver el array durante la ordenación, los valores bajos "burbujearían" hacia arriba mientras los grandes se hundirían. Aquí el código en Visual Basic 2010:

While swap = True
    swap = False
    For i = 0 To tbl.length - 2
        If tbl(i) > tbl(i + 1) Then
            tmp = tbl(i)
            tbl(i) = tbl(i + 1)
            tbl(i + 1) = tmp
            swap = True
        End If
    Next
End While

Cuándo elegir ordenación por burbuja

Este algoritmo tiene varias ventajas. Es simple de escribir, fácil de entender y solo necesita unas líneas de código. Los datos se ordenan in situ, con poca sobrecarga de memoria, y una vez ordenados están en memoria listos para procesar. La gran desventaja es el tiempo que tarda. El tiempo medio aumenta casi exponencialmente al crecer el número de elementos. Diez veces más elementos tarda casi cien veces más en ordenarse.

Otras ordenaciones basadas en arrays

Los algoritmos varían en complejidad, velocidad y sobrecarga. La burbuja es la menos compleja pero también de las más lentas. Otras como inserción e intercambio son algo más rápidas pero requieren más código. La ventaja principal de las basadas en arrays es que usan menos código y memoria de trabajo. Considera estas para arrays simples con menos de unos cientos de elementos.

Algoritmos de ordenación complejos

Conjuntos de datos grandes requieren código más complejo y más memoria. Quick sort y heap sort dividen y copian los datos para optimizar comparaciones. Quick sort divide la lista continuamente y la reensambla ordenada. Heap sort copia los datos en una estructura de árbol y recorre el árbol para copiarlos de vuelta en orden. Ambos son rápidos y eficientes pero necesitan más código y mucho más almacenamiento de trabajo. Elige estos para grandes conjuntos de datos.