Thread: 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.

"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.

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.

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.

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.

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.

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

Originally Posted by Kaisshau

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.

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.

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.