7 Replies - 8187 Views - Last Post: 29 January 2011 - 01:39 AM Rate Topic: -----

#1 kevinyu  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 27-January 11

Using bubble sort on a linked list

Posted 27 January 2011 - 07:31 AM

I need help regarding sorting, I'm just experimenting if it is possible, but I'm having an error. This is my code. Sorry I'm not that good in programming. Haha just applied that like I'm using an array.

void node::sort()
{
     node *temp = new node();
     node *node1 = new node();
     node *node2 = new node();
     

     
     for(node1 = head;node1->next != NULL ;node1 = node1->next)
     {
     for(node2 = node1->next; node2->next != NULL; node2 = node2->next)
     {
     
     if(node1 < node2)
     {
     temp = node1;
     node1 = node2; 
     node2 = temp;
     }
     }
     }
     
     }



Is This A Good Question/Topic? 0
  • +

Replies To: Using bubble sort on a linked list

#2 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1572
  • View blog
  • Posts: 2,991
  • Joined: 30-May 10

Re: Using bubble sort on a linked list

Posted 27 January 2011 - 07:41 AM

You're swapping the whole node - including the "next" pointer!.

The crude way is to swap just the data, but that probably isn't what you want.
It would be very expensive if each node had a lot of data.


The smart way is to change just the pointers, so
Eg.
head -> B -> A -> C -> null

say you were pointing at B, and you wanted to swap with A
temp = A->next;
A->next = B;
B->next = temp;

The only tricky bit is making sure head still points to the real head, not some swapped node which might have moved.
Was This Post Helpful? 0
  • +
  • -

#3 kevinyu  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 27-January 11

Re: Using bubble sort on a linked list

Posted 27 January 2011 - 07:52 AM

is the loop correct? is swapping the data enough to affect the display? thank you so much for the help! I don't care what method is going to be used as long as it will make things fine! :D

This post has been edited by kevinyu: 27 January 2011 - 08:01 AM

Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5641
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Using bubble sort on a linked list

Posted 27 January 2011 - 09:58 AM

It's a selection sort, not a bubble. You implement a memory leak. And then mess up your list.

 
void node::sort() {
	// you create new nodes and just drop them
	// declare these when you actually need them.
	// node *temp = new node(); // leak
	// node *node1 = new node(); // leak
	// node *node2 = new node(); // leak



	// the loops are fine, looks like a standard selection sort
	for(node *node1 = head;node1->next != NULL ;node1 = node1->next) {
		for(node *node2 = node1->next; node2->next != NULL; node2 = node2->next) {
			// what exactly do you think you're compareing?
			// you're actually comparin the location of the pointer
			if(node1 < node2) {
				node *temp = node1;
				node1 = node2; 
				node2 = temp;
				// yes, you have swappped node values
				// you've also ruined your linked list
				// and probably crashed your loop
			}
		}
	}
}



Your inner bit should look something like:

if(node1->data < node2->data) {
	NodeDataType temp = node1->data;
	node1->data = node2->data; 
	node2->data = temp;
}



Depending on the size of that data, swapping pointers can be more efficient. In such a case, a real bubble sort would probably make that easier. You still have to compare the payload of the node, though.

It's also disturbing that this method is node::sort and not list::sort. Nodes are nodes. A collection of nodes should be a different object. The collection, or list, will have a sort method and contain the head. A node is just an element of a list.
Was This Post Helpful? 0
  • +
  • -

#5 kevinyu  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 27-January 11

Re: Using bubble sort on a linked list

Posted 28 January 2011 - 06:29 AM

Hehehe, thank you baavgai, I've been looking forward to following your suggestion, i was stupid when the one i'm comparing were nodes :) thank you so much! I'll follow your tips! What do you mean about the memory leak? Is using new not really required? Hehe I did really mess up my list with that function!
Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5641
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Using bubble sort on a linked list

Posted 28 January 2011 - 12:56 PM

Memory leak:
 
node *node1 = new node();
// ...
node1 = head;
// the allocated memory that was previously stored in node1 one has been replaced by the value in head.
// You've just lost track of memory you allocated with the prior new and can't retrieve the pointer
// This memory is still allocated to you program but is now inaccessible
// This is commonly called a "memory leak" since you're program will constantly ask for memory and then loose track of it, "leaking" it into the void and out of your system's available resources


This post has been edited by baavgai: 28 January 2011 - 12:56 PM

Was This Post Helpful? 0
  • +
  • -

#7 kevinyu  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 27-January 11

Re: Using bubble sort on a linked list

Posted 29 January 2011 - 01:26 AM

Got it, thank you for the explanation baavgai :D
Was This Post Helpful? 0
  • +
  • -

#8 kevinyu  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 27-January 11

Re: Using bubble sort on a linked list

Posted 29 January 2011 - 01:39 AM

Got the program but in every sort it only compares two numbers, meaning i gotta call the sorting function n times in order for it to be totally sorted! Hehehe
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1