Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 10 of 10

Thread: Sorting problem

  1. #1
    Junior Member
    Join Date
    Jun 2011
    Posts
    8
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Sorting problem

    I'm attempting to sort a DoublyLinkedList, but my code is producing an error in the cmd box. My problem is, I don't know what's wrong because it just prints line after line of "at(DoublyLinkedList.sortRecur(Test.java:170)" . The code for the sorting algorithm is

    	public void sort ()
    	{
    		Node test = first;
    		Node current = first.getNext();
    		current.setPrev(null);
    		while (current.getNext() != null)
    		{
    			sortRecur(test, current);
    			current = current.getNext();
    		}
    	}
     
    	public void sortRecur(Node test, Node current)
    	{
    		if (test.getData() < current.getData())
    		{
    			if (current.getPrev() == null)
    			{
    				test.setPrev(null);
    				test.setNext(current);
    				current.setPrev(test);
    				first = test;
    			}
     
    			else if (test.getData() > current.getPrev().getData())
    			{
    				(current.getPrev()).setNext(test);
    				test.setPrev(current.getPrev());
    				test.setNext(current);
    				current.setPrev(test);
    			}
     
    			else
    			{
    				sortRecur(test, current.getPrev());
    			}
     
    		}
    		else
    		{
    			if (current.getNext() == null)
    			{
    				test.setNext(null);
    				test.setPrev(current);
    				current.setNext(test);
    				last = test;
    			}
     
    			else if (test.getData() < current.getNext().getData())
    			{
    				(current.getNext()).setPrev(test);
    				test.setNext(current.getNext());
    				test.setPrev(current);
    				current.setNext(test);
    			}
    			else
    			{
    				{
    					sortRecur(test, current.getNext());
    				}
    			}
    		}
    	}

    The line it refers to is the "sortRecur(test, current.getNext());" line. My DoublyLinkedList class is as follows
    class DoublyLinkedList
    {
    	private int size;
    	private Node first;
    	private Node last;
     
    	public DoublyLinkedList ()
    	{
    		first = null;
    		last = null;
    		size = 0;
    	}
     
    	public void add (int data)
    	{
    		if (first == null)
    		{
    			first = new Node(data, null, null);
    			last = new Node(data, null, null);
    		}
    		else if (size < 2)
    		{
    			Node newNode = new Node(data, first.getNext(), first);
    			first.setNext(newNode);
    			last = newNode;
    		}
    		else
    		{
    			Node newNode = new Node(data, null, last);
    			last.setNext(newNode);
    			last = newNode;
     
    		}
    		size++;
    	}
    	public int size()
    	{
    		return size;
    	}
    }

    And my Node class is as follows:
    class Node
    {
      private int data;
      private Node next;
      private Node previous;
     
      public Node(int data, Node next, Node previous)
      {
    	  this.data = data;
    	  this.next = next;
    	  this.previous = previous;
      }
     
      public int getData()
      {
    	  return data;
      }
     
      public Node getNext()
      {
    	  return next;
      }
     
      public Node getPrev()
      {
    	  return previous;
      }
     
      public void setNext(Node next)
      {
    	  this.next = next;
      }
     
      public void setPrev (Node previous)
      {
    	  this.previous = previous;
      }
    }

    If anyone could help me out with what my code's error is, or how I can figure out what the error is, that would be greatly appreciated.


  2. #2
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,545
    My Mood
    Grumpy
    Thanks
    0
    Thanked 167 Times in 158 Posts

    Default Re: Sorting problem

    "at(DoublyLinkedList.sortRecur(Test.java:170)"

    The error message would print out something before this but I assume that it quickly scrolls off the page. My guess is that you have infinite recursion.

  3. #3
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,421
    Thanks
    49
    Thanked 2,215 Times in 2,188 Posts

    Default Re: Sorting problem

    Try debugging your code by adding printlns to show variables's values and how they change and the execution flow.
    If you have a infinite recursion that is outputting too much, add a global variable, increment it a few times and System.exit(0) at when it gets to a certain value to get the first of the printouts.

  4. #4
    Junior Member
    Join Date
    Jun 2011
    Posts
    8
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sorting problem

    My testing code is
    public class A3Q2
    {
    	public static void main (String [] args)
    	{
    		String input = "";
    		int data;
    		DoublyLinkedList testList = new DoublyLinkedList();
    		try
    		{
     
    			BufferedReader br = new BufferedReader(new FileReader("unsorted.txt"));
    			while ((input = br.readLine()) != null)
    			{
    				data = Integer.parseInt(input);
    				testList.add(data);
    			}
     
    		}
     
    		catch (IOException E)
    		{
     
    		}
     
    		System.out.println("StartPreSort\n" + testList + "ENDED");
     
    		testList.sort();
     
    		System.out.println("PostSort\n" + testList + "DONE");
     
     
     
    	}
    }

    And I think it is an infinite recursion problem, it doesn't occur if I have the count escape at anything below a couple thousand. It compiles without error, just a problem on execution.

    Oh, and the unsorted file is just numbers, like this:
    234
    34
    67
    545
    34
    12
    3
    -5
    -12

    If I have it print out the current value with each recursion, it's never getting past the first value it seems. I can't exactly tell, but it prints "234" repeatedly if I insert "System.out.println(current.getData());" right before the recursion call.

  5. #5
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,545
    My Mood
    Grumpy
    Thanks
    0
    Thanked 167 Times in 158 Posts

    Default Re: Sorting problem

    Node test = first;
    Node current = first.getNext();
    current.setPrev(null); // ?????
    I do have to wonder why you are severing the link from the second node back to the first.

  6. #6
    Junior Member
    Join Date
    Jun 2011
    Posts
    8
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sorting problem

    So that the first two if statements in my sortRecur method will evaluate to true if the first value is lower than the second, and it will be placed back in front.

  7. #7
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,421
    Thanks
    49
    Thanked 2,215 Times in 2,188 Posts

    Default Re: Sorting problem

    You need to print out all the values involved in the comparions to see what is happening.
    Put an id with the values so you can tell where they were printed:
    System.out.println("curr.gD=" + current.getData()); // print number with an id

  8. #8
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,545
    My Mood
    Grumpy
    Thanks
    0
    Thanked 167 Times in 158 Posts

    Default Re: Sorting problem

    Quote Originally Posted by Kaisshau View Post
    So that the first two if statements in my sortRecur method will evaluate to true if the first value is lower than the second, and it will be placed back in front.
    Then your algorithm is wrong. You should only be setting previous to null if you do move second node to be the first. Don't stuff around with links unless you are actually moving a node.

  9. #9
    Junior Member
    Join Date
    Jun 2011
    Posts
    8
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sorting problem

    I think somehow my testNode and currentNode are getting set to the same thing and end up pointing at each other. I think it
    s in this part:
    			else if (test.getData() > current.getPrev().getData())
    			{
    				(current.getPrev()).setNext(test);
    				test.setPrev(current.getPrev());
    				test.setNext(current);
    				current.setPrev(test);
    			}

    I don't see what happens. It's supposed to insert the testNode between the current and the one before it.

    Re: Junky
    I added a line of code to make the second node the first after I remove the first and use it to call the recursive method.

  10. #10
    Junior Member
    Join Date
    Jun 2011
    Posts
    8
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Sorting problem

    Is it possible it's calling my else statement that calls for recursion even when it's not supposed to? I'm having problems with another program doing a similar thing.

Similar Threads

  1. Sorting an array
    By thebestpearl in forum Collections and Generics
    Replies: 5
    Last Post: April 17th, 2011, 08:58 PM
  2. [SOLVED] Sorting and Merging
    By javapenguin in forum What's Wrong With My Code?
    Replies: 36
    Last Post: December 7th, 2010, 07:04 PM
  3. sorting name using Selectionsort
    By asdfg in forum What's Wrong With My Code?
    Replies: 7
    Last Post: May 20th, 2010, 09:44 AM
  4. [SOLVED] sorting
    By kite98765 in forum Algorithms & Recursion
    Replies: 8
    Last Post: February 4th, 2010, 07:34 AM
  5. Selection Sorting
    By chronoz13 in forum Algorithms & Recursion
    Replies: 5
    Last Post: December 10th, 2009, 10:08 AM