Insertion Sort in Java with examples

royal52 Oct 7, 2016 100 0

SaveSavedRemoved 0

Insertion sorting is very similar to bubble sorting, even in worst case the running time will be same. The key concept of insertion sort is similar to arrange the playing card while player picks the 13 cards from the table and arrange those in order in hand. For example, on the table, we have four cards with number 3, 4, 5 and 6 in some random order. Suppose in the first-time player pick a card and it is 5, the second time he picked card number 1 then he will put card number left to card number 5 as he wants to arrange in increasing order. Now third time he got a card no 6 he will put right to card no and now the last card he will put left 4. As all the time player is inserting a new card.

Algorithm: inspired from playing cards.

Implementation of InsertionSort in Java:-

package one;
import java.util.ArrayList;
import java.util.Random;
public class InsertionSort
{
public static void main(String[] args)
{
// Creating a list of an integer
ArrayList<Integer> list = new ArrayList<Integer>();
// Create a new object to create a random integer number
Random randomGenerator = new Random();
for (int i = 0; i < 5; ++i){
// add random generated
list.add(randomGenerator.nextInt(100));
}
for(int i : list)
System.out.print(i + ",");
InsertionSorting(list);
System.out.println("\n" + "Sorted List is ");
for(int i : list)
System.out.print(i + ",");
}
private static void InsertionSorting(ArrayList<Integer> list)
{
int temp;
// Initially first element took as reference value
// and than scan and sort rest of n-1 number
for (int outer = 1; outer < list.size()-1; outer++)
{
for(int inner = outer ; inner > 0 ; inner--)
{
if(list.get(inner) < list.get(inner-1))
{
temp = list.get(inner);
list.set(inner,list.get(inner-1));
list.set(inner-1,temp);
}
}
}
}
}