Algorithm and Program for Insertion Sort

Insertion Sort Algorithm:

Suppose an array with n elements that means a[0], a[1],---a[n – 1] are in memory. The insertion sort algorithm is works as follows.

Step 1: a[1] is inserted either before or after a[0] so that a[0] & a[1] are sorted.

Step- 2: a[2] is inserted its proper position ie., a[0], a[1] , a[2] are sorted.

..........................

..........................

Step(n – 1):a[n – 1] is inserted in its proper position a[1],a[2]---a[n – 1 ] are sorted

Program :

class Isort

{

    int i, j, n, temp;

    int [ ] sort(int a[ ])

   {

      n=a.length;

      for(i=1; i

     {

       for(j=I; a[j – 1]>a[ j ] && j>0; j - -)

      {

        temp=a[j];

        a[j]=a[j – 1]

        a[j – 1]=temp;

      }

   }

   return a;

  }

}

class Display

{

  int i,n;

  void show(int a[ ])

  {

    n=a.length;

    for(i=0;i

   {

     System.out.println(“a[“+i+”]=”+a[i]);

    }

  }

}

class InsertionSort

{

 public static void main(String args[ ])throws IOException

{

 BufferedReader br=new BufferedReader (new InputStreamReader(System.in));

 int n,i;

 System.out.println(‘enter array size”);

 n=Integer.parseInt(br.readLine());

 int x[ ]=new int[n];

 System.out.println(“enter array elements”);

 for(i=0; i

 {

  System.out.println(“enter x[“+i+”]=”);

  x[i]= Integer.parseInt (br.readLine());

 }

Display d=new Display();

InsertionSort s=new InsertionSort ();

System.out.println(“before sorting”);

d.show(x);

s.sort(x);

System.out.println(“after sorting”);

d.show(x);

}

}