Insertion sort

"Insertion sort means placing an element in a proper position " ie.., sorting means arranging an elements in Ascending order or in Descending order.Insertion means inserting an element in a right position. Let us consider an example, An array 'A' consists of  FIVE element
 i.e  A[5], A[0]=25, A[1]=15, A[2]=30, A[3]=10, A[4]=1.


Given elements are
                                          A[0]             A[1]         A[2]          A[3]           A[4]

25

15

30

10

1

                                           A[0]             A[1]         A[2]          A[3]           A[4]

25

15

30

10

1

compare the elements 25>15 so interchange the elements 25 and 15

  A[0]             A[1]         A[2]          A[3]           A[4]

15

25

30

10

1

 A[0]             A[1]         A[2]          A[3]           A[4]

15

25

30

10

1

now compare 15 with 25,30,10 .15>10 insert 10 in the location of A[0] by shift the elements to right

A[0]             A[1]         A[2]          A[3]           A[4]

10

15

25

30

1

Compare 10 with elements 10 >1 insert 1 in the location of A[0] by shift the elements to right

1

11

15

25

30

Algorithm:

Function insertsort (a, n)

a:list of elements.

n:size of the list.

Step 1: entry

Step 2: for i from 0 to n do the following steps

begin

Step 3: take a[i] as a key element:

key = a[i]

Step 4: for j from i-1 down to 0

when key < a[j], do the following step

begin

a [j+1]=a[j]

end

Step 5: a [j+1]=key

end

Step 6: exit