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 arrays 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 reservar el buffer una sola vez y reutilizarlo en toda la recursión.

• Verifica que la mezcla copie de regreso al array 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 subarrays pequeños si quieres mejorar constantes.

• Evita peores casos con pivote aleatorio o mediana de tres.
• Para subarrays de tamaño <= 16, cambia a Insertion Sort.
• Si temes desbordar la pila, 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 arrays 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 el array 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.

8.5 Crear un menú interactivo en main.c

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

• Agrega una opción para regenerar datos sin salir del programa.
• Permite cambiar el tamaño del array 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 clock() para obtener tiempos en milisegundos. En arrays pequeños las diferencias pueden ser mínimas; aumenta n para observar las variaciones.

• Ejecuta cada algoritmo varias veces y promedia para reducir ruido.
• Si dispones de clock_gettime, usa alta resolución para n pequeño.
• Reporta también la cantidad de elementos para contextualizar el tiempo.

8.7 Compilar y depurar en CLion

Configura la ejecución en el IDE para compilar todos los archivos. 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 el array 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 = 1 000, 10 000, 50 000) 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, compilador, flags) para reproducibilidad.

8.9 Códigos completos del proyecto

Estructura propuesta lista para compilar en CLion. Incluye un menú simple y las tres implementaciones.

/* sort.h */
void mergesort_topdown(int *arr, int n);
void quicksort(int *arr, int inicio, int fin);
void heapsort(int *arr, int n);
void printArray(const int *arr, int n);
void copiar_array(const int *origen, int *destino, int n);
void llenar_aleatorio(int *arr, int n, int max_val);

/* sort.c */
#include <stdio.h>
#include <stdlib.h>
#include "sort.h"

void printArray(const int *arr, int n) {
  printf("[");
  for (int i = 0; i < n; i++) {
    printf("%d", arr[i]);
    if (i + 1 < n) {
      printf(", ");
    }
  }
  printf("]\n");
}

void copiar_array(const int *origen, int *destino, int n) {
  for (int i = 0; i < n; i++) {
    destino[i] = origen[i];
  }
}

void llenar_aleatorio(int *arr, int n, int max_val) {
  for (int i = 0; i < n; i++) {
    arr[i] = rand() % max_val;
  }
}

/* mergesort.c */
#include <stdlib.h>
#include "sort.h"

static void merge_with_buffer(int *arr, int *buffer, int inicio, int medio, int fin) {
  int i = inicio;
  int j = medio + 1;
  int k = inicio;
  while (i <= medio && j <= fin) {
    if (arr[i] <= arr[j]) {
      buffer[k++] = arr[i++];
    } else {
      buffer[k++] = arr[j++];
    }
  }
  while (i <= medio) {
    buffer[k++] = arr[i++];
  }
  while (j <= fin) {
    buffer[k++] = arr[j++];
  }
  for (int t = inicio; t <= fin; t++) {
    arr[t] = buffer[t];
  }
}

static void mergesort_rec(int *arr, int *buffer, int inicio, int fin) {
  if (inicio >= fin) {
    return;
  }
  int 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);
}

void mergesort_topdown(int *arr, int n) {
  int *buffer = malloc(sizeof(int) * n);
  if (!buffer) {
    return;
  }
  mergesort_rec(arr, buffer, 0, n - 1);
  free(buffer);
}

/* quicksort.c */
#include "sort.h"

static int mediana_de_tres(int *arr, int inicio, int fin) {
  int medio = (inicio + fin) / 2;
  if (arr[medio] < arr[inicio]) {
    int tmp = arr[medio]; arr[medio] = arr[inicio]; arr[inicio] = tmp;
  }
  if (arr[fin] < arr[inicio]) {
    int tmp = arr[fin]; arr[fin] = arr[inicio]; arr[inicio] = tmp;
  }
  if (arr[fin] < arr[medio]) {
    int tmp = arr[fin]; arr[fin] = arr[medio]; arr[medio] = tmp;
  }
  return medio;
}

static int particion_lomuto_mediana(int *arr, int inicio, int fin) {
  int m = mediana_de_tres(arr, inicio, fin);
  int tmp = arr[m]; arr[m] = arr[fin]; arr[fin] = tmp;
  int pivote = arr[fin];
  int i = inicio - 1;
  for (int j = inicio; j < fin; j++) {
    if (arr[j] <= pivote) {
      i++;
      int swap = arr[i];
      arr[i] = arr[j];
      arr[j] = swap;
    }
  }
  int swap = arr[i + 1];
  arr[i + 1] = arr[fin];
  arr[fin] = swap;
  return i + 1;
}

void quicksort(int *arr, int inicio, int fin) {
  if (inicio >= fin) {
    return;
  }
  int p = particion_lomuto_mediana(arr, inicio, fin);
  quicksort(arr, inicio, p - 1);
  quicksort(arr, p + 1, fin);
}

/* heapsort.c */
#include "sort.h"

static void sift_down(int *arr, int n, int i) {
  int mayor = i;
  int hijo_izq = 2 * i + 1;
  int hijo_der = 2 * i + 2;
  if (hijo_izq < n && arr[hijo_izq] > arr[mayor]) {
    mayor = hijo_izq;
  }
  if (hijo_der < n && arr[hijo_der] > arr[mayor]) {
    mayor = hijo_der;
  }
  if (mayor != i) {
    int tmp = arr[i];
    arr[i] = arr[mayor];
    arr[mayor] = tmp;
    sift_down(arr, n, mayor);
  }
}

static void heapify(int *arr, int n) {
  for (int i = (n / 2) - 1; i >= 0; i--) {
    sift_down(arr, n, i);
  }
}

void heapsort(int *arr, int n) {
  heapify(arr, n);
  for (int fin = n - 1; fin > 0; fin--) {
    int tmp = arr[0];
    arr[0] = arr[fin];
    arr[fin] = tmp;
    sift_down(arr, fin, 0);
  }
}

/* main.c */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"

typedef void (*sort_fn)(int *, int);
typedef void (*sort_range_fn)(int *, int, int);

void ejecutar_y_medir(const char *nombre, sort_fn fn, int *arr, int n) {
  clock_t inicio = clock();
  fn(arr, n);
  clock_t fin = clock();
  double ms = (double)(fin - inicio) * 1000.0 / CLOCKS_PER_SEC;
  printf("%s -> tiempo: %.3f ms\n", nombre, ms);
}

void ejecutar_y_medir_rango(const char *nombre, sort_range_fn fn, int *arr, int inicio, int fin) {
  clock_t inicio_t = clock();
  fn(arr, inicio, fin);
  clock_t fin_t = clock();
  double ms = (double)(fin_t - inicio_t) * 1000.0 / CLOCKS_PER_SEC;
  printf("%s -> tiempo: %.3f ms\n", nombre, ms);
}

int main(void) {
  const int MAX = 50000;
  int *original = malloc(sizeof(int) * MAX);
  int *trabajo = malloc(sizeof(int) * MAX);
  int n = 0;

  if (!original || !trabajo) {
    printf("No se pudo reservar memoria.\n");
    return 1;
  }

  srand((unsigned)time(NULL));

  printf("Ingrese cantidad de elementos (max %d): ", MAX);
  if (scanf("%d", &n) != 1 || n <= 0 || n > MAX) {
    printf("Tamano no valido.\n");
    return 1;
  }

  llenar_aleatorio(original, n, 100000);
  printf("Antes: ");
  printArray(original, n);

  printf("Seleccione algoritmo (m)erge, (q)uick, (h)eap: ");
  char opcion = 0;
  if (scanf(" %c", &opcion) != 1) {
    printf("Entrada no valida.\n");
    return 1;
  }

  copiar_array(original, trabajo, n);
  switch (opcion) {
    case 'm':
      ejecutar_y_medir("MergeSort", mergesort_topdown, trabajo, n);
      break;
    case 'q':
      ejecutar_y_medir_rango("QuickSort", quicksort, trabajo, 0, n - 1);
      break;
    case 'h':
      ejecutar_y_medir("HeapSort", heapsort, trabajo, n);
      break;
    default:
      printf("Opcion no reconocida.\n");
      free(original);
      free(trabajo);
      return 1;
  }

  printf("Despues: ");
  printArray(trabajo, n);

  free(original);
  free(trabajo);
  return 0;
}