Page 416 - computer science (868) class 11
P. 416

Binary Search
                                                    0   1    2   3   4    5   6    7   8   9
                                       Search 23    2   5    8  12   16  23   38  56   72  91
                                                   L=0  1    2   3  M=4   5   6    7   8   H=9
                                        23 > 16
                                           nd
                                      take 2  half  2   5    8  12   16  23   38  56   72  91
                                                    0   1    2   3   4   L=5  6   M=7  8   H=9
                                        23 > 56
                                           st
                                      take 1  half  2   5    8  12   16  23   38  56   72  91
                                                                         L=5,
                                       Found23,     0   1    2   3   4   M=5  H=6  7   8   9
                                       Returns 5    2   5    8  12   16  23   38  56   72  91

              Step 8:  If a[mid] < searchvalue then initialise begin = mid + 1.

              Step 9:  If pos not = -1 then go to Step 10 else go to Step 11.
              Step 10: Display searchvalue found at index pos, go to Step 12.

              Step 11: Display searchvalue not found.
              Step 12: Stop.


              13.5.4 Sorting Algorithms
              Problem 12: Write an algorithm to sort an array of a given size in ascending order using the BUBBLE SORT technique.



                      Note:  Bubble Sort program is already covered in the Array chapter of this book.


              Step 1:  Start.                                                            9  6   2  8   3  1  7   5  4
              Step 2:  Initialise variable i to 0.
                                                                                         6  2   8  3   1  7  5   4  9
              Step 3:  Repeat Step 4 to Step 9 while i < size-1.
                                                                                         2  6   3  1   7  5  4   8  9
              Step 4:  Initialise variable j to 0.
                                                                                         2  3   1  6   5  4  7   8  9
              Step 5:  Repeat Step 6 to Step 8 while j < size-i -1.
                                                                                         2  1   3  5   4  6  7   8  9
              Step 6:  If array[j] > array[j+1] then go to Step 7, else go to Step 8.
              Step 7:  Swap a[j] and a[j+1].                                             1  2   3  4   5  6  7   8  9
              Step 8:  Increment j by 1.                                                 1  2   3  4   5  6  7   8  9

              Step 9:  Increment i by 1.                                                 1  2   3  4   5  6  7   8  9
              Step 10: Display sorted array.
              Step 11: Stop.

              Problem 13: Write an algorithm to sort an array of a given size in ascending order using the SELECTION SORT
              technique.


                      Note:  Selection Sort program is already covered in the Array chapter of this book.


              Step 1:  Start.
              Step 2:  Initialise variable i to 0.

              Step 3:  Repeat Step 4 to Step 12 while i < size - 1.


                414414  Touchpad Computer Science-XI
   411   412   413   414   415   416   417   418   419   420   421