Page 125 - Computer science 868 Class 12
P. 125

2. State the best case and the worst case complexity for bubble sort algorithm.              [ISC 2023]
                   Ans. O(n): Best case complexity for bubble sort algorithm.
                         2
                       O(n  ): Worst case complexity for bubble sort algorithm
                    3. Design a class BinSearch to search for a particular value in an array. Some of the members of the class are given below:  [ISC 2020]
                       Classname                                             :   BinSearch
                       Data Members/Instance variables
                       arr[ ]                                                :   to store integer elements
                       n                                                     :   integer to store the size of the array
                       Member Functions/Methods
                       BinSearch(int nn )                                    :   parameterised constructor to initialize n=nn
                       void fillarray( )                                     :   to enter elements in the array
                       void sort( )                                          :    sorts the array elements in ascending order using any
                                                                               standard sorting technique
                       int bin_search(int l,int u,int v)                     :    searches  for  the  value  ‘v’  using  binary  search  and
                                                                               recursive technique and returns its location if found
                                                                               otherwise returns -1
                       Define the class BinSearch giving details of the constructor( ), void fillarray( ), void sort( ) and int bin_search(int,int,int). Define
                      the main( ) function to create an object and call the functions accordingly to enable the task.
                   Ans. import java.util.*;
                       class BinSearch
                       {
                         int arr[];
                         int n;
                         static Scanner x=new Scanner(System.in);
                         BinSearch(int nn)
                         {
                           n=nn;
                         }
                         void fillarray()
                         {
                            arr=new int[n];
                            System.out.println(“Enter “+n + “ elements”);
                            for(int i =0;i<n;i++)
                            arr[i]=x.nextInt();
                         }
                         void sort()
                         {
                            int t;
                            for(int i=0;i<n-1;i++)
                            for(int j =0;j<n-1-i;j++)
                            {
                               if (arr[j]>arr[j+1])
                               {
                                  t=arr[j];
                                  arr[j]=arr[j+1];
                                  arr[j+1]=t;
                               }
                            }
                         }
                         int bin_search(int l,int u, int v )
                         {
                            int m=(l+u)/2;
                            if(arr[m]==v)
                              return m;
                            else if(l>u)
                              return -1;
                            else if (arr[m]>v)


                                                                                                                       123
                                                                            Implementation of Algorithms to Solve Problems  123
   120   121   122   123   124   125   126   127   128   129   130