Entendiendo la Notación Big O y los Algoritmos de Ordenamiento Básicos

¿Cómo podemos comparar dos algoritmos de manera formal? En el post anterior , vimos que contar los segundos es una mala idea porque depende del hardware. Aprendimos que contar los pasos es el camino correcto.

Hoy aprenderemos a usar la Notación Big O, el estándar que usamos en la industria para catalogar la eficiencia del software, y la aplicaremos analizando tres algoritmos de ordenamiento clásicos: Bubble Sort, Selection Sort e Insertion Sort.

¿Qué es la Notación Big O?

La Notación Big O es una herramienta matemática que describe la eficiencia de un algoritmo en función de cómo crece su número de pasos a medida que el tamaño de los datos de entrada (denotado como N) aumenta.

No nos dice la cantidad exacta de milisegundos que tardará un programa, sino la relación de crecimiento entre el volumen de datos y el esfuerzo del procesador.

Los tres perfiles más comunes que hemos visto hasta ahora son:

1. O(1) - Tiempo Constante: El algoritmo siempre requiere la misma cantidad de pasos, sin importar si N es 10 o 10 millones (por ejemplo, leer un índice en un Array).
2. O(N) - Tiempo Lineal: El número de pasos crece en proporción directa a los datos (por ejemplo, buscar un elemento mediante Búsqueda Lineal).
3. O(log N) - Tiempo Logarítmico: El algoritmo es sumamente eficiente. Cada vez que duplicamos los datos, solo se agrega un paso más al total (por ejemplo, la Búsqueda Binaria).

Veamos gráficamente cómo se comparan estas curvas de crecimiento:

flowchart TD
    subgraph Eficiencia de Algoritmos
        direction TB
        C1["Excelente: O(1)"]
        C2["Muy Bueno: O(log N)"]
        C3["Aceptable: O(N)"]
        C4["Ineficiente: O(N²)"]
    end

Curvas de crecimiento de Big O

1. Ordenamiento Burbuja (Bubble Sort)

Bubble Sort es uno de los algoritmos de ordenamiento más simples e intuitivos. Se llama “Burbuja” porque los valores más altos van “flotando” gradualmente hacia el final del arreglo, como burbujas en el agua.

El proceso paso a paso:

1. Apuntas a los dos primeros elementos consecutivos del arreglo.
2. Si el de la izquierda es mayor que el de la derecha, los intercambias (swap).
3. Mueves los punteros una celda a la derecha y repites la comparación.
4. Repites el proceso hasta llegar al final del arreglo. Al terminar esta primera pasada, el número más alto está garantizado a estar en la última celda.
5. Regresas al inicio y realizas otra pasada completa.
6. El proceso termina cuando completas una pasada entera sin realizar ningún intercambio, lo que significa que todo está perfectamente ordenado.

flowchart TD
    Start["[4, 2, 7, 1]"] --> Step1["Comparar 4 y 2 -> ¡Intercambiar!"]
    Step1 --> Step2["[2, 4, 7, 1]"]
    Step2 --> Step3["Comparar 4 y 7 -> No intercambiar"]
    Step3 --> Step4["[2, 4, 7, 1]"]
    Step4 --> Step5["Comparar 7 y 1 -> ¡Intercambiar!"]
    Step5 --> EndPass["[2, 4, 1, 7] -> Primera pasada completada (7 está ordenado)"]

Implementación en Python:

def bubble_sort(arr: list[int]) -> list[int]:
    unsorted_until_index: int = len(arr) - 1
    is_sorted: bool = False

    while not is_sorted:
        is_sorted = True
        for i in range(unsorted_until_index):
            if arr[i] > arr[i+1]:
                # Intercambio rápido en Python:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                is_sorted = False
        unsorted_until_index -= 1

    return arr

Eficiencia de Bubble Sort

Para ordenar un arreglo de tamaño N, en el peor de los casos realizamos aproximadamente N² comparaciones e intercambios.

• Complejidad: O(N²) o Tiempo Cuadrático.
• Veredicto: Altamente ineficiente para grandes conjuntos de datos. A medida que N se duplica, el número de pasos se multiplica por cuatro.

2. Ordenamiento por Selección (Selection Sort)

Selection Sort toma un camino diferente: en lugar de ir comparando parejas consecutivas, realiza una pasada completa para “seleccionar” el elemento más pequeño del arreglo y colocarlo en su posición final.

El proceso paso a paso:

1. Comienzas en el índice 0. Recorres todo el arreglo buscando el valor más pequeño.
2. Al terminar la pasada, intercambias el valor más pequeño con el elemento en el índice 0.
3. Te mueves al índice 1 y repites el proceso buscando el menor valor del resto del arreglo.
4. Repites esto aumentando el índice de inicio en 1 cada vez, hasta llegar al final.

flowchart TD
    Start["[4, 2, 7, 1]"] --> Step1["Buscar el menor desde índice 0 -> Es 1"]
    Step1 --> Swap1["Intercambiar 1 (menor) con 4 (índice 0)"]
    Swap1 --> Step2["[1, 2, 7, 4]"]
    Step2 --> Step3["Buscar el menor desde índice 1 -> Es 2"]
    Step3 --> Swap2["2 ya está en su lugar -> No hay cambios"]
    Swap2 --> Step4["[1, 2, 7, 4]"]
    Step4 --> Step5["Buscar el menor desde índice 2 -> Es 4"]
    Step5 --> Swap3["Intercambiar 4 con 7 (índice 2)"]
    Swap3 --> End["[1, 2, 4, 7] -> ¡Completamente Ordenado! 🎉"]

Implementación en Python:

def selection_sort(arr: list[int]) -> list[int]:
    for i in range(len(arr) - 1):
        lowest_number_index: int = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[lowest_number_index]:
                lowest_number_index = j
        
        if lowest_number_index != i:
            arr[i], arr[lowest_number_index] = arr[lowest_number_index], arr[i]
            
    return arr

Eficiencia de Selection Sort

Si contamos los pasos de Selection Sort, en promedio realiza unas N²/2 comparaciones. Sin embargo, dado que Big O elimina las constantes (las fracciones y multiplicaciones por números fijos), su complejidad teórica también queda como O(N²).

3. Optimizando para Escenarios Optimistas (Insertion Sort)

Hasta ahora hemos analizado el rendimiento basándonos en el peor caso posible. Pero en el desarrollo real, muchas veces nos encontramos con arreglos que ya están parcialmente ordenados. Aquí es donde brilla Insertion Sort.

Insertion Sort funciona de manera similar a como ordenarías un mazo de cartas en tu mano.

El proceso paso a paso:

1. Comienzas en el índice 1 (la segunda celda). Remueves temporalmente el valor y lo guardas en una variable temporal (temp), dejando un “hueco”.
2. Comparas cada elemento a la izquierda del hueco con el valor en temp.
3. Si el elemento de la izquierda es mayor que temp, lo desplazas una posición hacia la derecha (el hueco se mueve hacia la izquierda).
4. Repites el paso 3 hasta encontrar un elemento menor o igual a temp, o llegar al inicio del arreglo.
5. Colocas el valor de temp en el hueco actual.
6. Repites el ciclo avanzando al siguiente índice.

Implementación en Python:

def insertion_sort(arr: list[int]) -> list[int]:
    for index in range(1, len(arr)):
        temp_value: int = arr[index]
        position: int = index - 1
        
        while position >= 0:
            if arr[position] > temp_value:
                arr[position + 1] = arr[position]
                position -= 1
            else:
                break
                
        arr[position + 1] = temp_value
        
    return arr

La gran revelación: El impacto de los escenarios

Analicemos la eficiencia de los tres algoritmos comparando sus mejores, peores y promedio casos:

¿Por qué Insertion Sort es tan especial?

Si le pasamos un arreglo que ya está ordenado a Insertion Sort, el bucle while interno se rompe inmediatamente en el primer paso (break). No hace ningún desplazamiento de datos. Por lo tanto, se ejecuta en un espectacular tiempo lineal O(N).

Si tus datos están mayoritariamente ordenados, Insertion Sort es por mucho la mejor opción entre los ordenamientos básicos.