Ordenamiento de listas por seleccion

Iniciado por Beginner Web, 1 Septiembre 2018, 08:22 AM

0 Miembros y 1 Visitante están viendo este tema.

Beginner Web

Hola picolos bambinos, alguien me podria decir porque mi metodo de ordenacion seleccion en listas simplemente enlazadas no funciona?

void ordenar_lista(pnodo &lista)//Este es el modulo ->

Código (cpp) [Seleccionar]
#include <iostream>
#include <stdlib.h>

using namespace std;

typedef struct tnodo *pnodo;
typedef struct tnodo{
int dato;
pnodo sig;
};

void inicia(pnodo &lista);
void crear(pnodo &nuevo);
void agregar_final(pnodo &lista, pnodo nuevo);
void ordenar_lista(pnodo &lista);
void mostrar(pnodo lista);

int main()
{
pnodo milista, nuevo;
int opcion;
inicia(milista);
do{
system("cls");
cout << "1. Iniciar lista" << endl;
cout << "2. Agregar elemento" << endl;
cout << "3. Ordenar lista" << endl;
cout << "4. Mostrar lista" << endl;
cout << "5. Salir" << endl;
cin >> opcion;
switch(opcion){
case 1: inicia(milista); break;
case 2: crear(nuevo); if(nuevo!=NULL){agregar_final(milista,nuevo);}; break;
case 3: ordenar_lista(milista); break;
case 4: cout << "*** LISTA ***" << endl; mostrar(milista); break;
case 5: cout << "FIN DEL  PROGRAMA" << endl; break;
default: cout << "Opcion incorrecta" << endl;
}
system("pause");
}while(opcion!=5);
}

void inicia(pnodo &lista)
{
lista=NULL;
}

void crear(pnodo &nuevo)
{
nuevo=new tnodo;
if(nuevo!=NULL){
cout << "Ingrese valor: "; cin >> nuevo->dato;
nuevo->sig=NULL;
}
else{
cout << "MEMORIA INSUFICIENTE" << endl;
}
}

void agregar_final(pnodo &lista, pnodo nuevo)
{
pnodo i;
if(lista==NULL){
lista=nuevo;
}
else{
for(i=lista;i->sig!=NULL;i=i->sig);
i->sig=nuevo;
}
}

void ordenar_lista(pnodo &lista)
{
pnodo i, j, min;
int aux;
for(i=lista;i->sig!=NULL;i=i->sig){
min=i;
for(j=lista;j->sig!=NULL;j=j->sig){
j=i->sig;
if(j->dato<i->dato){
min->dato=j->dato;
min->sig=j->sig;
}
}
aux=i->dato;
i->dato=min->dato;
min->dato=aux;
}
}

void mostrar(pnodo lista)
{
pnodo i;
if(lista!=NULL){
for(i=lista;i!=NULL;i=i->sig){
cout << "Nodo: " << i->dato << endl;
}
cout << endl;
}
else{
cout << "LISTA VACIA" << endl;
}
}





No se que pasa no me ordena como yo quiero, esto es lo que pude lograr hasta ahora
Código (cpp) [Seleccionar]
void ordenar_lista(pnodo &lista)
{
pnodo i, j, min;
int aux;
for(i=lista;i->sig!=NULL;i=i->sig){
min=i;
for(j=i->sig;j->sig!=NULL;j=j->sig){
if(min->dato>j->dato){
min=j;
}
}
if(min!=i){
aux=i->dato;
   i->dato=j->dato;
   j->dato=aux;
}
}
}




Mod: Prohibido el doble o triple post. Usa el botón "Modificar".
7w7

Serapis

#1
mmmm... si lo que te falla es el algortimo de ordenamiento, no es preciso poner el resto dle código... cuando el código es largo, y la descripción del problema vago, ahuyenta a cualquiera que tuviera intención de ayudarte... cíñete a algo específico, y no te faltará ayuda...

(ok, acabo de ver que lo has abreviado, en otro mensaje posterior, pero ...
los comentarios aquí se refieren al código de dicha función en tu primer mensaje, de este último, no he mirado, yo le di a responder esta mañana, pero me tuve que ir, y ahora al volver lo he terminado, no me apetece corregirlo (solo el parrafo que iba aquí)


   
Tu error reside en el bucle interno al completo.
Primero en:
Código (cpp) [Seleccionar]

for(j=lista;j->sig!=NULL;j=j->sig){
j=i->sig;

Es decir en el bucle interno, con cada iteración el nodo de dicho bucle es siempre el siguiente al del nodo del bucle externo, es decir no cambia en todo el bucle interno.... antes del bucle debes asignarlo
y dentro del bucle podrías iterarlo, sin embargo es algo que ya le has indicado al bucle que lo haga expresamente por tí, en la parte del avance del bucle (incremento, dirección del bucle: j=j->sig)

...y luego también está mal, la comparación...
parece tonta, aunque encuentres uno menor, tu siempre lo comparas con el valor del primer ítem, parece incapaz de 'aprender'
cambia esto:
Código (cpp) [Seleccionar]

                       if(j->dato < i->dato){
min->dato=j->dato;
min->sig=j->sig;
                       }

por esto (tienes min... que pasa a ser el menor, pués en lo siguiente debes buscar uno menor que el recién hallado).
Y también carece de sentido, ir cambiando los datos de cada nodo... Selección intercambia únicamente el menor hallado (en el bucle interno), por el actual en la posición de avance (del bucle externo)...
Código (cpp) [Seleccionar]

                       if(j->dato < min->dato){
min=j;
                       }

      
para que el bucle interno te quede finalmente así:
Código (cpp) [Seleccionar]

              for(j=i->sig;j->sig!=NULL;j=j->sig){
                       if(j->dato < min->dato){
min=j;
                       }
             }

...vamos que fallando el bucle interno te ha fallado todo, excepto intercambiar los datos.
Revisa que no te dé desbordamiento.



Te pongo un pseudocódigo más elegante, que espero que te resulte fácil de entender y sobre todo ameno...

En el algoritmo de ordenamiento por selección, se localiza el menor (entre los que aún queden sin ordenar), y luego se intercambia por el primero no ordenado aún.

Nota que son los comentarios lo que 'profusan el texto', por lo demás necesarios para que los que están aprendiendo, logren entenderlo bien... si los retiras el código resulta muy breve.

entero i, j, final
entero min, aux //supongamos que min es un valor entero, que no lo sé, podría incluso ser un string.
nodo n, m, tmp  // necesitaremos 3 nodos...
// n es el nodo siendo examinado en el bucle externo.
// tmp es el nodo siendo examinado en el bucle interno.
// m es el nodo que contiene el valor menor hallado hasta el momento.

final = tamaño de la lista-1
n= lista  // el primer nodo de la lista.

// vamos a marcar el recorrido de los bucles con enteros,
// cuando te funcione y lo tengas claro, puedes modificarlo para que sea con nodos.

// el último elemento, no precisa ser buscado...
// cuando se ordenen los previos, el que queda es el mayor, sí o sí, de ahí el -1
bucle i desde 0 hasta final-1 (incrementos de 1)
    // tomamos el menor aún no ordenado. Empezando por el primero
    min = n.dato  // usamos 'min' por velocidad, y claridad...
    tmp = n  // el primero para el bucle interno (nada más iniciar el bucle, saltamos al siguiente).
    m = n  // ahora este es el menor a superar
   
    // bucle para buscar el menor a partir del 'i'ésimo
    //este bucle toma el siguiente y termina uno más allá que el bucle externo.
    bucle j = desde i+1 hasta final (incrementos de 1)  
        tmp= tmp.siguiente  
        // el bucle interno, siempre empieza comparando con el siguiente al índice siendo ordenado
        Si (tmp.dato < min)
            m = tmp  //recordamos el nodo menor,  ahora este es el menor a superar
            min = m.dato    // tomamos su valor (para seguir comparando)            
        fin si
    fin bucle

    // ahora el intercambio n x m  (el del bucle externo, por el que contiene el valor menor)
    //   basta cambiar el dato (si el nodo sólo tiene como miembros a 'dato' y 'siguiente'
    //   pero... si tuviere más o se cambian todos los que proceda o
    //   se intercambian los nodos entre si al completo, excepto las referencias a otros nodos
    //     que deberían mantenerse 'siguiente', 'anterior', etc...)
    aux = n.dato
    n.dato = min
    m.dato = aux

    n = n.siguiente  
fin bucle


No he mirado el resto del código... si declaras que te falla el freno, carece de sentido mirar el motor, etc...

p.d.: Alineación de comentaros para que no exija scroll horizontal...

Beginner Web

#2
Código (cpp) [Seleccionar]
void ordenar_lista(pnodo &lista)
{
pnodo i, j, min;
int aux;
for(i=lista;i->sig!=NULL;i=i->sig){
min=i;
for(j=i->sig;j!=NULL;j=j->sig){//Esto no entiendo
if(j->dato<min->dato){
min=j;
}
}
if(min!=i){
aux=min->dato;
   min->dato=i->dato;
   i->dato=aux;
}
}
}


Datos de entrada:
9
8
6
4
2
1
Datos de salida
1
2
4
6
8
9




Perdon me mareo

Código (cpp) [Seleccionar]
void ordenar_lista(pnodo &lista)
{
pnodo i, j, min;
int aux;
for(i=lista;i->sig!=NULL;i=i->sig){
min=i;
for(j=i->sig;j!=NULL;j=j->sig){//Esto no entiendo
if(j->dato<min->dato){
min=j;
}
}
if(min!=i){
aux=i->dato;
   i->dato=min->dato;
   min->dato=aux;
}
}
}




Mod: Prohibido el doble o triple post. Usa el botón "Modificar".
7w7