Complejidad Temporal

Las operaciones constantes incluyen aritmética básica (suma, resta, multiplicación, división) y acceso directo a elementos de un arreglo, ya que utiliza desplazamiento en memoria contigua. Nota: acceder a un elemento de una lista enlazada no es constante, ya que requiere recorrido. La complejidad temporal se calcula contando el número de operaciones constantes, ignorando términos de orden inferior y coeficientes de los términos dominantes.

Intercambio Mediante Operaciones XOR

Se puede intercambiar dos variables usando operaciones bitwise XOR sin variable temporal:

def intercambiar_xor(val_a, val_b):
    val_a = val_a ^ val_b
    val_b = val_a ^ val_b
    val_a = val_a ^ val_b
    return val_a, val_b

Explicación: supongamos val_a = X, val_b = Y. Tras la primera operación, val_a = X ^ Y. Luego, val_b = (X ^ Y) ^ Y = X, ya que Y ^ Y = 0 y X ^ 0 = X. Finalmente, val_a = (X ^ Y) ^ X = Y. Requisito: las variables deben apuntar a ubicaciones de memoria distintas (no en el mismo arreglo en la misma posición). Se recomienda precaución en su uso.

Extracción del Último Bit 1

Para aislar el bit más bajo con valor 1 de un número entero, se usa la operación: numero & (~numero + 1). Esto aprovecha las propiedades de complemento a dos.

Algoritmos de Ordenamiento

Ordenamiento Burbuja

Compara elementos adyacentes y los intercambia si están en orden incorrecto. En cada pasada, el mayor elemento "flota" al final. Se repite para subarreglos reducidos.

Ordenamiento por Selección

Busca el mínimo en el subarreglo no ordenado y lo coloca en la posición correcta al inicio, expandiendo la región ordenada.

Ordeanmiento por Inserción

Toma un elemento y lo inserta en su posición correcta dentro de la región ordenada a la izquierda, desplazando elementos mayores.

Ordenamiento por Fusión (Merge Sort)

Divide recursivamente el arreglo hasta sublistas de un elemento, luego fusiona sublistas ordenadas en una lista ordenada usando un arreglo auxiliar. Complejidad: O(N log N), ya que reutiliza comparaciones previas.

Variante: Cálculo de Suma Menor

Para encontrar la suma de todos los elementos menores que un dato y ubicados a su izquierda, se adapta merge sort. Durante la fusión, si un elemento izquierdo es menor que uno derecho, se contabiliza su contribución multiplicada por el número de elementos derechos mayores. Esto calcula eficientemente el conteo.

Búsqueda Binaria

• En un arreglo ordenado, determinar si existe un número objetivo.
• En un arreglo ordenado, hallar la posición más a la izquierda de un elemento mayor o igual al objetivo: se mantiene una región donde todos los elementos a la izquierda son menores.
• En un arreglo desordenado, encontrar un mínimo local: se verifica primero los extremos, luego se aplica búsqueda binaria en la región donde la tendencia es descendente.

Problema de la Bandera Holandesa

Variantes para particionar un arreglo en relación a un pivote.

Versión Simplificada

def particionar_simple(datos, pivote):
    limite = -1
    idx = 0
    while idx < len(datos):
        if datos[idx] <= pivote:
            datos[limite + 1], datos[idx] = datos[idx], datos[limite + 1]
            limite += 1
        idx += 1
    return datos

Reordena elementos menores o iguales a la izquierda y mayores a la derecha.

Versión Completa

def particionar_completa(datos, pivote):
    izquierda = -1
    derecha = len(datos)
    idx = 0
    while idx < derecha:
        if datos[idx] < pivote:
            datos[izquierda + 1], datos[idx] = datos[idx], datos[izquierda + 1]
            izquierda += 1
            idx += 1
        elif datos[idx] == pivote:
            idx += 1
        else:
            derecha -= 1
            datos[idx], datos[derecha] = datos[derecha], datos[idx]
    return datos

Separa elementos menores, iguales y mayores al pivote en tres regiones.

Ordenamiento Rápido (Quicksort)

Utiliza la partición de la bandera holandesa. Enfoque 1: elige un pivote (e.g., último elemento), particiona, y recursa en subarreglos. Enfoque 2: usa partición triple para optimizar elementos iguales. Complejidad promedio: O(N log N), pero degenera a O(N²) si el pivote siempre es extremo.

Estructura de Datos Heap

Un heap es un árbol binario casi completo, representado como arreglo. Para un nodo en índice i, su padre está en (i-1)//2, hijo izquierdo en 2i+1, hijo derecho en 2i+2. Un max-heap garantiza que el padre sea mayor o igual que sus hijos.

Operaciones Básicas

• Inserción (heap_insert): agrega un elemento al final y lo promueve hacia arriba intercambiando con el padre si es mayor.
• Extracción (heapify): reemplaza la raíz con el último elemento, luego hunde el nuevo elemento hacia abajo intercambiando con el hijo mayor.

Ordenamiento por Heap

Construye un max-heap con todos los elementos, luego repetidamente extrae el máximo (raíz) y lo coloca al final, aplicando heapify en el subarreglo reducido. Complejidad: O(N log N), espacio O(1) si se hace in-place.

Heap para Casi Ordenados

Para un arreglo donde cada elemento está a distancia máxima k de su posición ordenada, se usa un min-heap de tamaño k+1. Se insertan los primeros k+1 elementos, se extrae el mínimo para la posición actual, y se repite deslizando la ventana.

Ordenamiento por Conteo

Útil para datos con rango limitado (e.g., edades 0-200). Crea un arreglo auxiliar de conteo por valor, calcula posiciones finales usando suma acumulada, y distribuye los elementos.

Ordenamiento Radix

Ordena números decimales dígito a dígito, desde el menos significativo al más significativo. Usa 10 cubetas (0-9) para cada dígito. Optimización con arreglo de conteo: para cada dígito, calcula posiciones finales mediante suma acumulada y reubica elementos establemente.

def ordenamiento_radix(datos):
    max_val = max(datos)
    exp = 1
    while max_val // exp > 0:
        contar = [0] * 10
        salida = [0] * len(datos)
        for num in datos:
            digito = (num // exp) % 10
            contar[digito] += 1
        for i in range(1, 10):
            contar[i] += contar[i - 1]
        for num in reversed(datos):
            digito = (num // exp) % 10
            salida[contar[digito] - 1] = num
            contar[digito] -= 1
        datos[:] = salida
        exp *= 10
    return datos