Page 443 - Cs_withBlue_J_C11_Flipbook
P. 443

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
                                        take 2  half  2   5    8   12  16   23  38   56  72   91
                                             nd
                                                      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.


                 14.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.


                                                                                                                       441
                                                                            Implementation of Algorithms to Solve Problems  441
   438   439   440   441   442   443   444   445   446   447   448