Thread: not succesfull sorting a linked list

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

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

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!