Insertion Sort in java:
Insertion sort is a sorting technique which is use to sort the data in the ascending or descending order. It is most commonly used sorting algorithm compare to other sorting techniques. .It work's more efficient than other sorting algorithm like bubble sort and selection sort.
In insertion sort first of all we need to select first element of an array and collect inside the any variable.and than we need to compare that variable to the previous element,if the previous element is larger than our selected element than we just need to interchange those elements.
Example: Let's discuss the Insertion sort algorithm with the help of a java program.
import java.util.Scanner;
class Insertion
{
static int n;
static int[] arr;
public static void getData()
{
System.out.println("Enter size of an array");
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
arr=new int[n];
System.out.println(" Enter Array elements:");
for(int i=0;i<n;i++)
{
System.out.println("Array elements are:"+(i+1));
arr[i]=sc.nextInt();
}
}
public static void insertSort(int[] arr)
{
int temp=0;
int j=0;
for(int i=1;i<arr.length;i++)
{
temp=arr[i];
j=i;
while(j>0 && arr[j-1]>temp)
{
arr[j]=arr[j-1];
j=j-1;
}
arr[j]=temp;
}
}
public static void main(String[] args)
{
getData();
System.out.println("Array elements before sorting:");
for(int i=0;i<arr.length;i++)
{
System.out.print(arr[i]+" ");
}
insertSort(arr);
System.out.println("");
System.out.println("Array elemnts after sorting:");
for(int i=0;i<Insertion.arr.length;i++)
{
System.out.print(arr[i]+" ");
}
}
}
Output:
Enter size of an array
5
Enter Array elements:
Array elements are:1
100
Array elements are:2
20
Array elements are:3
10
Array elements are:4
5
Array elements are:5
1
Array elements before sorting:
100 20 10 5 1
Array elements after sorting:
1 5 10 20 100
Description:
public static void insertSort(int[] arr)
{
int temp=0;
int j=0;
for(int i=1;i<arr.length;i++)
{
temp=arr[i];
j=i;
while(j>0 && arr[j-1]>temp)
{
arr[j]=arr[j-1];
j=j-1;
}
arr[j]=temp;
}
}
This is the complete logic part of the insertion sort algorithm. Due to this logic part first collect the first element of an array inside a temp variable and after than just compare that variable with previous elements of an array .if any element is grater than our temp variable than we just interchange the elements..
