Estructuras de datos lineales y algoritmos de ordenamiento

La Ceiba registra la venta de cada día. Se necesita: agregar el día nuevo, corregir un error de digitación, conocer total/promedio/mejor día y ver los últimos días, sin volver a escribir los datos.

Una lista es una secuencia ordenada y modificable. Cada elemento tiene una posición (índice) que empieza en 0. Es el “rango de celdas” de Python.

ventas = [340, 410, 0, 520, 610, 890]   # lunes a sábado

ventas.append(450)          # llega el domingo
ventas[2] = 380             # el miércoles se digitó 0 por error
print(f"Ventas: {ventas}")
print(f"Días: {len(ventas)}  Total: {sum(ventas)}  Promedio: {sum(ventas) / len(ventas):.2f}")

mejor = max(ventas)
dia_mejor = ventas.index(mejor) + 1     # +1 porque los índices empiezan en 0
print(f"Mejor día: {dia_mejor} (${mejor})")

print(f"Fin de semana: {ventas[-2:]}")
print(f"Primeros 3 días: {ventas[:3]}")
print(f"Días impares (1, 3, 5, 7): {ventas[::2]}")

sobre_500 = [v for v in ventas if v > 500]    # comprensión de lista
print(f"Días sobre $500: {sobre_500}")

Ventas: [340, 410, 380, 520, 610, 890, 450]
Días: 7  Total: 3600  Promedio: 514.29
Mejor día: 6 ($890)
Fin de semana: [890, 450]
Primeros 3 días: [340, 410, 380]
Días impares (1, 3, 5, 7): [340, 380, 610, 450]
Días sobre $500: [520, 610, 890]

Compara con el E4 de la semana 3: aquello que requería contadores manuales y dos listas escritas ahora son funciones de una palabra. El dato corregido (miércoles) sube el promedio de $460 a $514.29: un error de digitación en un solo día cambiaba el diagnóstico de la semana.

Slicing, en resumen: lista[inicio:fin:paso], incluye inicio, excluye fin; cualquiera se puede omitir. [:] es una copia completa.

El cajero escanea un código. ¿Está en el catálogo? ¿En qué posición? ¿Cuánto trabajo cuesta averiguarlo?

Sin ningún orden en los datos, la única estrategia es revisar uno por uno desde el principio hasta encontrarlo o acabar. Devolvemos la posición, o -1 si no está (una convención común). Contamos comparaciones para medir el trabajo.

def buscar_producto(catalogo, codigo_buscado):
    """Búsqueda lineal por código.

    Returns:
        (posicion, comparaciones); posicion es -1 si no se encontró.
    """
    comparaciones = 0
    for i in range(len(catalogo)):
        comparaciones += 1
        codigo = catalogo[i][0]           # primer campo de la tupla
        if codigo == codigo_buscado:
            return i, comparaciones       # se detiene al encontrarlo
    return -1, comparaciones


catalogo = [("A01", "Aceite", 12.50), ("B07", "Arroz", 4.25),
            ("C12", "Azúcar", 3.90), ("D03", "Café", 6.75)]

for codigo in ["A01", "D03", "Z99"]:
    posicion, comps = buscar_producto(catalogo, codigo)
    print(f"{codigo}: posición {posicion}, {comps} comparaciones")

A01: posición 0, 1 comparaciones
D03: posición 3, 4 comparaciones
Z99: posición -1, 4 comparaciones

Mejor caso (primero de la lista): 1 comparación. Peor caso (último o inexistente): n comparaciones. Con 4 productos no importa; con 50,000 productos y 2,000 ventas al día, sí. Por eso importa ordenar: con datos ordenados existen búsquedas mucho más rápidas (búsqueda binaria), que verás en Estructuras de Datos.

¿Cómo ordenar de menor a mayor los montos [42, 17, 58, 23, 9] usando solo comparaciones entre dos elementos vecinos?

REPETIR para cada pasada, mientras haya habido intercambios:
    PARA cada par de vecinos (j, j+1) en la parte aún no ordenada:
        SI datos[j] > datos[j+1] ENTONCES intercambiarlos
    (al final de la pasada, el mayor restante quedó en su lugar)

"""Algoritmos de ordenamiento elementales con conteo de trabajo."""


def burbuja(lista):
    """Bubble Sort ascendente.

    Returns:
        (lista_ordenada, comparaciones, intercambios). No modifica la original.
    """
    datos = lista[:]                     # copia
    n = len(datos)
    comparaciones = 0
    intercambios = 0
    for pasada in range(n - 1):
        hubo_intercambio = False
        for j in range(n - 1 - pasada):  # los últimos 'pasada' ya están en su lugar
            comparaciones += 1
            if datos[j] > datos[j + 1]:
                datos[j], datos[j + 1] = datos[j + 1], datos[j]   # intercambio
                intercambios += 1
                hubo_intercambio = True
        if not hubo_intercambio:         # nada se movió: ya está ordenada
            break
    return datos, comparaciones, intercambios


def insercion(lista):
    """Insertion Sort ascendente.

    Returns:
        (lista_ordenada, comparaciones). No modifica la original.
    """
    datos = lista[:]
    comparaciones = 0
    for i in range(1, len(datos)):
        actual = datos[i]
        j = i - 1
        while j >= 0:
            comparaciones += 1
            if datos[j] > actual:
                datos[j + 1] = datos[j]  # desplaza el mayor una posición a la derecha
                j -= 1
            else:
                break
        datos[j + 1] = actual            # inserta en el hueco
    return datos, comparaciones

from ordenamiento import burbuja, insercion

montos = [42, 17, 58, 23, 9]
print(burbuja(montos))
print(insercion(montos))
print(montos)                      # la original sigue igual

([9, 17, 23, 42, 58], 10, 7)
([9, 17, 23, 42, 58], 9)
[42, 17, 58, 23, 9]

Bubble Sort hizo 4 pasadas con 4 + 3 + 2 + 1 = 10 comparaciones y 7 intercambios. La línea datos[j], datos[j + 1] = datos[j + 1], datos[j] intercambia dos valores gracias a las tuplas (sin variable temporal).

Insertion Sort funciona como ordenar facturas en la mano: tomas la siguiente y la deslizas hacia la izquierda hasta su lugar. Aquí hizo 9 comparaciones.

La bandera hubo_intercambio es una optimización: si una pasada no mueve nada, la lista ya está ordenada y se sale con break.

Para 5 montos da igual. ¿Y para 100, 1,000 o 10,000 transacciones? ¿Y si los datos ya vienen casi ordenados (como un registro por fecha)?

Dos formas de medir: contar comparaciones (no depende de la computadora, se puede razonar) y medir tiempo (depende de la máquina y varía entre ejecuciones). La primera es la que se defiende en un examen; la segunda confirma en la práctica.

import random

from ordenamiento import burbuja, insercion

N = 100
random.seed(2026)                                   # misma "aleatoriedad" en cada ejecución
ordenada = list(range(1, N + 1))
inversa = ordenada[::-1]
aleatoria = [random.randint(1, 1000) for _ in range(N)]

print(f"{'Escenario':<10} {'Bubble comp':>12} {'Bubble inter':>13} {'Insertion comp':>15}")
for nombre, datos in [("ordenada", ordenada), ("inversa", inversa), ("aleatoria", aleatoria)]:
    _, comp_b, inter_b = burbuja(datos)
    _, comp_i = insercion(datos)
    print(f"{nombre:<10} {comp_b:>12} {inter_b:>13} {comp_i:>15}")

Escenario   Bubble comp  Bubble inter  Insertion comp
ordenada             99             0              99
inversa            4950          4950            4950
aleatoria          4779          2515            2612

Y midiendo tiempo con listas aleatorias de distinto tamaño:

import random
import time

from ordenamiento import burbuja, insercion

for n in [100, 1000, 3000]:
    datos = [random.randint(1, 100000) for _ in range(n)]
    inicio = time.perf_counter()
    burbuja(datos)
    t_burbuja = time.perf_counter() - inicio
    inicio = time.perf_counter()
    insercion(datos)
    t_insercion = time.perf_counter() - inicio
    print(f"n={n:>5}: burbuja {t_burbuja:.4f} s, inserción {t_insercion:.4f} s")

n=  100: burbuja 0.0004 s, inserción 0.0001 s
n= 1000: burbuja 0.0370 s, inserción 0.0149 s
n= 3000: burbuja 0.3805 s, inserción 0.1473 s

• Peor caso (inversa): ambos hacen n(n − 1)/2 = 4,950 comparaciones. Duplicar n cuadruplica el trabajo: crecimiento cuadrático (se escribe O(n²)). Por eso de 1,000 a 3,000 datos el tiempo se multiplica por ~9, no por 3.
• Datos ya ordenados: gracias a la bandera, Bubble Sort para tras una pasada (99 comparaciones); Insertion Sort también hace 99. Ambos se vuelven lineales.
• Datos aleatorios: Insertion Sort hace aproximadamente la mitad de comparaciones que Bubble Sort, y muchos menos movimientos.
• Decisión de negocio: para registros que llegan casi ordenados (por fecha), Insertion Sort es razonable. Para volúmenes grandes, ninguno de los dos: sorted() usa un algoritmo mucho más eficiente.