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


using namespace std;

// Constantes
#define MAX 10

// Variables
int A[ MAX ]; // Arreglo de enteros
int N = MAX; // Total de elementos

// *** Sección de Prototipos
// Funciones generales
void MenuPrincipal();
void IngresarUsuario();
void IngresarAleatorio();
void MostrarArreglo();
void MostrarTiempo( time_t Inicio, time_t Final );

// Métodos de Ordenación
void BubbleSort( int A[], int N );
void ShakerSort( int A[], int N );
void InsercionDirecta( int A[], int N );
void InsercionBinaria( int A[], int N );
void SeleccionDirecta( int A[], int N );
void Shell( int A[], int N );
void QuickSort( int A[], int Izq, int Der );
void HeapSort( int A[], int N );
void Merge( int A[], int Izq, int Der);

// Métodos de Ordenación
int BusqSec( int A[], int N, int X );
int BusqBin( int A[], int N, int X );
int Hash();


// Implementación de procedimientos y funciones de usuario generales
void IngresarUsuario()
{
  for ( int i=0; i < MAX; i++)
    {
      cout << "Introduce elemento " << i + 1 << ": ";
      cin >> A[i];
    };
};

void IngresarAleatorio()
{
  srand(time(NULL));
  for ( int i=0; i < MAX; i++)
      A[i]= rand() % 999;
 };

void MostrarArreglo()
{
  for (int i=0; i<MAX; i++)
      cout << A[i] << " ";
  cout << endl;
};

void MostrarTiempo( time_t Inicio, time_t Final )
{
  printf( "Comienzo: %u s\n", Inicio );
  printf( "Final: %u s\n", Final );
  printf( "Número de segundos transcurridos desde el comienzo del programa: %f s\n", difftime( Final, Inicio) ); 
  system("pause");
}

// Implementación de Métodos de Ordenación

// Métodos de Ordenación
void BubbleSort( int A[], int N )
{
    // Ciclo externo realiza N-1 iteraciones
    for (int i = 0; i < N - 1; i++)
    {
        // Ciclo interno para comparar e intercambiar si es necesario
        for (int j = 0; j < N - i - 1; j++)
        {
            if (A[j] > A[j + 1])
            {
                // Intercambio de elementos
                int AUX = A[j];
                A[j] = A[j + 1];
                A[j + 1] = AUX;
            }
        }

    }
        MostrarArreglo();
        system("pause");
}

void ShakerSort( int A[], int N )
{
    int IZQ = 1;
    int DER = N - 1;
    int K = N - 1;
    int AUX;

    do {
        // Ciclo descendente (de derecha a izquierda)
        for (int I = DER; I >= IZQ; I--) {
            if (A[I - 1] > A[I]) {
                // Intercambiar A[I-1] y A[I]
                AUX = A[I - 1];
                A[I - 1] = A[I];
                A[I] = AUX;
                K = I;
            }
        }

        IZQ = K + 1;

        // Ciclo ascendente (de izquierda a derecha)
        for (int I = IZQ; I <= DER; I++) {
            if (A[I - 1] > A[I]) {
                // Intercambiar A[I-1] y A[I]
                AUX = A[I - 1];
                A[I - 1] = A[I];
                A[I] = AUX;
                K = I;
            }
        }

        DER = K - 1;

    } while (DER >= IZQ); // Termina cuando los índices se crucen
    MostrarArreglo();
    system ("pause");
}

void InsercionDirecta( int A[], int N )
{
    int AUX, K;

    for (int i = 1; i < N; i++){
        AUX = A[i];
        K = i - 1;
        while (K >= 0 && A[K] > AUX){
            A[K + 1] = A[K];
            K -= 1;
        }
        A[K + 1] = AUX;
    }
    MostrarArreglo();
    system ("pause");
}

void InsercionBinaria( int A[], int N )
{
    int AUX, IZQ, DER, M, J;

    for (int I = 1; I < N; I++) {
        AUX = A[I];  // Guardar el valor actual en AUX
        IZQ = 0;     // El límite izquierdo comienza en 0
        DER = I - 1; // El límite derecho es el índice del elemento anterior a I

        // Buscar la posición correcta con búsqueda binaria
        while (IZQ <= DER) {
            M = (IZQ + DER) / 2;  // Calcular la mitad

            if (AUX < A[M]) {
                DER = M - 1;  // Ajustar límite derecho
            } else {
                IZQ = M + 1;  // Ajustar límite izquierdo
            }
        }

        // Desplazar los elementos para hacer espacio para AUX
        for (J = I - 1; J >= IZQ; J--) {
            A[J + 1] = A[J];
        }

        A[IZQ] = AUX;  // Insertar AUX en la posición correcta
    }
        MostrarArreglo();
        cout << endl;
}

void SeleccionDirecta( int A[], int N )
{
    int MENOR, K;

    // Repetir con I desde 0 hasta N-2 (ajustado para trabajar con índices en 0)
    for (int I = 0; I < N - 1; I++) {
        MENOR = A[I];
        K = I;

        // Repetir con J desde I+1 hasta N-1
        for (int J = I + 1; J < N; J++) {
            if (A[J] < MENOR) {
                MENOR = A[J];
                K = J;
            }
        }

        // Intercambiar A[I] y A[K] si K cambió
        if (K != I) {
            int AUX = A[I];
            A[I] = A[K];
            A[K] = AUX;
        }
    }
    MostrarArreglo();
    system ("pause");
}

void Shell( int A[], int N )
{
    int INT = N + 1;
    do {
        INT = INT / 2;
        bool BAND = true;
        while (BAND) {
            BAND = false;
            int I = 0;
            while ((I + INT) < N) {
                if (A[I] > A[I + INT]) {
                    int AUX = A[I];
                    A[I] = A[I + INT];
                    A[I + INT] = AUX;
                    BAND = true;
                }
                I++;
            }
        }
    } while (INT > 1);
    MostrarArreglo();
    system ("pause");
}

void QuickSort( int A[], int INI, int FIN )
{
     int IZQ = INI, DER = FIN, POS = INI;
    bool BAND = true;

    // Paso 2: Mientras (BAND = VERDADERO) Repetir
    while (BAND) {
        BAND = false;

        // 2.1 Mientras ((A[POS] ≤ A[DER]) y (POS ≠ DER)) Repetir
        while ((A[POS] <= A[DER]) && (POS != DER)) {
            DER--;  // Hacer DER <- DER - 1
        }

        // 2.3 Si (POS ≠ DER) entonces
        if (POS != DER) {
            int AUX = A[POS];  // Hacer AUX <- A[POS]
            A[POS] = A[DER];   // A[POS] <- A[DER]
            A[DER] = AUX;      // A[DER] <- AUX
            POS = DER;         // POS <- DER

            // 2.3.1 Mientras ((A[POS] ≥ A[IZQ]) y (POS ≠ IZQ)) Repetir
            while ((A[POS] >= A[IZQ]) && (POS != IZQ)) {
                IZQ++;  // Hacer IZQ <- IZQ + 1
            }

            // 2.3.3 Si (POS ≠ IZQ) entonces
            if (POS != IZQ) {
                BAND = true;
                AUX = A[POS];  // Hacer AUX <- A[POS]
                A[POS] = A[IZQ];  // A[POS] <- A[IZQ]
                A[IZQ] = AUX;     // A[IZQ] <- AUX
                POS = IZQ;        // POS <- IZQ
            }
        }
    }

    // Paso 6: Condiciones para llamadas recursivas
    if ((POS - 1) > INI) {
        QuickSort(A, INI, POS - 1);  // Llamada recursiva
    }
    if ((POS + 1) < FIN) {
        QuickSort(A, POS + 1, FIN);  // Llamada recursiva
    }
}

void InsertaHeap ( int A[], int N )
{
    for (int i = 1; i < N; i++) {
        int k = i;
        bool BAND = true;

        while (k > 0 && BAND) {
            BAND = false;
            int parent = (k - 1) / 2;  // Índice del padre

            if (A[k] > A[parent]) {  // Comparar con el padre
                // Intercambiar A[k] con A[parent]
                int AUX = A[parent];
                A[parent] = A[k];
                A[k] = AUX;

                k = parent;
                BAND = true;
            }
        }
    }
}

void EliminaHeap ( int A[], int N )
{
    int AUX = A[0];
    A[0] = A[N - 1];
    A[N - 1] = AUX;

    N--;  // Reducir el tamaño del montón
    int k = 0;
    bool BAND = true;

    while (2 * k + 1 < N && BAND) {
        BAND = false;
        int hijo_izq = 2 * k + 1;
        int hijo_der = 2 * k + 2;
        int mayor = hijo_izq;

        // Verificar si el hijo derecho es mayor que el izquierdo
        if (hijo_der < N && A[hijo_der] > A[hijo_izq]) {
            mayor = hijo_der;
        }

        if (A[mayor] > A[k]) {
            // Intercambiar A[k] con A[mayor]
            AUX = A[k];
            A[k] = A[mayor];
            A[mayor] = AUX;

            k = mayor;
            BAND = true;
        }
    }
}

void HeapSort( int A[], int N )
{
    InsertaHeap ( A, N );
    for (int i = N; i > 1; i--) EliminaHeap ( A, i );
    MostrarArreglo();
    system("pause");
}

void intercalar(int arr[], int inicio, int medio, int fin) {
    int n1 = medio - inicio + 1;
    int n2 = fin - medio;

    int izquierda[n1], derecha[n2];

    for (int i = 0; i < n1; i++)
        izquierda[i] = arr[inicio + i];
    for (int j = 0; j < n2; j++)
        derecha[j] = arr[medio + 1 + j];

    int i = 0, j = 0, k = inicio;
    while (i < n1 && j < n2) {
        if (izquierda[i] <= derecha[j]) {
            arr[k] = izquierda[i];
            i++;
        } else {
            arr[k] = derecha[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = izquierda[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = derecha[j];
        j++;
        k++;
    }
}

void Merge( int A[], int Izq, int Der)
{
    if (Izq < Der) {
        int medio = Izq + (Der - Izq) / 2;

        Merge(A, Izq, medio);
        Merge(A, medio + 1, Der);

        intercalar(A, Izq, medio, Der);
    }
}


// Implementación de Métodos de Búsqueda
int BusqSec( int A[], int N, int X )
{
  int i=0;

  while ( (i<N) && (A[i]!= X) ) 
    i++;

  if (i>=N)  
     return 0;
  else 
     return i+1;    
}

int BusqBin( int V[], int N, int X )
{

    int IZQ = 0, DER = N - 1;
    bool BAN = false;
    int CEN;

    while (IZQ <= DER && !BAN) {
        CEN = IZQ + (DER - IZQ) / 2;  // Calcula posición central

        if (X == V[CEN]) {
            BAN = true;  // Elemento encontrado
        } else {
            if (X > V[CEN]) {
                IZQ = CEN + 1;  // Busca en la mitad derecha
            } else {
                DER = CEN - 1;  // Busca en la mitad izquierda
            }
        }
    }

    if (BAN) {
        return CEN +1;
    } else {
        return 0;
    }
}

int Hash(int A[], int N, int K)
{
    const int VACIO = -1;
    int D = K % N;  // Hacer D ← H(K), genera dirección
    int DX = D;     // Inicializar DX

    // Si ((V[DX] ≠ VACIO) y (V[DX] = K)) entonces
    if (A[DX] != VACIO && A[DX] == K) {
        cout << "La información está en la posición " << D << endl;
        return D; // Fin
    }

    // Si no
    DX = D + 1;  // Hacer DX ← D + 1
    // Mientras (DX ≠ N) y (V[DX] ≠ VACIO) y (V[DX] ≠ K) y (DX ≠ D) Repetir
    while ((DX != N) && (A[DX] != VACIO) && (A[DX] != K) && (DX != D)) {
        DX = DX + 1;  // Hacer DX ← DX + 1

        // Si (DX = N + 1) entonces
        if (DX == N) {
            DX = 0;  // Hacer DX ← 1
        }
    }

    // Si ((V[DX] = VACIO) o (DX = D)) entonces
    if (A[DX] == VACIO || DX == D) {
        return 0;  // Fin
    }

    // Si no
    return DX+1; // Fin
}

void MenuPrincipal()
{ // Variables locales
  char Opc;   // Variable auxiliar Opcion
  int X, Y;
  time_t Inicio, Final;

  do {
     system("cls");
     cout << "\n\t\t *powered by ImNotLeo :D\n" << endl;
     cout << "\t**** Metodos de Ordenacion y Busqueda. " << endl;
     cout << "1. Introducir valores Usuario. " << endl;
     cout << "2. Introducir valores aleatoriamente. " << endl;
     cout << "3. Mostrar Arreglo. " << endl << endl;

     cout << "\t**** Algoritmos de Ordenacion. " << endl;
     cout << "4. Por Intercambio Directo (Burbuja). " << endl;
     cout << "5. Metodo de la Sacudida (ShakerSort). " << endl;
     cout << "6. Metodo de Insercion Directa. " << endl;
     cout << "7. Metodo de Insercion Binaria. " << endl;
     cout << "8. Metodo de Seleccion Directa. " << endl;
     cout << "9. Shell. " << endl;
     cout << "A. QuickSort. " << endl;
     cout << "B. Monticulo (HeapSort). " << endl;
     cout << "C. Intercalacion de archivos (Merge). " << endl << endl;

     cout << "\t**** Algoritmos de Busqueda. " << endl;
     cout << "D. Busqueda Secuencia." << endl;
     cout << "E. Busqueda Binaria." << endl;
     cout << "F. Hash." << endl;
     cout << "0. Salir " << endl << endl;
     cout << "Opcion: "; cin >> Opc;

     switch (Opc) {
       case '1': IngresarUsuario(); break;
       case '2': IngresarAleatorio(); break;
       case '3': MostrarArreglo(); system("Pause"); break;
       //----------------------------------------------
       case '4': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; BubbleSort( A, N ); break;
       case '5': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; ShakerSort( A, N ); break;
       case '6': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; InsercionDirecta( A, N ); break;

       case '7': // Inserción Binaria 
                 Inicio= time(NULL); // Tiempo inicial o actual
                 cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; InsercionBinaria( A, N ); // Llamada al Método de Ordenación
                 Final= time(NULL);    // Tiempo final o actual

                 MostrarTiempo( Inicio, Final ); // Muestra tiempo transcurrido
                 break;

       case '8': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; SeleccionDirecta( A, N ); break;
       case '9': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; Shell( A, N ); break;
       case 'A': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; QuickSort( A, 0, MAX-1 ); MostrarArreglo(); system ("pause"); break;
       case 'B': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; HeapSort( A, N ); break;
       case 'C': cout << "\n\tArreglo Original: "; MostrarArreglo(); cout << endl; Merge( A, 0, MAX-1 ); MostrarArreglo(); system ("pause"); break;
       //----------------------------------------------
       case 'D': // Método de Búsqueda Secuencial
                 cout << "Escriba valor a buscar: ";
                 cin >> X;

                 Inicio= time(NULL); // Tiempo inicial o actual
                 Y= BusqSec( A, N, X ); // llamada al Método de Busqueda
                 Final= time(NULL);    // Tiempo final o actual
                    if (Y == 0) cout << "\n\tLa informacion no esta en el arreglo. \n";
                    else printf("\n\tLa posicion encontrada fue %i \n", Y); 
                 MostrarTiempo( Inicio, Final ); // Muestra tiempo transcurrido
                 break;      

       case 'E': // Método de Búsqueda Binaria
                 cout << "Escriba valor a buscar: ";
                 cin >> X;
                 Merge( A, 0, MAX-1 );
                 cout << "\n\tArreglo Original: "; MostrarArreglo();
                 Inicio= time(NULL); // Tiempo inicial o actual
                 Y= BusqBin( A, N, X ); // llamada al Método de Busqueda
                 Final= time(NULL);    // Tiempo final o actual
                    if (Y == 0) cout << "\n\tLa informacion no esta en el arreglo. \n";
                    else printf("\n\tLa posicion encontrada fue %i \n", Y); 
                 MostrarTiempo( Inicio, Final ); // Muestra tiempo transcurrido
                 break;

       case 'F': // Método de Hash
                 cout << "Escriba valor a buscar: ";
                 cin >> X;

                 Inicio= time(NULL); // Tiempo inicial o actual
                 Y= Hash( A, N, X ); // llamada al Método de Busqueda
                 Final= time(NULL);    // Tiempo final o actual
                    if (Y == 0) cout << "\n\tLa informacion no esta en el arreglo. \n";
                    else printf("\n\tLa posicion encontrada fue %i \n", Y); 
                 MostrarTiempo( Inicio, Final ); // Muestra tiempo transcurrido
                 break;
     };

  } while (Opc!='0');
    system("cls");
    cout << "\n\n\tGracias por usar mi programa, puedes usarlo cuando gustes!\n" << endl;
    cout << "\t\t\t\tby ImNot Leo :D\n\n" << endl;
};

// Programa o función principal del programa
int main()
{
  MenuPrincipal();
  return 0;
};