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

// Funciones de ordenamiento
void burbuja(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void insercion(int arr[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {
        temp = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

void seleccion(int arr[], int n) {
    int i, j, min, temp;
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min])
                min = j;
        }
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

// Búsquedas
int secuencial(int arr[], int n, int x, int *comparaciones) {
    *comparaciones = 0;
    for (int i = 0; i < n; i++) {
        (*comparaciones)++;
        if (arr[i] == x)
            return i;
    }
    return -1;
}

int binaria(int arr[], int n, int x, int *comparaciones) {
    int inicio = 0, fin = n - 1, medio;
    *comparaciones = 0;
    while (inicio <= fin) {
        medio = (inicio + fin) / 2;
        (*comparaciones)++;
        if (arr[medio] == x)
            return medio;
        else if (arr[medio] < x)
            inicio = medio + 1;
        else
            fin = medio - 1;
    }
    return -1;
}

int main() {
    int n, opcion, valor, resultado, comparaciones;
    printf("Ingrese la longitud del arreglo: ");
    scanf("%d", &n);

    int arr[n];
    printf("Ingrese %d valores enteros:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    do {
        printf("\n--- MENU ---\n");
        printf("1. Ordenamiento Burbuja\n");
        printf("2. Ordenamiento Insercion\n");
        printf("3. Ordenamiento Seleccion\n");
        printf("4. Busqueda Secuencial\n");
        printf("5. Busqueda Binaria\n");
        printf("6. Salir\n");
        printf("Elija una opcion: ");
        scanf("%d", &opcion);

        switch (opcion) {
            case 1:
                burbuja(arr, n);
                printf("Arreglo ordenado (Burbuja): ");
                for (int i = 0; i < n; i++) printf("%d ", arr[i]);
                printf("\n");
                break;
            case 2:
                insercion(arr, n);
                printf("Arreglo ordenado (Insercion): ");
                for (int i = 0; i < n; i++) printf("%d ", arr[i]);
                printf("\n");
                break;
            case 3:
                seleccion(arr, n);
                printf("Arreglo ordenado (Seleccion): ");
                for (int i = 0; i < n; i++) printf("%d ", arr[i]);
                printf("\n");
                break;
            case 4:
                printf("Arreglo actual: ");
                for (int i = 0; i < n; i++) printf("%d ", arr[i]);
                printf("\nIngrese el valor a buscar: ");
                scanf("%d", &valor);
                resultado = secuencial(arr, n, valor, &comparaciones);
                if (resultado != -1)
                    printf("Encontrado en posicion %d con %d comparaciones.\n", resultado, comparaciones);
                else
                    printf("No encontrado tras %d comparaciones.\n", comparaciones);
                break;
            case 5:
                printf("Arreglo actual: ");
                for (int i = 0; i < n; i++) printf("%d ", arr[i]);
                printf("\nIngrese el valor a buscar: ");
                scanf("%d", &valor);
                resultado = binaria(arr, n, valor, &comparaciones);
                if (resultado != -1)
                    printf("Encontrado en posicion %d con %d comparaciones.\n", resultado, comparaciones);
                else
                    printf("No encontrado tras %d comparaciones.\n", comparaciones);
                break;
            case 6:
                printf("Saliendo...\n");
                break;
            default:
                printf("Opcion invalida.\n");
        }
    } while (opcion != 6);

    return 0;
}