Insertion Sort

Insertion Sort: The idea behind is that in each iteration, it consumes one element from the input elements, removes it and finds its correct position i.e., where it belongs in the sorted list and places it there.

It iterates the array by growing the sorted list behind it at each iteration. It checks the current element with the largest value in the sorted list. If the current element is larger, then it leaves the element at its place and moves to the next element else it finds its correct position in the sorted list and moves it to that position. It is done by shifting all the elements which are larger than the current element to one position ahead.

Since, 7 as the first element has no other element to be compared with, it remains at its position. Now when we move towards 4, we have 7 which is the largest element in the sorted list and greater than 4. So we will move 4 to its correct position. Similarly with 5, as 7 (largest element in the sorted list) is greater than 5, we will move 5 to its correct position. Finally for 2, all the elements on left side of 2 (sorted list) are moved one position forward as all are greater than 2 and then 2 is placed on first position. Finally you will get a sorted array.

Complexity : Complexity of Insertion sort is O(n²) .

import java.util.Scanner;

class Insertion

{

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

int arr[]=new int[n];

void input()

{

for(int i=0;i<n;i++)

{

System.out.printf("Enter the %d element:",(i+1));

arr[i]=sc.nextInt();

}

}

void sort()

{

for(int i=1;i<n;i++)

{

int j=i;

int key=arr[j];

int x=j-1;

while(key<arr[x]&&j>0)

{

arr[j]=arr[j-1];

j=j-1;

x=j-1;

if(x==-1)

break;

}

arr[j]=key;

}

}

void display()

{

System.out.println();

System.out.println("the sorted array is:");

for(int i=0;i<n;i++)

{

System.out.print(arr[i]+"\t");

}

}

void showsteps()

{

for(int i=1;i<n;i++)

{

int j=i;

int key=arr[j];

int x=j-1;

System.out.println();

System.out.printf("OuterLoop: %d",i);

while(key<arr[x]&&j>0)

{

System.out.println();

System.out.printf("InnerLoop: %d",j);

System.out.println();

arr[j]=arr[j-1];

j=j-1;

x=j-1;

for(int t=0;t<n;t++)

System.out.print(arr[t]+"\t");

System.out.println();

if(x==-1)

break;

}

arr[j]=key;

try

{

Thread.sleep(3000);

}

catch(InterruptedException e)

{

System.out.println(e.getMessage());

}

}

}

}

class InsertionTest

{

public static void main(String args[])

{

System.out.println("enter the total number of elements:");

Insertion i1=new Insertion();

i1.input();

//i1.sort();

//i1.display();

i1.showsteps();

i1.display();

}

}