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.

Just to be clear, the first number sequence is after you sorted it? — Kenney
– Kenney, Commented Nov 12, 2015 at 23:38
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. — tzegian
– tzegian, Commented Nov 12, 2015 at 23:40
You'll need to post more source for someone to help. What do goBack(), getRequest(), and hasNext() actually do? — mascoj
– mascoj, Commented Nov 12, 2015 at 23:42
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). — Kenney
– Kenney, Commented Nov 12, 2015 at 23:43

Kenney · Accepted Answer · 2015-11-13 02:32:39Z

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.

rcgldr · Accepted Answer · 2015-11-13 04:01:53Z

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

Collectives™ on Stack Overflow

Insertion Sort algorithm java doubly linked list

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related