Algoritmos - Búsqueda y Ordenamiento

🎯 ¿Qué es un algoritmo?

Un algoritmo es una secuencia finita de pasos bien definidos que resuelven un problema específico. Es como una receta de cocina: tenés ingredientes (datos de entrada), seguís pasos ordenados (instrucciones), y obtenés un resultado (salida).

Características de un buen algoritmo

1. Finito: Debe terminar después de un número determinado de pasos
2. Definido: Cada paso debe estar claramente especificado
3. Entrada: Puede tener cero o más entradas
4. Salida: Debe producir al menos una salida
5. Efectivo: Cada operación debe ser lo suficientemente básica para ejecutarse

Ejemplo cotidiano

Algoritmo para preparar mate:

1. Llenar el termo con agua caliente
2. Llenar 3/4 del mate con yerba
3. Tapar con la mano y sacudir
4. Inclinar el mate 45 grados
5. Agregar agua tibia en el hueco
6. Insertar la bombilla
7. Cebar con agua caliente
8. Tomar y repetir paso 7

⏱️ Complejidad de algoritmos - Big O

La complejidad mide cuánto tiempo o espacio necesita un algoritmo para ejecutarse en función del tamaño de la entrada.

Notación Big O

La notación O (Big O) describe el peor caso de un algoritmo.

Visualización de complejidades

Tiempo de ejecución para n = 1000

O(1)        ▏ 1 operación
O(log n)    ▏▏▏ 10 operaciones
O(n)        ▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏ 1,000 operaciones
O(n log n)  ▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏▏ 10,000 operaciones
O(n²)       ████████████████████████████████████████ 1,000,000 operaciones

Regla de oro: Siempre buscá el algoritmo con la menor complejidad posible.

🔍 Algoritmos de Búsqueda

1. Búsqueda Lineal (Linear Search)

Concepto: Recorre la lista elemento por elemento hasta encontrar el objetivo.

Complejidad: O(n)

Cuándo usarla:

• Lista pequeña
• Lista desordenada
• Búsqueda simple

Implementación básica

def busqueda_lineal(lista, objetivo):
    """
    Busca un elemento en una lista de forma secuencial

    Args:
        lista: Lista donde buscar
        objetivo: Elemento a buscar

    Returns:
        Índice del elemento si se encuentra, -1 si no
    """
    for i in range(len(lista)):
        if lista[i] == objetivo:
            return i
    return -1

# Ejemplo de uso
sensores = ["TEMP-001", "PRES-002", "NIV-003", "TEMP-004", "PRES-005"]
posicion = busqueda_lineal(sensores, "NIV-003")

if posicion != -1:
    print(f"Sensor encontrado en posición {posicion}")
else:
    print("Sensor no encontrado")

Versión mejorada con contador

def busqueda_lineal_detallada(lista, objetivo):
    """
    Búsqueda lineal con información detallada
    """
    comparaciones = 0

    for i in range(len(lista)):
        comparaciones += 1
        if lista[i] == objetivo:
            print(f"✅ Encontrado en posición {i}")
            print(f"📊 Comparaciones realizadas: {comparaciones}")
            return i

    print(f"❌ No encontrado")
    print(f"📊 Comparaciones realizadas: {comparaciones}")
    return -1

# Ejemplo
datos = [45, 23, 67, 12, 89, 34, 56]
busqueda_lineal_detallada(datos, 89)

2. Búsqueda Binaria (Binary Search)

Concepto: Divide la lista ordenada en dos mitades y descarta la mitad donde el elemento no puede estar.

Complejidad: O(log n)

Requisito: La lista DEBE estar ordenada

Cuándo usarla:

• Lista grande y ordenada
• Necesitás eficiencia
• Búsquedas frecuentes

Visualización del proceso

Lista: [10, 20, 30, 40, 50, 60, 70, 80, 90]
Buscar: 70

Paso 1: [10, 20, 30, 40, 50, 60, 70, 80, 90]
                      ↑ medio=50
        70 > 50 → buscar en mitad derecha

Paso 2:                   [60, 70, 80, 90]
                              ↑ medio=70
        70 == 70 → ¡Encontrado!

Implementación iterativa

def busqueda_binaria(lista, objetivo):
    """
    Búsqueda binaria iterativa

    Args:
        lista: Lista ORDENADA donde buscar
        objetivo: Elemento a buscar

    Returns:
        Índice del elemento si se encuentra, -1 si no
    """
    inicio = 0
    fin = len(lista) - 1

    while inicio <= fin:
        medio = (inicio + fin) // 2

        if lista[medio] == objetivo:
            return medio
        elif lista[medio] < objetivo:
            inicio = medio + 1  # Buscar en mitad derecha
        else:
            fin = medio - 1     # Buscar en mitad izquierda

    return -1

# Ejemplo
temperaturas_ordenadas = [15, 18, 22, 25, 28, 32, 35, 40, 45, 50]
posicion = busqueda_binaria(temperaturas_ordenadas, 32)
print(f"Temperatura encontrada en índice: {posicion}")

Implementación recursiva

def busqueda_binaria_recursiva(lista, objetivo, inicio=0, fin=None):
    """
    Búsqueda binaria recursiva
    """
    if fin is None:
        fin = len(lista) - 1

    # Caso base: no se encontró
    if inicio > fin:
        return -1

    medio = (inicio + fin) // 2

    # Caso base: se encontró
    if lista[medio] == objetivo:
        return medio

    # Caso recursivo: buscar en mitad correspondiente
    if lista[medio] < objetivo:
        return busqueda_binaria_recursiva(lista, objetivo, medio + 1, fin)
    else:
        return busqueda_binaria_recursiva(lista, objetivo, inicio, medio - 1)

Ejemplo industrial: Búsqueda de setpoint

class ControladorTemperatura:
    """
    Controlador que busca el setpoint más cercano en una tabla
    """

    def __init__(self):
        # Tabla de setpoints predefinidos (ordenada)
        self.setpoints_disponibles = [15, 20, 25, 30, 35, 40, 45, 50, 55, 60]

    def buscar_setpoint_exacto(self, temperatura):
        """Busca un setpoint exacto"""
        indice = busqueda_binaria(self.setpoints_disponibles, temperatura)

        if indice != -1:
            return f"✅ Setpoint {temperatura}°C disponible"
        else:
            return f"❌ Setpoint {temperatura}°C no disponible"

    def buscar_setpoint_cercano(self, temperatura):
        """Busca el setpoint más cercano"""
        inicio = 0
        fin = len(self.setpoints_disponibles) - 1

        while inicio <= fin:
            medio = (inicio + fin) // 2

            if self.setpoints_disponibles[medio] == temperatura:
                return self.setpoints_disponibles[medio]
            elif self.setpoints_disponibles[medio] < temperatura:
                inicio = medio + 1
            else:
                fin = medio - 1

        # No encontrado exacto, buscar el más cercano
        if inicio >= len(self.setpoints_disponibles):
            return self.setpoints_disponibles[-1]
        if fin < 0:
            return self.setpoints_disponibles[0]

        # Comparar cuál está más cerca
        if abs(self.setpoints_disponibles[inicio] - temperatura) < abs(self.setpoints_disponibles[fin] - temperatura):
            return self.setpoints_disponibles[inicio]
        else:
            return self.setpoints_disponibles[fin]

# Uso
controlador = ControladorTemperatura()
print(controlador.buscar_setpoint_exacto(30))
print(f"Setpoint más cercano a 33°C: {controlador.buscar_setpoint_cercano(33)}°C")

📊 Algoritmos de Ordenamiento

1. Ordenamiento Burbuja (Bubble Sort)

Concepto: Compara elementos adyacentes y los intercambia si están en orden incorrecto. Repite hasta que la lista esté ordenada.

Complejidad: O(n²)

Ventajas: Simple de entender e implementar

Desventajas: Muy lento para listas grandes

Visualización

Pasada 1: [5, 2, 8, 1, 9]
          [2, 5, 8, 1, 9]  (5 y 2 se intercambian)
          [2, 5, 1, 8, 9]  (8 y 1 se intercambian)

Pasada 2: [2, 1, 5, 8, 9]
          [1, 2, 5, 8, 9]  (2 y 1 se intercambian)

Pasada 3: [1, 2, 5, 8, 9]  ✅ Ordenado

Implementación

def ordenamiento_burbuja(lista):
    """
    Ordena una lista usando el algoritmo de burbuja

    Args:
        lista: Lista a ordenar (se modifica in-place)
    """
    n = len(lista)

    # Recorrer todos los elementos
    for i in range(n):
        # Flag para optimización
        hubo_intercambio = False

        # Últimos i elementos ya están ordenados
        for j in range(0, n - i - 1):
            # Comparar elementos adyacentes
            if lista[j] > lista[j + 1]:
                # Intercambiar si están en orden incorrecto
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                hubo_intercambio = True

        # Si no hubo intercambios, ya está ordenado
        if not hubo_intercambio:
            break

# Ejemplo
temperaturas = [32, 15, 28, 45, 12, 38, 22]
print(f"Original: {temperaturas}")
ordenamiento_burbuja(temperaturas)
print(f"Ordenado: {temperaturas}")

Versión con visualización

def ordenamiento_burbuja_visual(lista):
    """
    Bubble sort con visualización del proceso
    """
    n = len(lista)
    print(f"Lista original: {lista}\n")

    for i in range(n):
        print(f"--- Pasada {i + 1} ---")
        hubo_intercambio = False

        for j in range(0, n - i - 1):
            if lista[j] > lista[j + 1]:
                print(f"Intercambio: {lista[j]} ↔ {lista[j + 1]}")
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                hubo_intercambio = True

        print(f"Estado: {lista}")

        if not hubo_intercambio:
            print("✅ Ya está ordenado!")
            break
        print()

    return lista

# Ejemplo
datos = [64, 34, 25, 12, 22, 11, 90]
ordenamiento_burbuja_visual(datos)

2. Ordenamiento por Selección (Selection Sort)

Concepto: Encuentra el elemento mínimo y lo coloca al principio. Repite para el resto de la lista.

Complejidad: O(n²)

Ventaja: Hace menos intercambios que bubble sort

Implementación

def ordenamiento_seleccion(lista):
    """
    Ordena una lista usando el algoritmo de selección
    """
    n = len(lista)

    for i in range(n):
        # Encontrar el mínimo en el resto de la lista
        indice_minimo = i

        for j in range(i + 1, n):
            if lista[j] < lista[indice_minimo]:
                indice_minimo = j

        # Intercambiar el mínimo con el primer elemento
        lista[i], lista[indice_minimo] = lista[indice_minimo], lista[i]

# Ejemplo
presiones = [7.5, 3.2, 9.1, 2.8, 5.6]
print(f"Original: {presiones}")
ordenamiento_seleccion(presiones)
print(f"Ordenado: {presiones}")

3. Ordenamiento por Inserción (Insertion Sort)

Concepto: Construye la lista ordenada de a un elemento por vez, insertando cada elemento en su posición correcta.

Complejidad: O(n²) en el peor caso, O(n) si está casi ordenada

Ventaja: Eficiente para listas pequeñas o casi ordenadas

Implementación

def ordenamiento_insercion(lista):
    """
    Ordena una lista usando el algoritmo de inserción
    """
    for i in range(1, len(lista)):
        clave = lista[i]
        j = i - 1

        # Mover elementos mayores que la clave una posición adelante
        while j >= 0 and lista[j] > clave:
            lista[j + 1] = lista[j]
            j -= 1

        # Insertar la clave en su posición correcta
        lista[j + 1] = clave

# Ejemplo
niveles = [45, 23, 67, 12, 89, 34]
print(f"Original: {niveles}")
ordenamiento_insercion(niveles)
print(f"Ordenado: {niveles}")

4. Merge Sort (Ordenamiento por Mezcla)

Concepto: Divide la lista en mitades, ordena cada mitad recursivamente y luego las combina.

Complejidad: O(n log n)

Ventaja: Muy eficiente, complejidad garantizada

Desventaja: Usa memoria adicional

Implementación

def merge_sort(lista):
    """
    Ordena una lista usando merge sort (recursivo)
    """
    # Caso base: lista de 0 o 1 elemento ya está ordenada
    if len(lista) <= 1:
        return lista

    # Dividir la lista en dos mitades
    medio = len(lista) // 2
    izquierda = lista[:medio]
    derecha = lista[medio:]

    # Ordenar recursivamente cada mitad
    izquierda = merge_sort(izquierda)
    derecha = merge_sort(derecha)

    # Combinar las mitades ordenadas
    return merge(izquierda, derecha)

def merge(izquierda, derecha):
    """
    Combina dos listas ordenadas en una sola lista ordenada
    """
    resultado = []
    i = j = 0

    # Comparar elementos de ambas listas
    while i < len(izquierda) and j < len(derecha):
        if izquierda[i] <= derecha[j]:
            resultado.append(izquierda[i])
            i += 1
        else:
            resultado.append(derecha[j])
            j += 1

    # Agregar elementos restantes
    resultado.extend(izquierda[i:])
    resultado.extend(derecha[j:])

    return resultado

# Ejemplo
datos = [38, 27, 43, 3, 9, 82, 10]
print(f"Original: {datos}")
ordenado = merge_sort(datos)
print(f"Ordenado: {ordenado}")

5. Quick Sort (Ordenamiento Rápido)

Concepto: Elige un pivote, particiona la lista en elementos menores y mayores al pivote, y ordena recursivamente.

Complejidad: O(n log n) en promedio, O(n²) en el peor caso

Ventaja: Muy rápido en la práctica, no usa memoria adicional

Implementación

def quick_sort(lista):
    """
    Ordena una lista usando quick sort
    """
    if len(lista) <= 1:
        return lista

    # Elegir el pivote (último elemento)
    pivote = lista[-1]

    # Particionar en menores, iguales y mayores
    menores = [x for x in lista[:-1] if x < pivote]
    iguales = [x for x in lista if x == pivote]
    mayores = [x for x in lista[:-1] if x > pivote]

    # Ordenar recursivamente y combinar
    return quick_sort(menores) + iguales + quick_sort(mayores)

# Ejemplo
valores = [64, 34, 25, 12, 22, 11, 90, 88]
print(f"Original: {valores}")
ordenado = quick_sort(valores)
print(f"Ordenado: {ordenado}")

📊 Comparación de algoritmos de ordenamiento

Estable: Mantiene el orden relativo de elementos iguales

🏭 Ejemplo industrial completo

class SistemaMonitoreoSensores:
    """
    Sistema que gestiona lecturas de sensores con búsqueda y ordenamiento
    """

    def __init__(self):
        self.lecturas = []

    def agregar_lectura(self, sensor_id, valor, timestamp):
        """Agrega una lectura de sensor"""
        self.lecturas.append({
            'sensor_id': sensor_id,
            'valor': valor,
            'timestamp': timestamp
        })
        print(f"✅ Lectura agregada: {sensor_id} = {valor}")

    def ordenar_por_valor(self):
        """Ordena lecturas por valor usando merge sort"""
        self.lecturas = merge_sort_dict(self.lecturas, 'valor')
        print("📊 Lecturas ordenadas por valor")

    def ordenar_por_timestamp(self):
        """Ordena lecturas por timestamp"""
        self.lecturas = merge_sort_dict(self.lecturas, 'timestamp')
        print("📊 Lecturas ordenadas por tiempo")

    def buscar_lectura_binaria(self, valor_objetivo):
        """Busca una lectura por valor (requiere lista ordenada)"""
        # Primero ordenar
        self.ordenar_por_valor()

        # Búsqueda binaria adaptada
        inicio = 0
        fin = len(self.lecturas) - 1

        while inicio <= fin:
            medio = (inicio + fin) // 2
            valor_medio = self.lecturas[medio]['valor']

            if valor_medio == valor_objetivo:
                return self.lecturas[medio]
            elif valor_medio < valor_objetivo:
                inicio = medio + 1
            else:
                fin = medio - 1

        return None

    def obtener_top_n(self, n):
        """Obtiene las n lecturas más altas"""
        self.ordenar_por_valor()
        return self.lecturas[-n:]

    def mostrar_lecturas(self):
        """Muestra todas las lecturas"""
        print("\n📋 LECTURAS REGISTRADAS")
        print("=" * 60)
        for lectura in self.lecturas:
            print(f"  {lectura['sensor_id']}: {lectura['valor']} "
                  f"(Tiempo: {lectura['timestamp']})")

def merge_sort_dict(lista, clave):
    """Merge sort adaptado para diccionarios"""
    if len(lista) <= 1:
        return lista

    medio = len(lista) // 2
    izquierda = merge_sort_dict(lista[:medio], clave)
    derecha = merge_sort_dict(lista[medio:], clave)

    return merge_dict(izquierda, derecha, clave)

def merge_dict(izq, der, clave):
    """Merge para diccionarios"""
    resultado = []
    i = j = 0

    while i < len(izq) and j < len(der):
        if izq[i][clave] <= der[j][clave]:
            resultado.append(izq[i])
            i += 1
        else:
            resultado.append(der[j])
            j += 1

    resultado.extend(izq[i:])
    resultado.extend(der[j:])
    return resultado

# Uso del sistema
sistema = SistemaMonitoreoSensores()

# Agregar lecturas
sistema.agregar_lectura("TEMP-001", 85.5, "10:00:00")
sistema.agregar_lectura("TEMP-002", 72.3, "10:00:05")
sistema.agregar_lectura("PRES-001", 7.8, "10:00:10")
sistema.agregar_lectura("TEMP-003", 91.2, "10:00:15")
sistema.agregar_lectura("NIV-001", 3.4, "10:00:20")

# Mostrar lecturas
sistema.mostrar_lecturas()

# Ordenar por valor
sistema.ordenar_por_valor()
sistema.mostrar_lecturas()

# Obtener top 3
print("\n🏆 TOP 3 VALORES MÁS ALTOS:")
top3 = sistema.obtener_top_n(3)
for lectura in top3:
    print(f"  {lectura['sensor_id']}: {lectura['valor']}")

🎯 Ejercicios prácticos

🟢 Nivel Básico

Ejercicio 1: Implementá una función que use búsqueda lineal para encontrar la temperatura máxima en una lista.

Ejercicio 2: Modificá el bubble sort para ordenar de mayor a menor.

Ejercicio 3: Creá una función que cuente cuántas comparaciones hace la búsqueda binaria.

🟡 Nivel Medio

Ejercicio 4: Implementá una función que ordene una lista de sensores por ID usando insertion sort.

Ejercicio 5: Creá un sistema que busque el sensor con el valor más cercano a un objetivo usando búsqueda binaria.

Ejercicio 6: Implementá selection sort para ordenar una lista de alarmas por prioridad.

🔴 Nivel Avanzado

Ejercicio 7: Implementá un sistema que mantenga una lista de lecturas siempre ordenada (usa insertion sort al agregar).

Ejercicio 8: Creá una función que compare el tiempo de ejecución de bubble sort vs merge sort con listas de diferentes tamaños.

💡 Consejos y buenas prácticas

✅ Cuándo usar cada algoritmo

Búsqueda Lineal:

• Lista pequeña (< 100 elementos)
• Lista desordenada
• Búsqueda única

Búsqueda Binaria:

• Lista grande y ordenada
• Búsquedas frecuentes
• Necesitás eficiencia

Bubble/Selection/Insertion Sort:

• Listas pequeñas (< 50 elementos)
• Fines educativos
• Lista casi ordenada (insertion sort)

Merge/Quick Sort:

• Listas grandes
• Necesitás eficiencia garantizada (merge sort)
• Memoria no es problema

❌ Errores comunes

1. Usar bubble sort para listas grandes → Usá merge o quick sort
2. Olvidar ordenar antes de búsqueda binaria → Siempre verificá
3. No considerar la complejidad → Analizá antes de implementar
4. Modificar la lista original sin querer → Hacé una copia si es necesario

🎓 Resumen

✅ Búsqueda Lineal: O(n) - Simple pero lenta

✅ Búsqueda Binaria: O(log n) - Rápida pero requiere orden

✅ Bubble Sort: O(n²) - Simple pero ineficiente

✅ Merge Sort: O(n log n) - Eficiente y estable

✅ Quick Sort: O(n log n) - Rápido en la práctica

🚀 Próximos pasos

1. Implementá todos los ejercicios propuestos
2. Medí el tiempo de ejecución de diferentes algoritmos
3. Investigá sobre algoritmos de búsqueda avanzados (hash tables)
4. Estudiá algoritmos de ordenamiento especializados (radix sort, heap sort)

¿Tenés dudas? ¡Preguntá en clase! 🙋‍♂️

¡Ahora a dominar los algoritmos! 💪🔍