Algoritmos de ordenación: burbuja, selección y fusión

Al finalizar este tema

Podrás explicar el funcionamiento de tres algoritmos de ordenación y comparar su complejidad temporal, así como sus ventajas y desventajas.

¿Por qué estudiar la ordenación?

La ordenación es uno de los problemas más fundamentales y ampliamente estudiados en programación. Aunque es poco frecuente implementar directamente un algoritmo de ordenación en la práctica (basta con usar sorted() de Python), estudiar estos algoritmos entrena el pensamiento algorítmico: cómo descomponer problemas, aplicar iteraciones y optimizar soluciones.

Ordenación por burbuja: la más intuitiva

Compara pares de elementos adyacentes e intercambia sus posiciones si están en el orden incorrecto. Este proceso se repite hasta que toda la lista queda ordenada.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# [5, 3, 8, 1, 2] → [3, 5, 1, 2, 8] → ... → [1, 2, 3, 5, 8]

Proceso de funcionamiento (por ciclo):

[5, 3, 8, 1, 2]
 5>3 → intercambio → [3, 5, 8, 1, 2]
 5<8 → mantener → [3, 5, 8, 1, 2]
 8>1 → intercambio → [3, 5, 1, 8, 2]
 8>2 → intercambio → [3, 5, 1, 2, 8]  ← 8 al final

Se llama ordenamiento de burbuja porque los valores grandes "suben" hacia arriba como burbujas. Complejidad temporal: O(n²). Es fácil de entender, pero lento.

Ordenamiento por selección: elegir el valor mínimo y colocarlo al principio

Encuentra el valor más pequeño de todo el conjunto y lo coloca al principio. Luego, encuentra el valor más pequeño entre los restantes y lo coloca en la segunda posición. Esto se repite iterativamente.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Proceso de funcionamiento:

[5, 3, 8, 1, 2]
 mínimo=1 → [1, 3, 8, 5, 2]
 mínimo=2 → [1, 2, 8, 5, 3]
 mínimo=3 → [1, 2, 3, 5, 8]
 completado

Complejidad temporal: O(n²). Similar a la ordenación de burbuja, pero con menos intercambios, por lo que en la práctica es ligeramente más rápida.

Ordenación por mezcla — Divide y vencerás

Idea: Dividir la lista en dos, ordenar cada mitad y luego fusionarlas.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # ordenar mitad izquierda
    right = merge_sort(arr[mid:])  # ordenar mitad derecha

    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

Proceso de funcionamiento:

[5, 3, 8, 1, 2]
    ↙         ↘
[5, 3, 8]   [1, 2]
  ↙   ↘       ↓
[5] [3,8]  [1, 2]
     ↓       ↓
[5] [3,8] [1,2]
  ↘  ↙      ↓
[3,5,8]  [1,2]
    ↘     ↙
[1, 2, 3, 5, 8]

Complejidad temporal: O(n log n). Al dividirlo a la mitad en cada paso (log n pasos) × n comparaciones por paso = O(n log n). Este es el límite teórico óptimo para los algoritmos de ordenamiento basados en comparaciones.

Comparación de rendimiento

• Estable: El orden original de los elementos con valores iguales se mantiene. (Por ejemplo, el orden de los nombres de los estudiantes con la misma puntuación).
• El ordenamiento de burbuja y el de selección no requieren memoria adicional (in-place), mientras que el de mezcla necesita crear una nueva lista.

Para 10.000 elementos: ordenamiento de burbuja/selección ≈ 100 millones de operaciones, ordenamiento por mezcla ≈ 130 mil. La diferencia es de 770 veces.

¿Cómo se utiliza en la práctica?

# Python integrado — Timsort (hibrido de fusion + insercion ordenada)
numbers = [5, 3, 8, 1, 2]
sorted(numbers)           # Devuelve una nueva lista
numbers.sort()             # Ordena el original

# Especificar criterio
students = [("Kim Hun", 90), ("Lee Soo", 85), ("Park Jin", 95)]
sorted(students, key=lambda s: s[1])  # Por puntuacion
sorted(students, key=lambda s: s[1], reverse=True)  # Descendente

Python utiliza el algoritmo sorted() Timsort. Combina las ventajas de la ordenación por mezcla y la ordenación por inserción, lo que lo hace muy eficiente con datos reales. Por este motivo, no es necesario implementar la ordenación directamente.

Resumen clave

Los tres algoritmos abordan el mismo problema desde diferentes perspectivas, y esta diferencia se manifiesta en una marcada diferencia de rendimiento entre O(n²) y O(n log n). Esta es la razón por la que es importante estudiar algoritmos: aunque produzcan el mismo resultado, la forma en que se llega a él puede marcar una diferencia de más de 1000 veces. El mismo principio se aplica a todos los problemas algorítmicos, como la búsqueda, los grafos y la optimización.