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})$