Skip to main content

Insertion sort Implementation

 Insertion sort :  In insertion sort, Same process like selection sort , we will divide the array in sorted and unsorted array and we will select element from unsorted array and will insert it into sorted array at its proper position.

   Time Complexity for Insertion sort also is O(n^2).
   space complexity for bubble sort will be O(1).

class InsertionSort {

    public static void sort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
                swap(array, j, j - 1);
            }
        }
    }


    private static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    private static void print(int[] A) {
        System.out.print("[");
        for (int i = 0; i < A.length; i++) {
            System.out.print(A[i]);
            if (i < A.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        int[] A = {111, 80, 14, 21, 19, 31, 19, 121, 10, 190, 80, 6, 7};
        sort(A);
        print(A);
    }
}

Please have a look to the  source code of all sorting method from below link
  1. BUBBLE SORT PROGRAM
  2. SELECTION SORT PROGRAM
  3. INSERTION SORT PROGRAM
  4. MERGE SORT PROGRAM
  5. QUICK SORT PROGRAM



Labels:

Comments

Post a Comment

Popular posts from this blog

Java Program : Writing First Java Factorial Program with explanation

 NAMING CONVENTION IN JAVA : Java is an object oriented programming language , we can relate it to real life object like i mapped Java with human in my previous post JAVA OVERVIEW (SESSION 1)  and represent human properties like body parts as properties in Java and Human can dance , drive , walk , run these can be mapped as Behaviour in java.    Now To represent properties and behaviour in java , there are some standard naming conventions we should follow. Class name should always starts with Uppercase letter like class Student { //Code to be executed } Properties or any kind of variables should starts from lower case and afterwards every first letter of each next word should be in Upper case . like class Student { int studentId ; String studentName ; //Code to be executed } Methods name should also starts from lower case and afterwards every first letter of each next word should be in Upper case . like class Student { int studentId ; String studentName ;
2 comments
Read more

OOPS Concept in Java : ENCAPSULATION

OOPS Concept in Java : ENCAPSULATION   This OOPS concept can be used to make things simpler in case of software development . Main purpose of this concept is to hide the properties of any class and give access to fetch and modified based on business criteria.  A simple example can be a POJO ( Plain Old Java Object) in which all the properties of a class can be private and through getter and setter method of properties we can fetch and update the properties of Object. So instead of having direct access to properties we have created 2 methods to make the CLASS things encapsulated in single unit while access to it is via 2 public methods.   Just consider we have requirement that once the object is created its value should not be changed then simplest way to achieve this  can be done by just removing setter method and we will keep only getter methods to access Object properties . In this case after Object creation whatever the value of Object properties has been initialised it will b
Post a Comment
Read more

OOPS Concept in Java : POLYMORPHISM

 POLYMORPHISM IN JAVA :  Polymorphism means mutiple forms of Single reference. And to understand in simple way just take an example from my previous post of OOPS CONCEPT IN JAVA : INHERITANCE  , I request you guys to go through this link before proceding here. So in this post I have created a method called sum() in PARENT class which has been used by CHILD class without writing same sum() method in CHILD class. This was possible becuase of INHERITANCE concept in java.  But what if CHILD class is not satisfied with PARENT sum() and CHILD class wants to improve it like by adding some message before the calculation. To do this we have another OOPS CONCEPT IN JAVA i.e POLYMORPHISM and by applying this logic we can make same sum() method behvae differently based on Object. As I mentioned earlier POLYMORPHISM means different forms and same has been achieved here by calling same sum() method but the output is different based on Object on which it has been called. If Object is of PARENT
Post a Comment
Read more