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

Selection Sort in JAVA

What is selection sort?

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

The process is:-

1) Find minimum element in unsorted array.
2) Swap the element at the end of sorted array.

when i=0 we don't have any sorted array so element will be replaced from first element later the sorted array end will growas the index.

Steps:-


underline elements are sorted array, the length is increasing with each minimum element added at the end.minimum element11 1125122264 minimum element12 1112252264 minimum element22 1112222564 minimum element25 1112222564 minimum element64 1112222564
Program:-


package sorting;publicclassSelectionSort{//function to print arraypublicstaticvoidprint(int[] arr){for(int i=0;i<=arr.length-1;i++) System.out.print(" "+arr[i]); System.out.println(" ");}//function to swap elementspublicstaticint[]swap(int[] arr,int i,int j){int temp; temp=arr[i]; arr[i]=arr[j]; arr[j]=temp…

Bubble Sort in JAVA

What is bubble sort?

It is a sorting technique that is based on the comparison.Here we compare adjacent element, if the first element is larger than the second we swap each other. We do the same procedure again and again until array do not sort completely.

Example:-
5 1 4 2 8



51428here pass is nothing but iterating the loops equal to number of elements in the array but if it already sorted before then we can break the loop anddo existPASS1 case0 1 //check 0 and first element15428 case1 2 //check 1 and 2 element14528 case2 314258 case3 414258 swap istruePASS2 //first pass completed now do second pass case0 114258 case1 212458 case2 312458 case3 412458 swap istrue PASS3 // third pass case0 112458 case1 212458 case2 312458 case3 412458 swap isfalse since swap is false we break from the loop and do not go for fourth and fifth pass
Program:-

package sorting;publicclassBubbleSort{//function to print arraypublicstaticvoidprint(int[] arr){for(int i=0;i<=arr.length-1;i++) Syst…