Insertion Sort in JAVA

04:19

What is insertion sort?

It is a sorting technique that is based on the partitioning of array into two parts like selection sort, sorted and unsorted.

The process is:-

compare adjacent elements.
if(left > right)
Swap the element
{
check for sorted array whether it is still in sort manner(put j=i and loop in until j is not equal to zero)
- No
check for if(right<left)
swap
do it until at the end of position.
}

Implementation:-

Underline eleemnts are part of sorted array

inside main array loop 14 27 10 33 35 19 42 4 (14 10 27 33 35 19 42 4 (here sorted array is distorted hence sorting has been done inside the loop)
    inside sorted array loop 10 14 27 33 35 19 42 4 
inside main array loop 10 14 27 33 35 19 42 4 
inside main array loop 10 14 27 33 35 19 42 4 
inside main array loop 10 14 27 33 35 19 42 4 
    inside sorted array loop 10 14 27 19 33 35 42 4 
    inside sorted array loop 10 14 19 27 33 35 42 4 
inside main array loop 10 14 19 27 33 35 42 4 
inside main array loop 10 14 19 27 33 35 42 4 
    inside sorted array loop 10 14 19 27 33 4 35 42 
    inside sorted array loop 10 14 19 27 4 33 35 42 
    inside sorted array loop 10 14 19 4 27 33 35 42 
    inside sorted array loop 10 14 4 19 27 33 35 42 
    inside sorted array loop 10 4 14 19 27 33 35 42 
    inside sorted array loop 4 10 14 19 27 33 35 42 
inside main array loop 4 10 14 19 27 33 35 42 (final sorted array)

Program:-


package sorting;

public class InsertionSort {

 //function to print array
   public static void print(int[] arr)
   {
    for(int i=0;i<=arr.length-1;i++)
     System.out.print(" "+arr[i]);
    System.out.println(" ");
   }
   
   //function to swap elements
   public static int[] swap(int[] arr,int i, int j)
   {
    int temp;
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
    
    return arr;
   }
  
  public static void main(String[] args)
  {
   int[] arr={14,27,10,33,35,19,42,4};
   int j;
   for(int i=0;i<arr.length-1;i++)
   {
    if(arr[i]>arr[i+1])
    {
     swap(arr,i,(i+1));
     j=i;
     for(;j>0;j--)
     {
      if(arr[j]<arr[j-1])
      {
       swap(arr,j,(j-1));
       System.out.print("    "+"inside sorted array loop");
       print(arr);
      }
     }
     
    }
    System.out.print("inside main array loop");
    print(arr);
   }
   
   
  }
}

You Might Also Like

0 comments