The Insertion Sort Alogrithm
By Binkster
Poor C++
What is an “Insertion Sort?”
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:
The InsertSort Class
/*********************************************************
//
// InsertSort Class
//
// Defininition: Class creates an array and sorts it.
//*********************************************************
package insertionsorttest;
import java.util.Arrays;//for array creation
import java.util.Random;//Random Generator
//InsertionSort class Constructor
public class InsertionSort {
private int[] data;//array of integer values
private static final Random generator = new Random();//Create Random ints
//create array of given size and fill it with random intergers
public InsertionSort(int size)
{
data = new int[size];// array of values
//fill array with random ints 10-99
for(int i = 0; i < size; i++)
{
data[i] = 10 + generator.nextInt(90);
}
}//end Constructor
//sort array via insertion sort
public void sort()
{
int insert;//temp variable to hold element to insert
//loop through array: data.legth - 1
for(int next = 1; next < data.length; next++)
{
insert = data[next];//store value in current element
int moveItem = next;//initialize a location to place element
//search for a place to put current element
while(moveItem > 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 to Test the Sort
//***********************************************************
//
// Insertion Sort Test Main Program
//
//**********************************************************
package insertionsorttest;
public class InsertionSortTest {
public static void main(String[] args) {
//Create object to perform the insertion sort with 20 elements
InsertionSort sortArray = new InsertionSort(20);
//Print a Header
System.out.println("Unsorted Array:");
//Print unsroted data out to console screen
System.out.println(sortArray + "\n");
//Sort newly created array
sortArray.sort();
//Header
System.out.println("Sorted Array:");
//Print out full sorted array to console screen
System.out.println(sortArray);
}//End Main
}//End Test
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]
And here is the program in a DOS console using the Java Command:
Output in Dos Window
Conclusion:
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 algorith for any type (i.e. String, long, etc.). Plus, you can use it for an array of objects.
Awesome Programming Books from Amazon
 | Amazon Price: $17.00 List Price: $29.99 |
 | Amazon Price: $19.61 List Price: $34.99 |
 | Amazon Price: $34.99 |
 | Amazon Price: $15.00 List Price: $29.99 |
 | Amazon Price: $22.20 List Price: $39.99 |
Like what you see? Subscribe now.
- Ancient Italian History and the Rise of Rome: Part 2
The Copper and Bronze ages saw the rise of three distince cultures in ancient Italy. In the orth there were the Urn-Field folk who had more access to agriculture and metal for their tools plus they cremated thier dead. In the south you had the Apennine culture who where semi-nomadic and herders. You also had the Greeks who established trading posts in the south. - 3 months ago
- Ancient History of Italy and the Rise of Rome: Part 1
Rome is considered one of the most advance empires of all time. It was the first true European empire and its culture and way of life has been talked about throughout the ages. This article begins an explanation of the history of ancient Italy and the inevitable rise of a great empire. - 3 months ago
- Creating Dialogs with Java’s Swing Class
One of the most used classes in java is JOptionPane. This class allows you to create dialogs that appear on the screen. These dialogs can be used for messages as well as user input. i will show you how to create these dialogs with Java code. - 4 months ago
Do you know any predefined sorting classes in Java or C#? Leave a Comment.
Hey Pente,
The bubble sort is pretty much the same (i.e. it has to go trough every element in the array). However, implementing it in code is a little more demanding since you have to define two temp variables and search every element in a nested for loop. So, between the two, the insertion sort is less demanding to code.
Pente 4 months ago
So how does this sorting algorithm compare to a bubble sort?