CODEWITHSUNDEEP
javasortinginsertlinked-listinsertion-sort
tzegian
tzegian

Reputation: 589

Insertion Sort algorithm java doubly linked list

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.

Upvotes: 1

Views: 903

Answers (2)

rcgldr
rcgldr

Reputation: 28828

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

Upvotes: 1

Kenney
Kenney

Reputation: 9093

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.

Upvotes: 1

Related Questions