Insertion sort using Linked Integer Nodes

Question

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.

This doesn't look a lot like insertion sort. Also, your if test seems backwards; are you trying to sort into descending order? — Ted Hopp
– Ted Hopp, Commented May 7, 2013 at 3:22
They told us it didn't matter if it sorted descending or ascending which I thought was odd. In the list generation i pass the main method a integer eg 5 and it will generate 5 numbers between 0 and 5. The list is the same passed out as it is in. — James Luxton
– James Luxton, Commented May 7, 2013 at 3:24

aymankoo · Accepted Answer · 2013-05-07 04:10:05Z

1

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;

}

answered May 7, 2013 at 4:10

aymankoo

6716 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

James Luxton Over a year ago

Thankyou aymankoo and everyone else who helped you have been awesome!

Zim-Zam O'Pootertoot · Accepted Answer · 2013-05-07 03:33:28Z

0

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.

answered May 7, 2013 at 3:33

Zim-Zam O'Pootertoot

18.2k4 gold badges45 silver badges71 bronze badges

2 Comments

James Luxton Over a year ago

What would I need to change in my code to achieve this? besides making a new instance of my list class

Zim-Zam O'Pootertoot Over a year ago

Your list class will need to be able to add nodes at arbitrary positions. Your while loop should run until the original list is empty; remove a node from the original list, then use the for loop to insert it into the new list. You should not be swapping any values, only removing and inserting nodes.

Yash Bansal · Accepted Answer · 2017-02-09 00:19:50Z

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

Collectives™ on Stack Overflow

Insertion sort using Linked Integer Nodes

3 Answers 3

1 Comment

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related