# include <iostream>
# include <math.h>
# include <cstdlib>
#include <conio.h>
#define TAM 15
using namespace std;
int opcion=0, A[100],n, c, i, j,Aux, k; 
int izq,der,pivote,aux, tam;
int a[TAM], busca, temp, bajo, alto, central;
float SUMAR;
void Busqueda();
void Burbuja();
void imprimir();
void generar();
void TAREA1();
void Tarea2();
int main()
{
do
{
cout << "    M E N U   P R I N C I P A L   D E   M A T R I C E S\n "<< endl;
cout << " ----------------------------"<< endl;
cout << " [1] BUSQUEDA SECUENCIAL \n "<< endl;
cout << " [2] ORDENAMIENTO DE BURBUJA \n "<< endl;
cout << " [3] TAREA(CLASE) ORDENAMIENTO POR QUICKSORT\n "<< endl;
cout << " [4] TAREA DE BUSQUEDA DE SECUENCIAL Y BURBUJA\n "<< endl;
cout << " [5] TAREA DE ORDENAMIENTO\n "<< endl;
cout << endl;

cout << "\n  INGRESE UNA OPCION <0> : "; cin>>opcion;
cout << " ----------------------------"<< endl;

switch (opcion)
{
   case 1:
   {
       cout << " [1] BUSQUEDA SECUENCIAL "<< endl;
       cout << " ----------------------------"<< endl;
       Busqueda();
       cout << " ----------------------------"<< endl;
       break;
   }
   case 2:
   {
       cout << " [2] ORDENAMIENTO DE BURBUJA  "<< endl;
       cout << " ----------------------------"<< endl;
       Burbuja();
       cout << "\n ----------------------------"<< endl;
       break;
   }
   case 3:
   {
       cout << " [3] TAREA(CLASE) ORDENAMIENTO POR QUICKSORT "<< endl;
       cout << " ----------------------------"<< endl;
       generar();
          cout << " ----------------------------"<< endl;
       break;
   }
   case 4:
   {
       cout << " [4] TAREA DE BUSQUEDA DE SECUENCIAL Y BURBUJA\n "<< endl;
       cout << " ----------------------------"<< endl;
       TAREA1();
          cout << " ----------------------------"<< endl;
          break;
   }
   case 5:
   {
       cout << " [5] TAREA DE ORDENAMIENTO\n "<< endl;
       cout << " ----------------------------"<< endl;
       Tarea2();
          cout << " ----------------------------"<< endl;
          break;
   }
       
}    
} while (opcion!=0);
   return 0;    
}

void Busqueda()
{
   for (i=1; i<=20; i++)
   {
       A[i]= rand()%20;
       cout<<"A["<<i<<"]="<<A[i]<<endl;
   }
   cout<<"Ingrese el elemento a buscar "; cin>>n;
   cout<<"cuenta las veces que se encuentra el elemento \n";
   
   for (i=1; i<=20; i++)
   {
       if (A[i]== n)
       {
       cout<<"A["<<i<<"]="<<A[i]<<endl;
       c=c+1;
       }
   }
   cout<<"\n se repitio: "<<c<<" veces "<<n<<endl;
}

void Burbuja()
{
   for (i=1; i<=20; i++)
   {
       A[i]= rand()%20;
       cout<<"A["<<i<<"]="<<A[i]<<endl;
   }
   cout<<"Ordenando el vector A[20] "<<endl;
   for (i=1; i<=20; i++)
   {
       for (j=1; j<=19; j++)
       {
          if(A[j]>A[j+1])
          {
              Aux = A[j];
              A[j]=A[j+1];
              A[j+1]=Aux;
          }
       }
   }
   
   for (i=1; i<=20; i++)
   {
       cout<<"A["<<i<<"]="<<A[i]<<endl;
   }
}
void imprimir(int A[], int tam);

void qs(int A [],int inicio, int fin){
    
    izq = inicio;
    der = fin;
    pivote = A[(izq+der)/2];

    do{
        while(A[izq] < pivote && izq<fin){
            izq++;
        }

        while(A[der] > pivote && der > inicio){
            der --;
        }

        if(izq <= der){
            aux = A[izq];
            A[izq] = A[der];
            A[der] = aux;
            izq++;
            der--;
        }

    }while(izq <= der);

    if(inicio <= der){
        qs(A,inicio,der);
    }

    if(fin > izq){
        qs(A,izq,fin);
    }

}

void generar(){

   for (i=1; i<=20; i++)
   {
       A[i]= rand()%20;
   }
    int A[i];
    int tam = sizeof(A)/sizeof(A[0]);

    printf("\n Arreglo en desorden: ");
    imprimir(A,tam);

    qs(A,0,tam-1);

    printf("\n Arreglo en orden: ");
    imprimir(A,tam);

    
}

void imprimir(int A[], int tam){
    int i;
    for(i=0;i<tam;i++){
        printf(" %d ",A[i]);
    }
    printf("\n");
}
void TAREA1()
{
   printf("Llenando el arreglo con numeros aleatorios\n");
    rand(); //Inicializa el generador de aleatorios
    for (int i=0; i<TAM; i++)
        A[i]=rand()%10;
            //Implementacion de Ordenamiento por burbuja de menor a mayor
            printf ("Ordenando arreglo...\n");
            for (int j=1; j <= TAM; j++)
                for (i=0; i<TAM-1; i++) 
                    if (A[i] > A[i+1]){ 
                        temp = A[i];
                        A[i] = A[i+1];
                        A[i+1] = temp;
                    }
    
            //Implementacion de busqueda binaria 
            printf ("\nIntroduce un numero a buscar: "); 
            scanf ("%d", &busca);
    
            bajo = 0; 
            alto = TAM-1; 
            central = (bajo+alto)/2;
            while (bajo < alto && busca != a[central]){ 
                if(busca > a[central]) 
                    bajo = central+1;
                else
                    alto = central-1;
                central=(bajo+alto)/2;
            }
    
            if (busca == a[central])
                printf("\n%d encontrado en posicion %d", busca, central);
            else
                printf("\n%d no existe", busca);
            printf ("\n\nEl arreglo ordenado era\n\n"); 
            for (i=0; i< TAM; i++)
                printf ("%d \n", A[i]); 
}
void Tarea2()
{
   cout << "Cantidad de numeros que desea Ingresar: ";
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cout << "Ingrese numero " << i + 1 << " : ";
        cin >> A[i];
    }
 
    for (i = 1; i < n; i++)
    {
        for (j = 0; j < n - i; j++)
        {
            if (A[j] > A[j + 1])
            {
                k = A[j + 1];
                A[j + 1] = A[j];
                A[j] = k;
            }
        }
    }
    cout << " ----------------------------"<< endl;
   cout << "ORDENANDO"<< endl;
   cout << " ----------------------------"<< endl;
    for (i = 0; i < n; i++)
    {
        cout << A[i] << endl;
    }
    cin.ignore();
}