[ Foro de C++ ]

Como ordenarían una lista con el metodo de MERGESORT Y QUICKSORT

29-Feb-2020 22:54
jorge camarena
1 Respuestas

como incluirían el metodo de meergesort y quicksort en mi lista


#include <iostream>
#include <stdlib.h>
using namespace std;

struct nodo{
       int nro;
       struct nodo *sgte;
};


typedef struct nodo *Tlista;

void insertarInicio(Tlista &lista, int valor)
{
    Tlista q;
    q = new(struct nodo);
    q->nro = valor;
    q->sgte = lista;
    lista  = q;
}

void insertarFinal(Tlista &lista, int valor)
{
    Tlista t, q = new(struct nodo);

    q->nro  = valor;
    q->sgte = NULL;

    if(lista==NULL)
    {
        lista = q;
    }
    else
    {
        t = lista;
        while(t->sgte!=NULL)
        {
            t = t->sgte;
        }
        t->sgte = q;
    }

}

int insertarAntesDespues()
{
    int _op, band;
    cout<<endl;
    cout<<"\t 1. Antes de la posicion"<<endl;
    cout<<"\t 2. Despues de la posicion"<<endl;

    cout<<"\n\t Opcion : "; cin>> _op;

    if(_op==1)
        band = -1;
    else
        band = 0;

    return band;
}

void insertarElemento(Tlista &lista, int valor, int pos)
{
    Tlista q, t;
    int i;
    q = new(struct nodo);
    q->nro = valor;

    if(pos==1)
    {
        q->sgte = lista;
        lista = q;
    }
    else
    {
        int x = insertarAntesDespues();
        t = lista;

        for(i=1; t!=NULL; i++)
        {
            if(i==pos+x)
            {
                q->sgte = t->sgte;
                t->sgte = q;
                return;
            }
            t = t->sgte;
        }
    }
    cout<<"   Error...Posicion no encontrada..!"<<endl;
}

void buscarElemento(Tlista lista, int valor)
{
    Tlista q = lista;
    int i = 1, band = 0;

    while(q!=NULL)
    {
        if(q->nro==valor)
        {
            cout<<endl<<" Encontrada en posicion "<< i <<endl;
            band = 1;
        }
        q = q->sgte;
        i++;
    }

    if(band==0)
        cout<<"\n\n Numero no encontrado..!"<< endl;
}

void reportarLista(Tlista lista)
{
     int i = 0;

     while(lista != NULL)
     {
          cout <<' '<< i+1 <<") " << lista->nro << endl;
          lista = lista->sgte;
          i++;
     }
}


void eliminarElemento(Tlista &lista, int valor)
{
    Tlista p, ant;
    p = lista;

    if(lista!=NULL)
    {
        while(p!=NULL)
        {
            if(p->nro==valor)
            {
                if(p==lista)
                    lista = lista->sgte;
                else
                    ant->sgte = p->sgte;

                delete(p);
                return;
            }
            ant = p;
            p = p->sgte;
        }
    }
    else
        cout<<" Lista vacia..!";
}


void Anular(Tlista &lista)
{
   lista=NULL;
}
void Burbuja(Tlista lista){
     Tlista actual , siguiente;
     int t;
     
     actual = lista;
     while(actual->sgte != NULL)
     {
          siguiente = actual->sgte;
         
          while(siguiente!=NULL)
          {
               if(actual->nro > siguiente->nro)
               {
                    t = siguiente->nro;
                    siguiente->nro = actual->nro;
                    actual->nro = t;         
               }
               siguiente = siguiente->sgte;                   
          }   
          actual = actual->sgte;
          siguiente = actual->sgte;
           
     }
     
     cout<<"\n\n\tLista ordenada..."<<endl;
}
void Seleccion(Tlista lista){
   Tlista actual, siguiente;   int t;
   actual = lista; int minimo;
   Tlista min=lista;
   
   while(actual->sgte!=NULL){
      minimo=actual->nro;
      min=actual;
      siguiente=actual->sgte;
      while(siguiente!=NULL){
         if(siguiente->nro < minimo){
         minimo = siguiente->nro;
         min = siguiente;
         }  
         siguiente=siguiente->sgte;      
      }
      t= actual->nro;
      actual->nro=min->nro;
      min->nro=t;
      actual=actual->sgte;
   }
    cout<<"\n\n\tLista ordenada..."<<endl;
}
void Mergesort(Tlista lista){
	
}
void Quicksort(Tlista lista){
	
} 
void menu1()
{
    cout<<"\n\t\tLISTA\n\n";
    cout<<" 1. INSERTAR AL INICIO"<<endl;
    cout<<" 2. INSERTAR AL FINAL"<<endl;
    cout<<" 3. INSERTAR EN UNA POSICION"<<endl;
    cout<<" 4. MOSTRAR LISTA"<<endl;
    cout<<" 5. BUSCAR ELEMENTO"<<endl;
    cout<<" 6. ELIMINAR ELEMENTO"<<endl;
    cout<<" 7. Anular Lista"<<endl;
    cout<<" 8. Ordenar por Burbuja"<<endl;
    cout<<" 9. Ordenar por Seleccion"<<endl;
    cout<<" 10. Ordenar por Mergesort"<<endl;
    cout<<" 11. Ordenar por Quicksort"<<endl;
    cout<<" 12. SALIR"<<endl;

    cout<<"\n INGRESE OPCION: ";
}


int main()
{
    Tlista lista = NULL;
    int op;
    int _dato;
    int pos;


    do
    {
        menu1();  cin>> op;

        switch(op)
        {
            case 1:

                 cout<< "\n NUMERO A INSERTAR: "; cin>> _dato;
                 insertarInicio(lista, _dato);
            break;


            case 2:

                 cout<< "\n NUMERO A INSERTAR: "; cin>> _dato;
                 insertarFinal(lista, _dato );
            break;


            case 3:

                 cout<< "\n NUMERO A INSERTAR: ";cin>> _dato;
                 cout<< " Posicion : ";       cin>> pos;
                 insertarElemento(lista, _dato, pos);
            break;
            case 4:

                 cout << "\n\n MOSTRANDO LISTA\n\n";
                 reportarLista(lista);
            break;
            case 5:

                 cout<<"\n Valor a buscar: "; cin>> _dato;
                 buscarElemento(lista, _dato);
            break;
            case 6:

                cout<<"\n Valor a eliminar: "; cin>> _dato;

                eliminarElemento(lista, _dato);
            break;
            case 7:
                Anular(lista);
                cout<<"La Lista Fue Anulada Exitosamente"<<endl;
                break;
            case 8:
            	Burbuja(lista);
				cout<<"La lista se ordena por Burbuja"<<endl;
				break;
            case 9:
            	Seleccion(lista);
            	cout<<"La lista se ordena por Seleccion"<<endl;
            	break;
            case 10:
            	Mergesort(lista);
            	cout<<"La lista se ordena por Mergesort"<<endl;
            	break;
            case 11:
            	Quicksort(lista);
            	cout<<"La lista se ordena por Quicksort"<<endl;
            	break;
            }

        cout<<endl<<endl;
        system("pause");  system("cls");

    }while(op!=12);


   system("pause");
   return 0;
}


 


01-Mar-2020 23:53
Nacho Cabanes (+84)

Para poder usar un quicksort clásico, y también para mergesort, deberás comenzar por imitar un acceso directo: poder acceder a cada dato por su posición (aunque realmente lo hagas buscando esa posición de forma secuencial, con lo que serán mucho menos rápidos de lo deseables).

Además, tendrás que crear rutinas para intercambiar dos datos cualesquiera, que tampoco es trivial.






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)