#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    int opcion;
    {
    cout<<"******************menu************* :  \n";
    cout<<"1) metodo burbuja:  \n";
    cout<<"2) metodo por seleccion\n";
    cout<<"3) metodo insersion  \n";
    cout<<"4) metodo shell  \n";
    cout<<"5) metodo quick sort \n";
    cin>>opcion;
    switch(opcion)
     {
             case 1:
      {
          int n,aux;
          cout<<"ingrese la cantidad de numeros:"; cin>>n;
          
          int V[n];
          //LLENAR MI VECTOR
          for (int i=0;i<n;i++){
              cout<<"numero" <<i+1<<"=";
              cin>>V[i];
          }
          
          //ORDENAR
          
          for(int i=0;i<n;i++){
              for(int j=i+1;j<n;j++){
                if(V[j]<V[i]){
                   aux=V[i];
                     V[i]=V[j];
                     V[j]=aux;
          }
       }
     }
    
     cout<<"elementos ordenados:"<<endl;
     for(int i=0; i<n; i++){
     cout<<V[i]<<endl;
    }
    
   }

     
     case 2:
         
      {
          {
             int n;
         cout<<"ingrese el numero de elementos "<<endl;
        cin>>n;
         int a[n];
       for(int i=0;i<n;i++)
    {
        cout<<"Ingrese valores "<<(i+1)<<" del arreglo"<<endl;
        cin>>a[i];
    }
   Seleccion(a , n);
   Imprimir(a , n);
}
void Seleccion(int a[] ,  int n)
{
    //Variables a utilizar
    int k , menor , i , j;
    for(i=0;i<n;i++)
    {
        menor=a[i];
        k=i;
         for(j=i+1;j<n;j++)
         {
             if(a[j]<menor)
             {
                 menor = a[j];
                 k=j;
             }
         }
         a[k]=a[i];
         a[i]=menor;
    }
  }
    void Imprimir(int a[] , int n)
{
    cout<<"EL orden correpto es "<<endl;
     
    for(int i=0;i<n;i++)
        cout<<"[ "<<a[i]<<" ]";
             
           }
 }
           

    case 3:
        {

            {
     cout<<"Numeros Ordenados de Menor a Mayor"<<endl;
    for(int i=0;i<n;i++)
        cout<<"[ "<<a[i]<<" ]";
}
void Insercion(int a[] , int n)
{
    int i,k,aux;
    for(i=0;i<=n-1;i++)
    {
        aux=a[i];
        k=i-1;
        while((k>=0) && (aux<a[k]))
        {
            a[k+1]=a[k];
            k=k-1;
        }
        a[k+1]=aux;
    }
}
int main()
{
    int n;
    cout<<"ingrese el numero de elementos"<<endl;
    cin>>n;
    int num[n];
    for(int i=0;i<n;i++)
    {
        cout<<"Ingrese el numero "<<(i+1)<<endl;
        cin>>num[i];
    }
    Insercion(num,n);
    Imprimir(num,n);

    return 0;
}
    
}
    case 4:
        {
        
        {
        int total;
    cout<<"ingrese el numero de elementos"<<endl;
    cin>>total;
    int num[total];
    for(int i=0;i<total;i++)
    {
        cout<<"Ingrese el numero para la posicion [ "<<(i+1)<<" ] del arreglo"<<endl;
        cin>>num[i];
    }
    Shell(num,total);
}
void Shell(int a[] , int n)
{
    int ints,i,aux;
    bool band;
    ints=n;
    while(ints>1)
    {
        ints=(ints/2);
        band=true;

        while(band==true)
        {
            band=false;
            i=0;
            while((i+ints)<=n)
                {
                    if(a[i]>a[i+ints])
                    {
                        aux=a[i];
                        a[i]=a[i+ints];
                        a[i+ints]=aux;
                        band=true;
                    }
                i++;
         Imprimir(a,n);

                }
        }
    }
}
void Imprimir(int a[] , int n)
{
    cout<<"Numeros del arreglo ordenandos de Menor a Mayor"<<endl;

    for(int i=0;i<n;i++)
        cout<<"[ "<<a[i]<<" ]";

}    
        }
        
    case 5:
        {
        
        {
        int n ;
    cout<<"IIIEE-2\n\n\n ";
    cout<<"ingrese el numero de elementos "<<endl;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cout<<"Ingresa el elemento numero "<<i+1<<" : "<<endl;
        cin>>a[i];
    }
    QuickSort(a,n);
    Imprimir(a,n);
}
void QuickSort(int a[] , int n)
{
    int tope, ini, fin , pos;
            int may[MAX],menor[MAX];
            tope=0;
            menor[tope]=0;
            may[tope]=n-1;
            while(tope>=0)
            {
                ini = menor[tope];
                fin = may[tope];
                tope--;
            int izq,der,aux;
            bool band;
            izq=ini;
            der=fin;
            pos=ini;
            band=true;
            while(band==true)
            {
                while((a[pos]<a[der]) && ( pos!=der ))
                    der--;
                if(pos==der)
                    band=false;
                else
                {
                    aux=a[pos];
                    a[pos]=a[der];
                    a[der]=aux;
                    pos=der;
                }
                while((a[pos]>a[izq]) && ( pos!=izq ))
                    izq++;

                 if(pos==izq)
                    band=false;
                else
                {
                    aux=a[pos];
                    a[pos]=a[izq];
                    a[izq]=aux;
                    pos=izq;
                }
            }
                if(ini<=(pos-1))
                {
                    tope++;
                    menor[tope]=ini;
                    may[tope]=pos-1;
                }
                if(fin>=(pos+1))
                {
                    tope++;
                    menor[tope]=pos+1;
                    may[tope]=fin;
                }
            }
}
void Imprimir(int a[] , int n){
    cout<<"Elementos Ordenados"<<endl;
    for(int i =0 ;i<n;i++){
        cout<<"["<<a[i]<<"]";
        
    }
}    
        }
          }        
    }
}