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);
}
}
}
}
}
Output:-
5,9,7,3,2
Sorted List is
3,5,7,9,2
Explanation of java Insertion Sort:-
Outer loop will run for index 1 to 4 // similar to picking the card
<Internal loop> // Internal loop will run only once as picked card should be compared with only 5.
9 picked and this will compare with only one element which 5.
As 5 is less than 9 no swapping.
Outer loop // Second card picked which is 7.
<Internal loop> // Internal loop will run two times as picked card should be compared with 9 and 5.
7 is compared with 9, and it will swap the position.
Now 7 and 5 will compare, no swapping.
Outer loop // Third card picked which is 3.
<Internal loop> // Internal loop will run three times as picked card should be compared with 9,7 and 5.
3 is compared with 9, and it will swap the position.
Now 3 and 7 will compare, and it will swap the position.
Now 3 and 5 will compare, and it will swap the position.
Outer loop // Fourth card picked which is 2.
<Internal loop> // Internal loop will run four times as picked card should be compared with 9,7 ,5,3.
2 is compared with 9, and it will swap the position.
Now 2 and 7 will compare, and it will swap the position.
Now 2 and 5 will compare, and it will swap the position.
Now 2 and 3 will compare, and it will swap the position
For array size 5 number of total execution is:
4 + 3 + 2 + 1 = 10.
