not succesfull sorting a linked list

hi.
im learning know data structures, im trying to sort a linked list with the bubblesort method. but i have 2 days trying to makit work but it dont works, if i exchange the data betwen the nodes i can sort the list, but i want to sort it exchanging and redirectioning the pointers,
any idea how to do that?? or link where i can analize the code in c++?, please must be in c++ because i dont know c.

the code should not be stl because im learnig from a book and i has not study that chapter yet.

thanks in advance
and please excuse my english

btw. i understand the bubblesort and can sort an array without problen. but want to sort a linked lists with custom created data objects.

have you done anything? can you post some code?

and http://www.google.com/search?hl=en&i...=Google+Search

sure heres the code exchanging data, but thats not what i want to do.

the code is in spanish so i hope you can understand it

Code:

---

file for the node class:

//definicion de la plantilla de clase Nodo
#ifndef F_NODO_H
#define F_NODO_H

template<class TIPONODO>
class Lista;

template<class TIPONODO>

class Nodo{
        friend class Lista<TIPONODO>;
    public:
                Nodo(const TIPONODO &);
                TIPONODO obtener_datos()const;
        private:
                TIPONODO datos;
                Nodo<TIPONODO> *ptr_siguiente;

};

//definicion de funciones miembro
//constructor
template<class TIPONODO>
Nodo<TIPONODO>::Nodo(const TIPONODO &info)
        :datos(info),ptr_siguiente(0)
{
        //vacio
}

//devuelve el valor de datos
template<class TIPONODO>
TIPONODO Nodo<TIPONODO>::obtener_datos()const
{
        return datos;
}

#endif

//////////////////////////////////////////////////////////////////////////////////
file for list class:

//definicion de la plantilla de clase Lista
#ifndef F_LISTA_H
#define F_LISTA_H

#include "f_nodo.h"

template<class TIPONODO>

class Lista{
        public:
                Lista();
                //~Lista();
                void insertar_nodo(const TIPONODO &);
                bool esta_vacia()const;
                void imprimir()const;
                void mezclar(const Lista<TIPONODO> &,
                        const Lista<TIPONODO> &);
               
                void ordenar();
               
        private:
                Nodo<TIPONODO> *ptr_inicio;
                Nodo<TIPONODO> *ptr_ultimo;
        //funcion de utileria para ordenar listas
               
                //funcion de utileria para concatenar listas
                void concatenar(const Lista<TIPONODO> &,
                                                const Lista<TIPONODO> &);
                //funcion de utileria para saber el tamanio de la lista
                int tamanio_lista();
};

//definicion de funciones miembro

//constructor
template<class TIPONODO>
Lista<TIPONODO>::Lista()
        :ptr_inicio(0),ptr_ultimo(0)
{
        //vacio
}

//destructor
//template<class TIPONODO>
//Lista<TIPONODO>::~Lista()
//{
        //Nodo<TIPONODO> *ptr_actual = ptr_inicio;
        //Nodo<TIPONODO> *ptr_temp;

        //if(!esta_vacia()){
                //cout << "\nDestruyendo nodos...\n";
                //while(ptr_actual != 0){
                        //cout << ptr_actual->datos << ' ';
                        //ptr_temp = ptr_actual->ptr_siguiente;
                        //delete ptr_actual;
                        //ptr_actual = ptr_temp;
                       
                //}
                //cout << endl;
        //}
       
//}


//insertar nodo
template<class TIPONODO>
void Lista<TIPONODO>::insertar_nodo(const TIPONODO &valor)
{
        Nodo<TIPONODO> *ptr_nuevo = new Nodo<TIPONODO>(valor);
        if(esta_vacia()){
                ptr_inicio = ptr_ultimo = ptr_nuevo;
               
        }
        else{
                ptr_ultimo->ptr_siguiente = ptr_nuevo;
                ptr_ultimo = ptr_nuevo;
               
        }
}

//verifica si esta vacia
template<class TIPONODO>
bool Lista<TIPONODO>::esta_vacia()const
{
        return ptr_inicio == 0;
}

//imprime lista
template<class TIPONODO>
void Lista<TIPONODO>::imprimir()const
{
        Nodo<TIPONODO> *ptr_actual = ptr_inicio;
        cout << "Imprimiendo lista...\n";
       
        while(ptr_actual != 0){
                cout << ptr_actual->datos << ' ';
                ptr_actual = ptr_actual->ptr_siguiente;
        }
        cout << endl;
}

template<class TIPONODO>
void Lista<TIPONODO>::concatenar(const Lista<TIPONODO> &lista1
                                                                ,const Lista<TIPONODO> &lista2)
{
        //declara ptrActual que apunte al inicio de la primer lista
        Nodo<TIPONODO> *ptr_actual = lista1.ptr_inicio;
       
        //for 2 veces porque son dos listas las que se concatenan
        for(int i = 0;i < 2; i++){
                //mientras no termine la primera
                while(ptr_actual != 0){
                        Nodo<TIPONODO> *nuevo_ptr = new Nodo<TIPONODO>(ptr_actual->datos);
                        if(esta_vacia())
                                ptr_inicio = ptr_ultimo = nuevo_ptr;
                        else{
                                ptr_ultimo->ptr_siguiente = nuevo_ptr;
                                ptr_ultimo = nuevo_ptr;
                        }
                        ptr_actual = ptr_actual->ptr_siguiente;       
                }
            //cuando termina while porque actualPtr == 0o sea termina
                //la primera lista, pone a ptrActual a que apunte a a la
                //otra lista para concatenarlas
                ptr_actual = lista2.ptr_inicio;
        }
}

template<class TIPONODO>
void Lista<TIPONODO>::mezclar(const Lista<TIPONODO> &primera,
                                          const Lista<TIPONODO> &segunda)
{
        concatenar(primera,segunda);
        ordenar();
}

template<class TIPONODO>
void Lista<TIPONODO>::ordenar()
{
Nodo<TIPONODO> *ptr_actual = ptr_inicio;
Nodo<TIPONODO> *siguiente = ptr_actual->ptr_siguiente;        int temp = 0;
   
//obtiene tamanio de lista
 int tamanio_lista = 1;
while(ptr_actual != 0){
tamanio_lista++ ;
ptr_actual = ptr_actual->ptr_siguiente;
}
      ptr_actual = ptr_inicio;
   
//utilizo -2 en el ciclo ya que si no se hace asi se pasa
//ya que debe llegar hasta el apuntador ptr_siguiente del
//penultimo elemento o si no queda el apuntador indefinido
        for(int i = 0; i < tamanio_lista-2; i++){
                for(int j = 0; j < tamanio_lista-2; j++)                        if(ptr_actual->datos > siguiente->datos){
                temp = siguiente->obtener_datos();
                siguiente->datos = ptr_actual->datos;                        ptr_actual->datos = temp;
        }
                       
      ptr_actual = ptr_actual->ptr_siguiente                                siguiente = siguiente->ptr_siguiente;
                  }
        //pone de nuevo ptr_Actual en ptr_inicio                ptr_actual = ptr_inicio;
        //pone siguiente a que apunte al segundo objeto
        siguiente = ptr_actual->ptr_siguiente;
       
        }
}

//tamanio de la lista
template<class TIPONODO>
int Lista<TIPONODO>::tamanio_lista()
{
        int s_lista = 0;
    Nodo<TIPONODO> *ptr_actual;
    ptr_actual = ptr_inicio;

        while(ptr_actual != 0){
                s_lista++ ;
        ptr_actual = ptr_actual->ptr_siguiente;
        }
        return s_lista;
}


#endif

/////////////////////////////////////////////////////////////////////////////////
main file:

//EJERCICIO 17.7
//autor: Alex Mejia
//inicio de desarrollo: 24/08/04
//ultima revision: 24/08/04
////////////////////////////////

#include <iostream>
using namespace std;

#include "f_lista.h"

#include<ctime>

//genera la lista aleatoria
void generar_lista(Lista<int> &);

int main()
{
        //semilla random
        srand(time(0));

        Lista<int>list1;
    generar_lista(list1);
        list1.imprimir();
       
        Lista<int>list2;
        generar_lista(list2);
        list2.imprimir();
       
        Lista<int>list3;
        list3.mezclar(list1,list2);
        list3.imprimir();
       
       
        return 0;
}

void generar_lista(Lista<int> &lista)
{
        int n_aleatorio = 0;
        int arreglo[5] = {11,2,3,4,5};

        for(int i = 0; i < 5; i++){
                n_aleatorio = 1 + rand() % 30;
                lista.insertar_nodo(n_aleatorio);
        }
}

//////////////////////////////////////////////////////////////////////////////////

some translations to help you out:

ordenar = sort
tamanio = size(for list size)
generar lista = generate list
mezclar = join(join 2 lists in 1)
imprimir = print(print list)

---

sorry for the indentation but the browser messed it up

>im trying to sort a linked list with the bubblesort method
What possible reason under the sun could you have to sort a linked list with bubble sort? Insertion sort is the way to go for the simple stuff, then try mergesort. Both are easily implemented with linked lists. If you're really adventurous you could try sorting a list with quicksort, but that's for a later exercise. ;)

Quote:

---

Originally Posted by Prelude

>im trying to sort a linked list with the bubblesort method
What possible reason under the sun could you have to sort a linked list with bubble sort? Insertion sort is the way to go for the simple stuff, then try mergesort. Both are easily implemented with linked lists. If you're really adventurous you could try sorting a list with quicksort, but that's for a later exercise. ;)

---

ok thanks

oops, forgot about this thread. But Prelude is right, I would choose (and have in the past) mergesort for sorting a linked list. You could search for the "skyline algorithm" using mergesort to give you some ideas.

Quote:

---

Originally Posted by terracota

but i want to sort it exchanging and redirectioning the pointers

---

Do what you would do if you were to move the data itself only apply that to the pointers. That is to say swap the targets they point at.

Inspired with this thread I tried to implement selection sort on linked list on simple example So far I manage to do this:

Code:

---

#include <iostream>
using namespace std;
struct Node
{
        int data;
        Node* next;
};

class List
{
                Node *head;
                void insert(Node*,int);
public:
        List();
        ~List();
        void insert_head(int);
        void remove_head();
        void show();
        void sort();
        int len();
};

List::List():head(0){}
List::~List(){//appropriate cleanup
}
void List::insert(Node* n,int data)
{
        Node* cur=new Node;
        cur->data=data;
        cur->next=n;
        n=cur;
}
void List::insert_head(int data)
{
        if(!head)
        {
                head=new Node;
                head->data=data;
                head->next=0;
                return;
        }
        Node* newNode=new Node;
        newNode->data=data;
        newNode->next=head;
        head=newNode;
}

void List::show()
{
        Node* tmp=head;
        while(tmp)
        {
                printf("%d ",tmp->data);
                tmp=tmp->next;
        }

}

int List::len()
{
        Node* tmp=head;
        int i=0;
        while(tmp)
        {
                i++;
                tmp=tmp->next;
        }
        return i;
}
void List::sort()
{
        Node* min,*tmp,*cur,*tmpi;
        int data,le;
        le=len();
        tmpi=head;
while(tmpi->next) //this is not working properly
{
        min=tmp=tmpi;
        while(tmp->next)
        {
                if(min->data > tmp->next->data)
                {
                        min=tmp;
                }
                tmp=tmp->next;
        }
        data=min->next->data;
        cur=min->next;
        min->next=min->next->next;
        delete cur;
        insert(tmpi,data);
       
}
tmpi=tmpi->next;
}
       

int main()
{
        List lista;
        lista.insert_head(2);
        lista.insert_head(4);
        lista.insert_head(8);
        lista.insert_head(10);
        lista.show();
        lista.sort();
        lista.show();
}

---

Idea is that in the first iteration I choose the smallest element and put it at the begining. In the next iteration I need to choos min element from the rest and so on...
I tried to do this with tmpi but no success.
If someone can point to me place whaere I'm making mistakes?
Thanks!