Skip to main content

Insertion Sort in JAVA

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);
   }
   
   
  }
}

Comments

.

Popular posts from this blog

Heap implementation in JAVA

In this tutorial we will see all the functionalities of heaps implemented through java language.



package com.problems.heap;publicclassHeapFunctions{//Function to generate maxheapify where root is max than childspublicvoidmaxHeapify(int Arr[],int i,int N){int largest;int left =2*i+1;//left childint right =2*i +2;//right child System.out.println("left"+" "+left); System.out.println("right"+" "+right); System.out.println("Max size"+" "+N);if(left< N && Arr[left]> Arr[i]){ largest = left; System.out.println("largest left"+largest);}else{ largest = i; System.out.println("largest i"+largest);}if(right < N && Arr[right]> Arr[largest]){ largest = right; System.out.println("largest right"+largest);}if(largest != i ){ System.out.println("No largest"+largest); Arr=swap (A…