# Entrada (desordenada)
numeros = [64, 34, 25, 12, 22, 11, 90]

# Salida (ordenada ascendentemente)

numeros_ordenados = [11, 12, 22, 25, 34, 64, 90]

# Verificación

for i in range(len(numeros_ordenados) - 1):
assert numeros_ordenados[i] <= numeros_ordenados[i + 1]
print("✓ Correctamente ordenado")

def busqueda_lineal(arr, objetivo):
    """O(n) - Sin requisito de orden"""
    for i, elemento in enumerate(arr):
        if elemento == objetivo:
            return i
    return -1

def busqueda_binaria(arr, objetivo):
"""O(log n) - Requiere array ordenado"""
izq, der = 0, len(arr) - 1

    while izq <= der:
        mid = (izq + der) // 2

        if arr[mid] == objetivo:
            return mid
        elif arr[mid] < objetivo:
            izq = mid + 1
        else:
            der = mid - 1

    return -1

# Ejemplo

numeros = [11, 12, 22, 25, 34, 64, 90] # Ya ordenado

# Buscar 25

print(busqueda_lineal(numeros, 25)) # Resultado: 3 (después de 4 comparaciones)
print(busqueda_binaria(numeros, 25)) # Resultado: 3 (después de 2 comparaciones)

# Para 1,000,000 elementos:

# Lineal: hasta 1,000,000 comparaciones

# Binaria: máximo 20 comparaciones (log₂ 1,000,000 ≈ 20)

def tiene_duplicados_ingenuo(arr):
    """O(n²) - Compara todos los pares"""
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            if arr[i] == arr[j]:
                return True
    return False

def tiene_duplicados_eficiente(arr):
    """O(n log n) - Ordena primero"""
    arr_ordenado = sorted(arr)  # O(n log n)

    # Barrido lineal O(n)
    for i in range(len(arr_ordenado) - 1):
        if arr_ordenado[i] == arr_ordenado[i + 1]:
            return True

    return False

# Ejemplo
numeros = [3, 7, 2, 9, 2, 11]
print(tiene_duplicados_eficiente(numeros))  # True

# Explicación:
# Ordenado: [2, 2, 3, 7, 9, 11]
#            ↑  ↑
#         Duplicados adyacentes - fácil de detectar

def kavo_elemento_mas_grande(arr, k):
    """
    Encuentra el k-ésimo elemento más grande
    Tiempo: O(n log n) por el ordenamiento
    """
    arr_ordenado = sorted(arr, reverse=True)
    return arr_ordenado[k - 1]  # O(1) después de ordenar

# Ejemplos

numeros = [64, 34, 25, 12, 22, 11, 90]

print(kavo_elemento_mas_grande(numeros, 1)) # 90 (el más grande)
print(kavo_elemento_mas_grande(numeros, 3)) # 34 (tercero más grande)
print(kavo_elemento_mas_grande(numeros, 7)) # 11 (el más pequeño)

# Ordenado descendente: [90, 64, 34, 25, 22, 12, 11]

# 1° 2° 3° 4° 5° 6° 7°

numeros = [64, 34, 25, 12, 22, 11, 90]

# Ascendente (por defecto)
ascendente = sorted(numeros)
print(f"Ascendente: {ascendente}")
# [11, 12, 22, 25, 34, 64, 90]

# Descendente
descendente = sorted(numeros, reverse=True)
print(f"Descendente: {descendente}")
# [90, 64, 34, 25, 22, 12, 11]

# Registro complejo: estudiantes con múltiples campos
estudiantes = [
    {"nombre": "Ana", "edad": 22, "promedio": 8.5},
    {"nombre": "Carlos", "edad": 20, "promedio": 9.2},
    {"nombre": "María", "edad": 21, "promedio": 7.8},
    {"nombre": "Pedro", "edad": 20, "promedio": 8.9}
]

# Ordenar por edad (campo clave)

por_edad = sorted(estudiantes, key=lambda x: x["edad"])
print("Por edad:")
for est in por_edad:
print(f" {est['nombre']}: {est['edad']} años")

# Ordenar por promedio (descendente)

por_promedio = sorted(estudiantes, key=lambda x: x["promedio"], reverse=True)
print("\nPor promedio:")
for est in por_promedio:
print(f" {est['nombre']}: {est['promedio']}")

# Ordenar por múltiples criterios: primero edad, luego promedio

por_multiple = sorted(estudiantes, key=lambda x: (x["edad"], -x["promedio"]))

from functools import cmp_to_key

# Ejemplo 1: Ordenar strings por longitud

palabras = ["python", "es", "genial", "y", "poderoso"]

por_longitud = sorted(palabras, key=len)
print(f"Por longitud: {por_longitud}")

# ['y', 'es', 'genial', 'python', 'poderoso']

# Ejemplo 2: Orden alfabético inverso

alfabetico_inverso = sorted(palabras, key=str.lower, reverse=True)
print(f"Alfabético inverso: {alfabetico_inverso}")

# Ejemplo 3: Comparación compleja con cmp_to_key

def comparar_numeros_especial(a, b):
"""
Pares antes que impares
Dentro de cada grupo, orden ascendente
""" # Ambos pares o ambos impares
if (a % 2) == (b % 2):
return a - b # a es par, b es impar
if a % 2 == 0:
return -1 # a es impar, b es par
return 1

numeros = [7, 2, 9, 4, 1, 8, 3, 6, 5]
ordenado = sorted(numeros, key=cmp_to_key(comparar_numeros_especial))
print(f"Pares primero: {ordenado}")

# [2, 4, 6, 8, 1, 3, 5, 7, 9]

# ← pares → ← impares →

def selection_sort(arr):
    """
    Selection Sort ingenuo - O(n²)
    """
    n = len(arr)

    for i in range(n):
        # Encontrar el mínimo en el resto del array
        min_idx = i
        for j in range(i + 1, n):  # ← Barrido lineal O(n)
            if arr[j] < arr[min_idx]:
                min_idx = j

        # Intercambiar
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

    return arr

# Análisis de complejidad:
# Iteración 1: n-1 comparaciones
# Iteración 2: n-2 comparaciones
# ...
# Iteración n: 1 comparación
# Total: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)

def heapify(arr, n, i):
    """
    Mantener la propiedad de max-heap
    para el subárbol con raíz en índice i
    """
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    # Si hijo izquierdo es mayor que la raíz
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # Si hijo derecho es mayor que el mayor hasta ahora
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # Si el mayor no es la raíz
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # Recursivamente heapify el subárbol afectado
        heapify(arr, n, largest)

def heap_sort(arr):
"""
Heapsort - O(n log n)
"""
n = len(arr)

    # Paso 1: Construir max-heap - O(n)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Paso 2: Extraer elementos uno por uno - O(n log n)
    for i in range(n - 1, 0, -1):
        # Mover raíz actual al final
        arr[0], arr[i] = arr[i], arr[0]

        # Heapify la raíz reducida
        heapify(arr, i, 0)

    return arr

# Ejemplo

numeros = [64, 34, 25, 12, 22, 11, 90]
print(f"Original: {numeros}")
heap_sort(numeros)
print(f"Ordenado: {numeros}")