Results 1 to 3 of 3
  1. #1
    cherrychives is offline Member
    Join Date
    Apr 2012
    Posts
    25
    Rep Power
    0

    Default 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. #2
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default 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. #3
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,642
    Rep Power
    7

    Default 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...)

Similar Threads

  1. Insertion Sort
    By apiwowar in forum New To Java
    Replies: 2
    Last Post: 08-31-2011, 07:20 AM
  2. Help with insertion sort
    By daendoonge in forum Java Applets
    Replies: 0
    Last Post: 01-29-2011, 11:28 PM
  3. problem with insertion sort???
    By blueduiker in forum New To Java
    Replies: 2
    Last Post: 03-22-2010, 01:17 PM
  4. Insertion Sort in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 07:41 PM
  5. Insertion sort algorithm
    By Albert in forum Advanced Java
    Replies: 2
    Last Post: 06-28-2007, 08:26 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •