Java - Insertion Sort Implementation and discussion.

This article will discuss a simple insertion sort algorithm in Java.
See ALL Java Postings   |  Insertion Sort By Language Java Scala Go Python Perl


Discussion of Insertion Sort
Insertion sort is one of the most natural ways of sorting a collection of comparable items.  The reason it is one of the most natural ways is because it is the way most people will sort physical items.   For example each year (about this time) I will sort all 12 of my previous years phone bills, gas bills, etc...  The algorithm used to sort them is to place the first one in stack.  Then the second one is compared to the first one to see if it goes in front of or behind the first one.  The third one is then compared to each if the two sorted items to determine where it fits in.  This procedure continues until all 12 bills are in the pile.  Once all 12 bills are in the pile it is sorted. I happen to sort form oldest to newest, my spouse does it the other way newest to oldest.

Applying this concept to a collection of objects in a computer is fundamentally the same.  The algorithm dictates that one will iterate over a collection of elements in an unsorted list 1 at a time, and place that item into it's correct location in a sorted list.

If the collection of objects to sort is n, insertion sort will take at most $O(n^2)$ operations to perform the sort, it will take on average $\frac{1}{2} O(n^2) = O(n^2)$, and in the best case senario will take $O(n)$ operations.


Questions:  


1.  What would be the initial characteristics of a list that took the worst case order $O(n^2)$ to sort?
2.  What would be the initial characteristics of a list that took the best case order $O(n)$ to sort?




Java Solution:

/*------------------------------------------------------------------------------
   Copyright (c) 2011 ecocrypt.com

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 -----------------------------------------------------------------------------*/
package insertionsort;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;

public class InsertionSortAlgorithm<type extends Comparable> {
    Collection<type> unsortedCollection;

    public InsertionSortAlgorithm(){
        unsortedCollection = new ArrayList<type>();
    }

    public InsertionSortAlgorithm(Collection<type> sourceCollection){
        unsortedCollection = new ArrayList<type>(sourceCollection);
    }
    public void add(Type element){
        unsortedCollection.add(element);
    }
    public Collection<type> getUnsortedCollection(){
        return unsortedCollection;
    }

    public List<type> sortWithInsertionSort(){
        LinkedList<type> sortedList = new LinkedList<type>();
        for (Type nextObject : unsortedCollection) {
            sortedList = placeInSortedList(sortedList,nextObject);
        }
        return sortedList;
    }

    private LinkedList<type> placeInSortedList(LinkedList<type> sortedList, Type nextObject){
        int insertionIndex = 0;
        for (Type object : sortedList) {
            if(nextObject.compareTo(object)>0){
                break;
            }
            ++insertionIndex;
        }
        sortedList.add(insertionIndex, nextObject);
        return sortedList;
    }
}

Answers:
1.  The best case senario would be order: $O(n)$
2.  The worst case senario would be order: $O(n^{2})$

Java - Hello World

Java's Hello World is simpler than Go's (golang), but not as simple as Python's.  Also like python the output is quite portable from platform to platform.  Writing hello world in Java requires the following steps:

Step 1: Create a Java source file
There are actually quite a few caveats to this step alone because Java as some requirements that make it more restrictive  than any other language in this blog.  In Java, there everything is an "Object" and thus extends from java.lang.Object.  Therefore, you will have to create a full class definition even though we will not be instantiating any classes.  The source file for Hello World thus looks like the following:
__________________________________________________________________________________

public class HelloWorld extends java.lang.Object {
    public static void main(String args[]){
        System.out.println("Hello World in Java from ecocrypt.blogspot.com");
    }
}

__________________________________________________________________________________

There is another caveat in Java the class HelloWord must be stored in a file called HelloWorld.java. Picking another name will cause a compiler error.

Step 2: Compile the Java Source
At a command prompt, type the java compiler command:
prompt % javac HelloWorld.java

The result of this will be to produce an output file called HelloWorld.class, this class file is a byte code version of the HelloWorld.java source file.  Unlike golang, where the output of the linker can be directly executed, the java class file is not executable.  However, a java executable program and load the HelloWorld.class file, and execute the instructions.

Step 3: Running HelloWorld
At the command prompt, type:
prompt % java HelloWorld
Hello World in Java from ecocrypt.blogspot.com

Congratulate yourself!  You have successfully installed the JDK, created a simple java source file compiled it to byte code, and run it inside of the Java Virtual Machine.