Page 305 - Cs_withBlue_J_C11_Flipbook
P. 305

33              }
                   34          }

                   35      }
                 The output of the preceding program is as follows:
                 Enter the number of elements: 10

                 Enter a number: 112
                 Enter a number: 54
                 Enter a number: 23
                 Enter a number: 134
                 Enter a number: 32
                 Enter a number: 67
                 Enter a number: 90
                 Enter a number: 10

                 Enter a number: 4
                 Enter a number: 9
                 The sorted array is:
                 4 9 10 23 32 54 67 90 112 134

                 Insertion Sort
                 In this process, the second element is checked with the first element and if the element is found to be smaller than
                 the previous one, in the case of ascending sort, the first element is shifted by one index to the right and the second
                 element is placed in the front. Similarly, the third element is checked with the previous elements and as long as
                 the condition is satisfied the numbers are shifted, then the element in the third position is placed. This procedure
                 continues until the last iteration is executed.
                 Let us take the following example,

                 The array is to be sorted in ascending order:

                                     Index         0          1           2           3           4
                                       Ar         10          5           14          7          21
                 Step 1:  The second element is compared with the first element.

                                     Index         0          1           2           3           4
                                       Ar         10          5           14          7          21

                        Since, ar[1] < ar[0], i.e., 5 < 10 is true; shift the element.
                                                                                       th
                        Element ar[0] is shifted to the next position and ar[1] is placed in the 0  index,
                                     index         0          1           2           3           4
                                       Ar          5          10          14          7          21

                 Step 2:  The second element is compared with the third element.

                                     Index         0          1           2           3           4
                                       Ar          5          10          14          7          21




                                                                                                                       303
                                                                                                              Arrays   303
   300   301   302   303   304   305   306   307   308   309   310