Insertion Sort Algorithm in Java

Insertion sort is a sorting algorithm that builds the final sorted array (or list) one item at a time. The algorithm iterates over the list and removes the current element, finds the location within the sorted part of the list, and inserts it there. This process is repeated until the whole list is sorted.

Algorithm Classification

The following table contains information about the analysis of the Insertion Sort algorithm. It defines the worst, average and best cases in terms of time complexity and also the worst case in space complexity.

Attribute	Value
Class	Sorting Algorithm
Classification	Internal, In-place, Stable Algorithm
Data Structure	Array
Time Complexity: Best	Ω(n)
Time Complexity: Average	Θ(n2)
Time Complexity: Worst	O(n2)
Space Complexity: Worst	O(1)

Please use the following link for an explanation on Big-O notation and what is good, fair and bad.

Insertion Sort In Java

public final class InsertionSort {

    public void sort(int[] collection) {
        if (collection != null) {
            insertionSort(collection);
        } else {
            throw new IllegalArgumentException("Input parameter for array to sort is null.");
        }
    } 


    private void insertionSort(int[] collection) {
        int arrayLength = collection.length;

        for (int unsortIndex = 1; unsortIndex < arrayLength;  unsortIndex++) {
            int newElement = collection[unsortIndex];
            int iterator = 0;

            for (iterator = unsortIndex; iterator > 0 && collection[iterator - 1] > newElement; iterator--) {
                collection[iterator] = collection[iterator - 1];
            }
            collection[iterator] = newElement;
        }
    }
}

Sample Code (GitHub)

The details of the InsertionSort class can be viewed here.

The details of the InsertionSort JUnit Test class can be viewed here.

Conclusion

The Insertion Sort algorithm forms part of a larger group of sorting algorithms. Learning through experience is the reason I created this post about the implementation of the Insertion Sort algorithm in Java. I have learned a lot about how others have solved the Insertion Sort algorithm in other languages including different implementations in Java.

The post Insertion Sort Algorithm in Java appeared first on Code2Bits.