Listas Enlazadas Simples Metodos de ordenamiento

[david.albornoz]

/*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);
}

[Beginner Web]

Sii quieres usar busqueda binaria en listas debes recordar que la busqueda binaria funciona solamente en estructuras lineales ordenados, en listas podrias utilizar una clave para señalar el orden, luego ordenarlas con bubblesort en caso de haberlas insertado desordenadamente y recien hacerle una busqueda binaria a esa lista