[ Foro de C++ ]
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;
}
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.)