Insertion Sort using Java

Working :

This sorting technique requires n-1 passes to sort an array of n integers. Insertion sort starts with an assumption that the array is divided into 2 partitions, sorted partition and unsorted partition. Sorted partition is of size 1 and contains only a[0]. Whereas unsorted partition contains remaining n-1 elements. In pass number i , we take ith element of the array(i.e. first element of unsorted partition) and insert it in the sorted partition.

Code :



import java.util.*;

public class Insertion
{
static void insertionsort(int a[])
{
int x,j;

for(int i=1;i<=a.length-1;i++)
{
x = a[i]; j = i;

while(j > 0 && a[j-1] > x)
{
a[j] = a[j-1];
j = j-1;
}

a[j] = x;
}//end of for loop
}//end of insertionsort

public static void main(String args[])
{
System.out.println("Enter number of elements you wish to sort : ");
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

//declare array of n elements

int a[] = new int[n];
//scan array from 0 to n-1 locations
for(int i = 0; i <= n-1;i++)
{
System.out.print("\nEnter element " + (i+1) + " : ");
a[i] = sc.nextInt();
}

System.out.println("\nOriginal array : ");

for(int i=0;i<=n-1;i++)
System.out.print(a[i] + " ");

//sort the array

insertionsort(a);

//print sorted array

System.out.println("\nSorted array : ");

for(int i=0;i<=n-1;i++)
System.out.print(a[i] + " ");

}


}



Output :


Enter number of elements you wish to sort :
5

Enter element 1 : 5

Enter element 2 : 4

Enter element 3 : 1

Enter element 4 : 2

Enter element 5 : 6

Original array :
5 4 1 2 6
Sorted array :
1 2 4 5 6