# Thread: optimise insertion sort code?

1. Member
Join Date
Apr 2012
Posts
25
Rep Power
0

## optimise insertion sort code?

This is the code I've written for sorting a singly linked list using insertion sort method (create a temporary list, then add the values of the unsorted list one-by-one, sorting them in the process). I've been told that insertion sort is really simple, whereas my code looks a bit messy..

Java Code:
```private static intList insertSort(intList list){
intList tempList = new intList(list.size); //create a temporary linked list
tempList.insertFirst(list.first.value); //set value of first node in tempList to equal value of first node in list..
list.deleteFirst(); //..then delete first node from list
while(list.first != null){ //loop while list still has values to be added to tempList
intNode current = tempList.first; //create a node to contain current value in tempList
intNode tempNode = new intNode(list.first.value); //create a node to contain the value to be inserted into tempList
if(tempNode.value < current.value){
tempList.insertFirst(tempNode.value);
}
else{
while(current.nextNode != null && current.next < tempNode.value){ //loop while the node after current is smaller than tempNode
current = current.nextNode;
}
tempNode.next = current.next;
current.next = tempNode.value;
tempNode.nextNode = current.nextNode; //insert tempNode after current
current.nextNode = tempNode;
}
list.deleteFirst(); //delete first node in list before looping again
}
list.first = tempList.first;
return list;
}```
Do I have any unnecessary code here that could be simplified a bit?

I'm going to be looking for these things myself, but I'm very new to linked lists, so any advice would be greatly appreciated.

2. ## Re: optimise insertion sort code?

I've been told that insertion sort is really simple, whereas my code looks a bit messy..
have you seen some of the other sorts? Hehe

I'll look at your algorithm more closely when I have some paper handy.

3. Moderator
Join Date
Jul 2010
Location
California
Posts
1,641
Rep Power
9

## Re: optimise insertion sort code?

My advice (not directly related to your question but pertinent nonetheless) - abstract the algorithm, both on the level of the class which contains the list of objects and the level of the objects you are comparing. Your implementation of the algorithm locks it into requiring your implementation of a LinkedList containing a particular value...what if you want to sort another linked list containing Dates? Or containing Strings? Or sort an array? You'd have to rewrite the algorithm. Take a look at the java Collections framework, it relies on the interface Comparable (object comparison level), which allows the Collections class to be able to sort a List (which could be any implementation of that interface - LinkedList, ArrayList, etc...)