Page 291 - Computer science 868 Class 12
P. 291

The output of the preceding program is as follows:
                 Before sorting array
                 Mumbai Kolkata Delhi Chennai Amritsar
                 Sorted array

                 Amritsar Chennai Delhi Kolkata Mumbai
                 Bubble Sort and Selection Sort

                                         Bubble Sort                                  Selection Sort


                       1.  Compares with  the next element and  swaps if  the  1.   Selects the  minimum  element from the unsorted
                         condition matches                              part of the array and places it in the next position in
                                                                        the sorted part of the array.
                       2.  Execution is slow.                         2.  Execution is fast.
                       3.  Less efficient                             3.  More efficient

                 Insertion Sort
                 In this type of sorting technique, the elements from the unsorted part are extracted and placed at the correct position
                 in the sorted part by pushing the elements matching the condition to the right one by one.



                   Program 8     Write a program to sort an array using Insertion Sort.

                   1       class InsertionSort

                   2       {
                   3           double arr[] = { 1.2,4.6,7.8,4.5,8.9 };

                   4           void sort()
                   5           {
                   6               int i,j;

                   7               double key;

                   8               int len = arr.length;
                   9               System.out.println("Before Sorting : ");
                   10              for (i = 0; i < len; ++i)

                   11                  System.out.print(arr[i] + " ");
                   12              System.out.println();

                   13              for (i = 1; i < len; ++i)
                   14              {

                   15                  key = arr[i];
                   16                  j = i - 1;

                   17                  while (j >= 0 && arr[j] > key)
                   18                  {

                   19                      arr[j + 1] = arr[j];




                                                                                                                       289
                                                                                                              Arrays   289
   286   287   288   289   290   291   292   293   294   295   296