Creating an Insertion Sort in Java

When I was studying programming through the University of Maryland, I came across a sorting algorithm known as the insertion sort. I learned that if I had a small array of about 100 elements or less, I could use this sorting algorithm to sort through the array and place each element in its proper order. I thought this was cool at the time because it gave me the opportunity to be able to sort data using one storage variable. Not to mention that knowledge of this algorithm helped me in a class project I was working on at the time.

There is one little problem about this algorithm, however. It is not very efficient (i.e. why I stated earlier that it is only good on a small array). The issue is that its main function is to compare an element of an array to another in a linear fashion. That is, it takes an element and compares it to every element until it reaches a less or greater than value < >. Then after that is reached, it then places the element in its proper place. So the algorithm has to make many passes through each element to place a value in its proper place. In fact, the number of passes equals the number of elements within the array. However, it is still good to know this algorithm just in case you need it for smaller sorting tasks.

Programming the Sort:

In this article, I wanted to create my own Insertion Sort class and test it using an array that holds random integers. I also decided to target my program as a Java console application. As of this writing, I programmed everything using Netbeans 7.0.1 and the Java 1.6 SDK.

So, in the NetBeans IDE, I created a regular Java console application. I then created a new class with the following code:

 0 && data[moveItem -1]>insert)
            {
                //shift right one slot
                data[moveItem] = data[moveItem – 1];
                moveItem–;
            }//end while
            data[moveItem] = insert;//Place inderted element
            printPass(next, moveItem);//output pass of algorithm
        }//end for
    }
    //print to console a pass for each algorithm
    public void printPass(int pass, int index)
    {
        //Header to mark eaxh pass
        System.out.print(String.format(“after pass %2d: “, pass));
        //output present array state until swap time
        for(int i = 0; i < index; i++)
        {
            System.out.print(data[i]+" ");
        }//end for
            
        System.out.print(data[index] + "* ");//star indicates a swap
        //finish array output
        for(int i = index + 1; i < data.length; i++)
        {
            System.out.print(data[i] + " ");
        }//end for
            
        System.out.print("n           ");//for alignment
        // -- indicates the amount that the array was sorted
        for(int i = 0; i <= pass; i++)
        {
                System.out.print("-- ");
        }//end for
            
        System.out.println("n ");//add endline
    }//end printPass
    
    // method to change interger to string for output
    public String toString()
    {
        return Arrays.toString(data);
    }//end toString()
}//end class InsertSort

After I created the above code, I then added the object to the main class with the following code:

Main Class for This Java Project:

Here is the output that I received when I ran the program through the IDE output window.

Output from NetBeans IDE “Output Window.”

Unsorted Array:
[75, 31, 21, 91, 47, 84, 77, 48, 88, 61, 19, 33, 60, 34, 73, 31, 58, 12, 14, 35]

after pass 1: 31* 75 21 91 47 84 77 48 88 61 19 33 60 34 73 31 58 12 14 35
— —

after pass 2: 21* 31 75 91 47 84 77 48 88 61 19 33 60 34 73 31 58 12 14 35
— — —

after pass 3: 21 31 75 91* 47 84 77 48 88 61 19 33 60 34 73 31 58 12 14 35
— — — —

after pass 4: 21 31 47* 75 91 84 77 48 88 61 19 33 60 34 73 31 58 12 14 35
— — — — —

after pass 5: 21 31 47 75 84* 91 77 48 88 61 19 33 60 34 73 31 58 12 14 35
— — — — — —

after pass 6: 21 31 47 75 77* 84 91 48 88 61 19 33 60 34 73 31 58 12 14 35
— — — — — — —

after pass 7: 21 31 47 48* 75 77 84 91 88 61 19 33 60 34 73 31 58 12 14 35
— — — — — — — —

after pass 8: 21 31 47 48 75 77 84 88* 91 61 19 33 60 34 73 31 58 12 14 35
— — — — — — — — —

after pass 9: 21 31 47 48 61* 75 77 84 88 91 19 33 60 34 73 31 58 12 14 35
— — — — — — — — — —

after pass 10: 19* 21 31 47 48 61 75 77 84 88 91 33 60 34 73 31 58 12 14 35
— — — — — — — — — — —

after pass 11: 19 21 31 33* 47 48 61 75 77 84 88 91 60 34 73 31 58 12 14 35
— — — — — — — — — — — —

after pass 12: 19 21 31 33 47 48 60* 61 75 77 84 88 91 34 73 31 58 12 14 35
— — — — — — — — — — — — —

after pass 13: 19 21 31 33 34* 47 48 60 61 75 77 84 88 91 73 31 58 12 14 35
— — — — — — — — — — — — — —

after pass 14: 19 21 31 33 34 47 48 60 61 73* 75 77 84 88 91 31 58 12 14 35
— — — — — — — — — — — — — — —

after pass 15: 19 21 31 31* 33 34 47 48 60 61 73 75 77 84 88 91 58 12 14 35
— — — — — — — — — — — — — — — —

after pass 16: 19 21 31 31 33 34 47 48 58* 60 61 73 75 77 84 88 91 12 14 35
— — — — — — — — — — — — — — — — —

after pass 17: 12* 19 21 31 31 33 34 47 48 58 60 61 73 75 77 84 88 91 14 35
— — — — — — — — — — — — — — — — — —

after pass 18: 12 14* 19 21 31 31 33 34 47 48 58 60 61 73 75 77 84 88 91 35
— — — — — — — — — — — — — — — — — — —

after pass 19: 12 14 19 21 31 31 33 34 35* 47 48 58 60 61 73 75 77 84 88 91
— — — — — — — — — — — — — — — — — — — —

Sorted Array:
[12, 14, 19, 21, 31, 31, 33, 34, 35, 47, 48, 58, 60, 61, 73, 75, 77, 84, 88, 91]

So, that is it! Again, the insertion sort is not the most efficient sorting program out there, but it is ok if you need to sort a small array. You can also use this algorithm for any type (i.e. String, long, etc.). Plus, you can use it for an array of objects.