Insertion Sort algorithm java doubly linked list

Question

I have a doubly linked list with a sentinel node and I need to sort it using Insertion Sort with O(n^2) complexity. I have written this code but it does not work as it is supposed to.

Any help in general with insertion sort and specifically with a code?

 public void insertionSort()
 {
 int key,i;
 int size = getSize();
 this.restart();
 for(i = 2; i < size; i++)
 {
 this.next(); // Go to next node
 key = this.getVar(); // get the integer a node holds
 while(this.hasNext() == 1 && position.prev.var < key && position.var != -1)
 {
 position.prev.setNext(position.next);
 position.next.setPrev(position.prev);
 position.setNext(position.prev);
 position.setPrev(position.prev.prev);
 position.prev.setNext(position);
 position.next.setPrev(position); 
 this.goBack(); // go to the previous node
 } 
 }
 }

Size is how many elements my list has. My sentinel has var = -1 so I want to stop when I am at the head that's why I use this.

position.var != -1

and this.hasNext() == 1 is true as long as we are at a position != sentinel node .

In the specific example, I have 35 integers in my list:

5 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1

and I want to sort them this way:

9 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

UPDATE: The code I use into the insertion sort is the following:

public int getSize()
 {
 int size = 0;
 this.restart();
 while(this.hasNext() == 1)
 {
 size++;
 this.next();
 }
 return size;
 }
public void restart()
 {
 position = header;
 previous = Sentinel;
 }
public void next()
 {
 previous = position;
 position = position.next;
 }
public int getVar()
 {
 return position.var;
 }
public void goBack()
 {
 position = previous;
 previous = previous.prev;
 }
 public int hasNext()
 {
 if(position.var != -1)
 return 1;
 else 
 return 0;
 }
 public void setNext(Node next)
 {
 this.next = next;
 }

public void setPrev(Node prev) { this.prev = prev; }

Also, I use a list iterator.

• Kenney: Just to be clear, the first number sequence is after you sorted it?
• tzegian: Nope it is unsorted as I add them to the list. And I need after I finish with the adding, to sort my list using insertion sort.
• Kenney: So what's the output after you sort them?
• mascoj: You'll need to post more source for someone to help. What do goBack(), getRequest(), and hasNext() actually do?
• Kenney: Btw, you never update position (or define it), so position.var != -1 is always the same value, indicating it either doesn't sort at all, or never terminates (or maybe something in between).

Answer 1

Here's the notes from my analysis of the inner loop, and you were right, there's definitely a problem there.

position.unlink(): step out of line, neighbours become direct neighbours

position.prev.next = position.next; // TODO 1: position.next.prev = position.prev
position.next.prev = position.prev; // TODO 2: position.prev.next = position.next
 ^ Breaks TODO 1, but we can: position.prev.next.prev = position.prev

So we still need TODO 1 and then 2, in that order:

 -- TODO 1: position.prev.next.prev = position.prev
 -- TODO 2: position.prev.next = position.next

position.insertBefore(position.prev): re-queue one place further back in line

position.next = position.prev; // TODO 3: position.prev.prev = position
position.prev = a = position.prev.prev; // TODO 4: a.next = position
// ^ // same: position.prev.next = position 
// | // *Error 1!*
// + breaks TODO's 1 and 2, *Error 2!*
// + breaks TODO 3, but we can instead: position.next.prev = position

Regarding error 1, TODO 3 and TODO 4 both involve position.prev, setting both it's next and prev to position; this effectively surrounds position.prev with position. No matter if it steps forward or backward, it's direct neighbour will be position. After the one step though, everything is the same. Interesting structure - it's like the front and back door of your house both access the same spot.

Error 2 makes it impossible to update position.prev, which is needed for TODO's 1, 2 and 3. We can still meet TODO 3 by using the alternate expression accessing a.next through position.prev's next field, but TODO's 1 and 2 can no longer be met.

position.insertBefore(position.prev), continued:

position.prev.next = position; // DONE: 4 
position.next.prev = position; // DONE: 3 

These two lines complete TODO 3 and 4, so all that's left is:

 -- TODO 1: position.prev.next.prev = position.prev
 -- TODO 2: position.prev.next = position.next
 -- TODO 5: fix Error 1
 -- TODO 6: fix Error 2

Fixing error 1 involves making sure TODO 1 and 2 are done before TODO 4, and fixing error 2 is making sure TODO 3 is done before a is assigned.

You end up with 8 assignments; in hindsight, not unsurprising for a doubly-linked list and a movement involving 4 nodes.

Answer 2

This should fix the problem:

 int j;
 // ...
 for(i = 1; i < size; i++)
 {
 this.restart(); // start at ith node
 for(j = 0; j < i; j++)
 this.next();
 key = this.getVar(); // same code as before

or use another variable that advances by one node at a time for each outer loop.

Also, shouldn't this.hasNext() be renamed to this.hasPrev() ?

The main part of the code seems correct, example diagram:

 // goal: swap B and C
 // initial state
 p 
 -> -> -> ->
 A B C D
 <- <- <- <-
 // remove C from list
 position.prev.setNext(position.next);
 position.next.setPrev(position.prev);
 p
 ----->
 -> -> ->
 A B C D
 <- <- <-
 <----
 // update C next and previous 
 position.setNext(position.prev);
 position.setPrev(position.prev.prev);
 p
 ----->
 -> -> ->
 A C B D
 <- <- <-
 <----
 // insert C into list
 position.prev.setNext(position);
 position.next.setPrev(position);
 p
 -> -> -> ->
 A C B D
 <- <- <- <-