5 Replies - 54408 Views - Last Post: 04 December 2006 - 09:53 AM Rate Topic: -----

#1 bravos  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 11-October 06

Insertion Sort using Linked List

Posted 30 November 2006 - 02:09 PM

I have a class that sets up the parameters for creating a linked list. It has methods for adding integers to a list and printing out the list. I am trying to add a sort method. This method is to look at the first node in the list and traverse the list in order to get the integers in ascending order. I am clearly stuck. Could someone please look at my LinkedListSort class (the sort method in particular) and my test program to point me in the right direction?

public class LinkedListInsertionSort
{  int count = 0;
   protected class LinkedListNode
   {
	   public LinkedListNode link;
		int value;
		
		
		public LinkedListNode(int value_input)
	  {
		 value = value_input;
		 link = null;  }
   }
	  
	   protected LinkedListNode current;
		protected LinkedListNode previous;
		protected LinkedListNode first;
		
		public LinkedListInsertionSort()
		{  first = null;
		   current = null;
		   previous = null;  }
		  
		public void addList(int value_input)
	  {  
		   LinkedListNode newNode = new LinkedListNode(value_input); 
			
			  if (current == null) 
		 {  first = newNode;
				current = newNode;
			previous = newNode;  }
		 else  
		 {  previous.link = newNode;
				previous = previous.link;  }
			count++;	
	   }
	  
	 	 public void print()
	   {  
			LinkedListNode current; 
		  current = first;	
			while (current != null) 
		  {  System.out.println(current.value);
			 current = current.link;  }
	   }

	   public void sort()
	   {  
			int i = 0;
			 current = first;
			 previous = null;
			 
			 if (current.value > previous.value)
			 {  current = first.link;
				previous = first;  }
			 		
			 //while (i <= count)
			 		
				while (current.link != null)
				{  
					if (current.value > current.link.value)
				   {  previous = current;
					  current = current.link;
						   }
			 	  }  
			 
				// count--;		
			 
		  }  
}


   import java.util.*;
   import java.io.*;

	public class TestInsertionSort
   {  
	   public static void main(String[] args)
	  {  LinkedListInsertionSort list = new LinkedListInsertionSort();
		 
			
			list.addList(62);
			list.addList(11);
			list.addList(25);
			list.addList(17);
			list.addList(34);
		  list.addList(43);

			list.print();
			
			list.sort();
			
			list.print();
			}}
	   


Is This A Good Question/Topic? 0
  • +

Replies To: Insertion Sort using Linked List

#2 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 205
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: Insertion Sort using Linked List

Posted 30 November 2006 - 03:13 PM

there seems to be an issue here:
if (current.value > current.link.value)
{  previous = current;
	current = current.link;
}


this simply copies the value of current into previous and this is going to result in a list of 1 #. also you are not comparing anything in previous, so you should not be changing previous.
I think it should be more like:
if (current.value > current.link.value)
{  int temp = current.link.value;
	current.link.value = current.value;
	current.value = temp;
}


there is no need to swap the pointers, unless you want to then, simply change the values to the links, you can simply trade the value stored in the node, it is also an acceptable way to sort a list.
Was This Post Helpful? 0
  • +
  • -

#3 bravos  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 11-October 06

Re: Insertion Sort using Linked List

Posted 30 November 2006 - 03:44 PM

Thanks, that seems to sort the first 2 integers in my linked list.
Now I need to traverse the list. I am trying to use a while loop.
I've shown it in my code as

while (current.link != null)

I had thought that if I use this with the if statement, then it would go through the list once and sort the first integer into the correct spot. I would still have to do another loop that would check every integer in the list.
Was This Post Helpful? 0
  • +
  • -

#4 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 205
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: Insertion Sort using Linked List

Posted 30 November 2006 - 03:59 PM

haha, i'm having a bad day, ok you are using insertion sort.... my method is for bubble sort, and yes insertion should only go through once

here's a better implementation:
if (current.value > current.link.value)
{  
Node n = current; //grab the needed node
previous.link = current.link; //rmeove it from the list
proper_pos(n); //
}


you will need to create a poper_pos(Node n){} method, which traverses the list for the proper place this node belongs and insert it there.
Was This Post Helpful? 0
  • +
  • -

#5 bravos  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 11-October 06

Re: Insertion Sort using Linked List

Posted 01 December 2006 - 09:14 AM

I am sorry, forgive me cuz I'm new to this stuff. Have you ever felt like you're just digging a hole. Well I'm going around in circles here. The way this is being set up leads me to believe that it will go through for the first integer and put it in the correct spot, but it then needs to take the next integer and find it's spot. Currently all this give me is a print out of my original list and then when the sort method is called I get a nullpointerexception. I'm sure that is because previous is set to equal null. I'm also sure that even when that is corrected, the program is not going anywhere. Can someone please redirect me?


public void proper_pos(LinkedListNode n)
		 {  LinkedListNode p;
						
			 while (current.link != null)
			 {  if (current.value > current.link.value)
				{  int temp = current.link.value;
				current.link.value = current.value;
				current.value = temp;
					p = current; }
			}
		 } 		 
 		 
		  public void sort()
		{  
			current = first;
			 previous = null;
			 LinkedListNode n;
			 
			 {  if (current.value > current.link.value)
			 {  n = current; //grab the needed node
				previous.link = current.link; //remove it from the list
				proper_pos(n); }
			 } 

This post has been edited by bravos: 01 December 2006 - 09:14 AM

Was This Post Helpful? 0
  • +
  • -

#6 bravos  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 11-October 06

Re: Insertion Sort using Linked List

Posted 04 December 2006 - 09:53 AM

I figured it out...The addition of a method to traverse the list and find the proper position was a huge help. Thanks you!!!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1