8 - Proyecto final del tutorial

Integraremos MergeSort, QuickSort y HeapSort en un solo proyecto para comparar rendimiento, uso de memoria y estabilidad. El menú permitirá elegir el algoritmo, ordenar listas de prueba y medir tiempos, con opciones para repetir pruebas y observar tendencias.

8.1 Implementar MergeSort completo

Incluye la versión top-down con buffer compartido y la función de mezcla estable. Recuerda crear el buffer una sola vez y reutilizarlo en toda la recursión.

  • Verifica que la mezcla copie de regreso a la lista original tras cada fusión.
  • Controla el tamaño del buffer para evitar desbordes (usa n elementos).
  • Si necesitas estabilidad, mantén la comparación <=.

8.2 Implementar QuickSort con dos particiones

Usa mediana de tres para el pivote y partición de Lomuto o Hoare. Limita la profundidad de recursión y alterna a Insertion Sort para sublistas pequeñas si quieres mejorar constantes.

  • Evita peores casos con pivote aleatorio o mediana de tres.
  • Para sublistas de tamaño <= 16, cambia a Insertion Sort.
  • Si temes profundidades grandes, establece un límite y cae a HeapSort (introsort).

8.3 Implementar HeapSort desde cero

Agrega las funciones heapify y sift_down para construir el heap y ordenar in-place. Garantiza O(n log n) sin usar memoria extra.

  • Implementa sift_down iterativo para evitar recursión.
  • Usa el rango reducido (fin) tras cada extracción.
  • Si necesitas estabilidad, considera no usar HeapSort o aplicar un wrapper estable.

8.4 Comparar algoritmos con listas iguales

Genera los mismos datos de entrada para cada algoritmo (aleatorios, casi ordenados, inversos) y mide el tiempo de ejecución y, si deseas, el número de comparaciones.

  • Clona la lista original antes de cada prueba para mantener igualdad de condiciones.
  • Incluye un caso con muchos duplicados para observar estabilidad y particiones.
  • Guarda las métricas en un archivo CSV si planeas graficar.

Un menú por consola permite elegir el algoritmo (m, q, h), volver a generar datos y repetir las pruebas sin reejecutar el archivo.

  • Agrega una opción para regenerar datos sin salir del programa.
  • Permite cambiar el tamaño de la lista en cada iteración para ver escalabilidad.
  • Muestra un breve resumen de complejidad tras ejecutar cada opción.

8.6 Mostrar tiempos de ejecución (opcional)

Usa time.perf_counter() para obtener tiempos en milisegundos. En listas pequeñas las diferencias pueden ser mínimas; aumenta n para observar las variaciones.

  • Ejecuta cada algoritmo varias veces y promedia para reducir ruido.
  • Usa alta resolución para n pequeño con perf_counter.
  • Reporta también la cantidad de elementos para contextualizar el tiempo.

8.7 Depurar en Python

Configura la ejecución en tu editor (VS Code o terminal). Coloca breakpoints en las funciones de mezcla, partición y sift-down para observar su comportamiento.

  • Activa inspección de variables para ver cómo cambian los índices.
  • Usa el depurador para comparar la cantidad de llamadas recursivas en QuickSort y MergeSort.
  • Comprueba que HeapSort modifique solo la lista original (sin buffers auxiliares).

8.8 Refinar código y medir Big-O empíricamente

Registra los tiempos para distintos tamaños de entrada (n = 1000, 10000, 50000) y observa la tendencia. Ajusta el pivote de QuickSort o el tamaño de buffer de MergeSort si es necesario.

  • Grafica tiempo vs. n en escala logarítmica para validar la tendencia n log n.
  • Compara consumo de memoria si tu plataforma permite medirlo.
  • Documenta configuraciones (CPU, versión de Python) para reproducibilidad.

8.9 Código completo del proyecto

Estructura propuesta en un solo archivo ordenamientos.py. Incluye un menú simple y las tres implementaciones.

import random
import time

def merge_with_buffer(arr, buffer, inicio, medio, fin):
  i = inicio
  j = medio + 1
  k = inicio
  while i <= medio and j <= fin:
    if arr[i] <= arr[j]:
      buffer[k] = arr[i]
      i += 1
    else:
      buffer[k] = arr[j]
      j += 1
    k += 1
  while i <= medio:
    buffer[k] = arr[i]
    i += 1
    k += 1
  while j <= fin:
    buffer[k] = arr[j]
    j += 1
    k += 1
  arr[inicio:fin + 1] = buffer[inicio:fin + 1]

def mergesort_rec(arr, buffer, inicio, fin):
  if inicio >= fin:
    return
  medio = (inicio + fin) // 2
  mergesort_rec(arr, buffer, inicio, medio)
  mergesort_rec(arr, buffer, medio + 1, fin)
  merge_with_buffer(arr, buffer, inicio, medio, fin)

def mergesort_topdown(arr):
  if not arr:
    return
  buffer = [0] * len(arr)
  mergesort_rec(arr, buffer, 0, len(arr) - 1)

def mediana_de_tres(arr, inicio, fin):
  medio = (inicio + fin) // 2
  if arr[medio] < arr[inicio]:
    arr[medio], arr[inicio] = arr[inicio], arr[medio]
  if arr[fin] < arr[inicio]:
    arr[fin], arr[inicio] = arr[inicio], arr[fin]
  if arr[fin] < arr[medio]:
    arr[fin], arr[medio] = arr[medio], arr[fin]
  return medio

def particion_lomuto_mediana(arr, inicio, fin):
  m = mediana_de_tres(arr, inicio, fin)
  arr[m], arr[fin] = arr[fin], arr[m]
  pivote = arr[fin]
  i = inicio - 1
  for j in range(inicio, fin):
    if arr[j] <= pivote:
      i += 1
      arr[i], arr[j] = arr[j], arr[i]
  arr[i + 1], arr[fin] = arr[fin], arr[i + 1]
  return i + 1

def quicksort(arr, inicio, fin):
  if inicio >= fin:
    return
  p = particion_lomuto_mediana(arr, inicio, fin)
  quicksort(arr, inicio, p - 1)
  quicksort(arr, p + 1, fin)

def sift_down(arr, n, i):
  mayor = i
  hijo_izq = 2 * i + 1
  hijo_der = 2 * i + 2
  if hijo_izq < n and arr[hijo_izq] > arr[mayor]:
    mayor = hijo_izq
  if hijo_der < n and arr[hijo_der] > arr[mayor]:
    mayor = hijo_der
  if mayor != i:
    arr[i], arr[mayor] = arr[mayor], arr[i]
    sift_down(arr, n, mayor)

def heapify(arr):
  n = len(arr)
  for i in range((n // 2) - 1, -1, -1):
    sift_down(arr, n, i)

def heapsort(arr):
  heapify(arr)
  for fin in range(len(arr) - 1, 0, -1):
    arr[0], arr[fin] = arr[fin], arr[0]
    sift_down(arr, fin, 0)

def ejecutar_y_medir(nombre, fn, arr):
  inicio = time.perf_counter()
  fn(arr)
  fin = time.perf_counter()
  ms = (fin - inicio) * 1000.0
  print(f"{nombre} -> tiempo: {ms:.3f} ms")

def ejecutar_y_medir_rango(nombre, fn, arr):
  inicio = time.perf_counter()
  fn(arr, 0, len(arr) - 1)
  fin = time.perf_counter()
  ms = (fin - inicio) * 1000.0
  print(f"{nombre} -> tiempo: {ms:.3f} ms")

def generar_aleatorio(n, max_val):
  return [random.randint(0, max_val) for _ in range(n)]

def menu():
  max_n = 50000
  n = int(input(f"Ingrese cantidad de elementos (max {max_n}): "))
  if n <= 0 or n > max_n:
    print("Tamano no valido.")
    return

  original = generar_aleatorio(n, 100000)
  print("Antes:", original[:20], "...")

  opcion = input("Seleccione algoritmo (m)erge, (q)uick, (h)eap: ").strip().lower()
  trabajo = list(original)

  if opcion == "m":
    ejecutar_y_medir("MergeSort", mergesort_topdown, trabajo)
  elif opcion == "q":
    ejecutar_y_medir_rango("QuickSort", quicksort, trabajo)
  elif opcion == "h":
    ejecutar_y_medir("HeapSort", heapsort, trabajo)
  else:
    print("Opcion no reconocida.")
    return

  print("Despues:", trabajo[:20], "...")

if __name__ == "__main__":
  menu()
ordenamientos eficientes
Retornar