# optimise insertion sort code?

Printable View

• 05-12-2012, 02:15 PM
cherrychives
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..

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.
• 05-12-2012, 03:33 PM
quad64bit
Re: optimise insertion sort code?
Quote:

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.
• 05-12-2012, 05:40 PM
doWhile
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...)