/*Quisiera encontrador un metodos mas eficiente de usar los algoritmos conocidos en las listas enlazadas simples, por ejemplo la busqueda binaria.
En el codigo implemente insercion y seleccion pero creo que pueden ser mas eficiente.
*/
#include <iostream>
#include <conio.h>
#include <stdlib.h>

using namespace std;

struct Nodo{
       int valor;       
       struct Nodo *sgte;
};

typedef struct Nodo *Tlista;

Tlista Inicio, Fin;

void generarLista( Tlista &Inicio, Tlista &Fin, int valor ) {
     Tlista q, t;
     
         q = new(struct Nodo);
         q->valor = valor;
         
         if(Inicio==NULL){
              q->sgte = Inicio;
              Inicio  = q;
              Fin     = q;         
         }
         else{
              q->sgte   = Fin->sgte;
              Fin->sgte = q;
              Fin       = q;
         }

}

void reportarLista(Tlista Inicio){
     while(Inicio != NULL){
          cout <<"  " << Inicio->valor ;
          Inicio = Inicio->sgte;
     }
}

void ordenarLista(Tlista lista){
     Tlista actual , siguiente;
     int t;
     
     actual = lista;
     while(actual->sgte != NULL)
     {
          siguiente = actual->sgte;
         
          while(siguiente!=NULL)
          {
               if(actual->valor > siguiente->valor)
               {
                    t = siguiente->valor;
                    siguiente->valor = actual->valor;
                    actual->valor = t;         
               }
               siguiente = siguiente->sgte;                   
          }   
          actual = actual->sgte;
          siguiente = actual->sgte;
           
     }
     
     cout<<"\n\n\tLista ordenada..."<<endl;
}
void ordenamientoSeleccion(Tlista lista){
   Tlista actual, siguiente;   int t;
   actual = lista; int minimo;
   Tlista min=lista;
   
   while(actual->sgte!=NULL){
      minimo=actual->valor;
      min=actual;
      siguiente=actual->sgte;
      
      while(siguiente!=NULL){
         
         if(siguiente->valor < minimo){
         minimo = siguiente->valor;
         min = siguiente;
         }
         
         siguiente=siguiente->sgte;      
      }
      
      t= actual->valor;
      actual->valor=min->valor;
      min->valor=t;
      
      actual=actual->sgte;
      
   }
   
    cout<<"\n\n\tLista ordenada..."<<endl;
   
}

void ordenamientoInsercion(Tlista lista){
   Tlista actual;
   actual = lista; int cont=1,cursor,aux,k;
   
   while(actual!=NULL){
      cursor=cont;       cout<<"\ncursor:"<<cursor<<" ";
      aux=actual->valor;    cout<<"\naux:"<< aux<<" ";
      k = cursor-1;       cout<<"\nk: "<< k<<" ";
      Tlista anterior=lista;
      for(int f=0;f<k-1;f++){
         anterior=anterior->sgte;
      }
                     cout<<"\nAnterior: "<<anterior->valor <<" ";
      while(k>=0 && aux<anterior->valor){
         anterior->sgte->valor=anterior->valor;
         Tlista temp=lista;
         for(int j=0;j<k-2;j++){
            temp=temp->sgte;
         }   
                     cout<<"\nTemp:"<<temp->valor;         
         anterior=temp   ;   
         k--;   
      }
                     cout<<"\n--"<<aux<<endl;
      Tlista temp2 = lista;
      for(int h=0;h<k;h++){
      temp2=temp2->sgte;   
      }
      temp2->valor=aux;
      actual=actual->sgte;
      cont++;   
   }
   cout<<"\n\n\tLista ordenada..."<<endl;
}



void menu()
{
    cout<<"\n\t\tORDENAMIENTO DE UNA LISTA ENLAZADA\n\n";
    cout<<" 1. INGRESAR NUMERO\n";
    cout<<" 2. MOSTRAR NUMEROS\n";
    cout<<" 3. BURBUJA\n";
    cout<<" 4. SELECCION\n";
    cout<<" 5. INSERCION\n";

    cout<<" 0. SALIR\n";
    cout<<" INGRESE OPCION: ";
}

int main()
{
    Inicio = NULL;
    Fin    = NULL;
   
    int op;     
    int num;   
    generarLista( Inicio, Fin, 2 );
    generarLista( Inicio, Fin, 5 );
    generarLista( Inicio, Fin, 3 );
    generarLista( Inicio, Fin, 6 );
    generarLista( Inicio, Fin, 1 );
   
    do
    {
        menu();  cin>> op;
        switch(op)
        {     
            case 1: system("cls");
                 cout<< "\n Valor: "; cin>> num;
                 generarLista( Inicio, Fin, num );
                 reportarLista( Inicio );
            break;

            case 2: system("cls");
                 cout<<"\n\n LISTA:\n\n";
                 reportarLista( Inicio );
            break;
           
            case 3: system("cls");
                 ordenarLista( Inicio );break;
                 
            case 4: system("cls");
             ordenamientoSeleccion(Inicio);break;     
            case 5: system("cls");
            ordenamientoInsercion(Inicio);reportarLista( Inicio );break;   
            default: 
            break;           

        }

        cout<<endl<<endl;

    }while(op!=0);
}