CODEWITHSUNDEEP
javalinked-listinsertion-sort
James Luxton
James Luxton

Reputation: 394

Insertion sort using Linked Integer Nodes

Hey there I have been trying to get an insertion sort method to work for a class I'm taking and we have been told to use insertion sort to sort a linked list of integers without using the linked list class already in the Java libraries.

Here is my inner Node class I have made it only singly linked as i don't fully grasp the circular doubly linked list concept yet

public class IntNode
{
  public int value;
  public IntNode next;
}

And here is my insertion sort method in the IntList class

public IntList Insertion()
{
IntNode current = head;

while(current != null)
    {
    for(IntNode next = current; next.next != null; next = next.next)
        {
        if(next.value <= next.next.value)
            {
            int temp = next.value;
            next.value = next.next.value;
                next.next.value = temp;
            }           
        }
    current = current.next;
    }
return this;
}

The problem I am having is it doesn't sort at all it runs through the loops fine but doesn't manipulate the values in the list at all can someone please explain to me what I have done wrong I am a beginner.

Upvotes: 0

Views: 7365

Answers (3)

Yash Bansal
Yash Bansal

Reputation: 400

I agree with the Zim-Zam opinion also. The loop invariant of insertion sort also specifies this: "the subarray which is in sorted order". Below is the code, I implemented for insertion sorting in which I created another linked list that contains the element in sorted order:

Node newList=new Node();
        Node p = newList;
        Node temp=newList;
        newList.data=head.data;
        head=head.node;
        while(head!=null)
        {
            if(head.data<newList.data)
            {
                Node newTemp = new Node();
                newTemp.data=head.data;
                newTemp.node=newList;
                newList=newTemp;
                p=newList;
            }   
            else
            {
                while(newList!=null && head.data>newList.data)
                {
                    temp=newList;
                    newList=newList.node;
                }
                Node newTemp = new Node();
                newTemp.data=head.data;
                temp.node=newTemp;
                newTemp.node=newList;
                newList=p;
            }

            head=head.node;
        }

Upvotes: 0

aymankoo
aymankoo

Reputation: 671

you need to start each time from the first Node in your list, and the loop should end with the tail of your list -1 like this

 public static IntList Insertion()
{
     IntNode current = head;
     IntNode tail = null;
     while(current != null&& tail != head )
     {
       IntNode next = current;
      for( ; next.next != tail;  next = next.next)
    {
    if(next.value <= next.next.value)
        {
        int temp = next.value;
        next.value = next.next.value;
            next.next.value = temp;
        }
    }
    tail = next;
   current = head;
  }
 return this;

}

Upvotes: 1

Zim-Zam O&#39;Pootertoot
Zim-Zam O&#39;Pootertoot

Reputation: 18148

The insertion operation only works if the list being inserted into is already sorted - otherwise you're just randomly swapping elements. To start out, remove an element from the original list and construct a new list out of it - this list only has one element, hence it is sorted. Now proceed to remove the remaining elements from the original list, inserting them into the new list as you go. At the end the original list will be empty and the new list will be sorted.

Upvotes: 0

Related Questions