#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// --- 1. Implementación de Burbuja ---
void burbuja(int v[], int n, int *c, int *s) {
    *c = 0; // Inicializar comparaciones
    *s = 0; // Inicializar intercambios
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            (*c)++; // Se realiza una comparación
            if (v[j] > v[j + 1]) {
                int temp = v[j];
                v[j] = v[j + 1];
                v[j + 1] = temp;
                (*s)++; // Se realiza un intercambio
            }
        }
    }
}

// --- 2. Implementación de Inserción ---
void insercion(int v[], int n, int *c, int *s) {
    *c = 0;
    *s = 0;
    for (int i = 1; i < n; i++) {
        int clave = v[i];
        int j = i - 1;
        
        // La condición del while involucra una comparación
        while (j >= 0) {
            (*c)++; 
            if (v[j] > clave) {
                v[j + 1] = v[j];
                (*s)++; // Desplazamiento (cuenta como intercambio de posición)
                j--;
            } else {
                break; // Si no es mayor, rompe el ciclo
            }
        }
        v[j + 1] = clave;
    }
}

// --- Algoritmo Extra: Selección (Para completar los tres) ---
void seleccion(int v[], int n, int *c, int *s) {
    *c = 0;
    *s = 0;
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            (*c)++;
            if (v[j] < v[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            int temp = v[i];
            v[i] = v[min_idx];
            v[min_idx] = temp;
            (*s)++;
        }
    }
}

// --- 3. Función auxiliar para copiar arreglos ---
void copiarArreglo(int origen[], int destino[], int n) {
    for (int i = 0; i < n; i++) {
        destino[i] = origen[i];
    }
}

// --- Funciones para generar los 3 estados del arreglo ---
void generarAleatorio(int v[], int n) {
    for (int i = 0; i < n; i++) {
        v[i] = rand() % 100; // Números entre 0 y 99
    }
}

void generarOrdenado(int v[], int n) {
    for (int i = 0; i < n; i++) {
        v[i] = i;
    }
}

void generarInvertido(int v[], int n) {
    for (int i = 0; i < n; i++) {
        v[i] = n - i;
    }
}

// --- 4. Función para imprimir la tabla comparativa ---
void imprimirTabla(const char* estado, int compB, int intB, int compI, int intI, int compS, int intS) {
    printf("\n--- Estado del Arreglo: %s ---\n", estado);
    printf("%-15s | %-13s | %-12s\n", "Algoritmo", "Comparaciones", "Intercambios");
    printf("--------------------------------------------------\n");
    printf("%-15s | %-13d | %-12d\n", "Burbuja", compB, intB);
    printf("%-15s | %-13d | %-12d\n", "Insercion", compI, intI);
    printf("%-15s | %-13d | %-12d\n", "Seleccion", compS, intS);
    printf("--------------------------------------------------\n");
}

int main() {
    int n = 20; // Tamaño del arreglo de prueba (puedes cambiarlo)
    int original[n], copia[n];
    int comp, inter; // Variables para capturar los conteos
    
    // Variables de almacenamiento para la tabla
    int cB, sB, cI, sI, cS, sS;

    srand(time(NULL)); // Semilla para números aleatorios

    // ==========================================
    // 5. EVALUACIÓN DE LOS TRES ESTADOS
    // ==========================================

    // --- CASO 1: ALEATORIO ---
    generarAleatorio(original, n);
    
    copiarArreglo(original, copia, n);
    burbuja(copia, n, &cB, &sB);
    
    copiarArreglo(original, copia, n);
    insercion(copia, n, &cI, &sI);
    
    copiarArreglo(original, copia, n);
    seleccion(copia, n, &cS, &sS);
    
    imprimirTabla("ALEATORIO", cB, sB, cI, sI, cS, sS);

    // --- CASO 2: YA ORDENADO ---
    generarOrdenado(original, n);
    
    copiarArreglo(original, copia, n);
    burbuja(copia, n, &cB, &sB);
    
    copiarArreglo(original, copia, n);
    insercion(copia, n, &cI, &sI);
    
    copiarArreglo(original, copia, n);
    seleccion(copia, n, &cS, &sS);
    
    imprimirTabla("YA ORDENADO", cB, sB, cI, sI, cS, sS);

    // --- CASO 3: INVERTIDO ---
    generarInvertido(original, n);
    
    copiarArreglo(original, copia, n);
    burbuja(copia, n, &cB, &sB);
    
    copiarArreglo(original, copia, n);
    insercion(copia, n, &cI, &sI);
    
    copiarArreglo(original, copia, n);
    seleccion(copia, n, &cS, &sS);
    
    imprimirTabla("INVERTIDO", cB, sB, cI, sI, cS, sS);

    return 0;
}