Question

Implement both a brute-force and presorting-based algorithms (using C/C++) solving the problem below. Run the programs on same set of data and record and report the system-times for them.

Problem: Let A = {a1, …, an} and B = {b1, …, bm} be two sets of numbers. Consider the problem of finding their intersection, i.e., the set C of all the numbers that are in both set A and set B.

Answer 1

//C++ program

#include<iostream>
#include <chrono>
#include <ctime>
using namespace std;

void intersection(int a[],int b[],int n,int m){
   for(int i=0;i<n;i++){
       for(int j=0;j<m;j++){
           if(b[j]==a[i]){
               cout<<a[i]<<" ";
               break;
           }
       }
   }
}
int findpivot(int a[],int l,int r){
   int pivot=a[r];
   int i=0,j=-1;
   while(i<r){
       if(a[i]<pivot){j++;
           int temp=a[i];
           a[i]=a[j];
           a[j]=temp;
          
       }
       i++;
   }
  
   a[i]=a[++j];
   a[j]=pivot;
   return j;
}

void quicksort(int a[],int l,int r){
   int pivot;
   if(l<r){
       pivot=findpivot(a,l,r);
       quicksort(a,l,pivot-1);
       quicksort(a,pivot+1,r);
   }
}
void inter(int a[], int b[], int n, int m)
{
int i = 0, j = 0;
  
while (i < n && j < m)
{
  
if (a[i] > b[j])
{
j++;
}
  
else
if (b[j] > a[i])
{
i++;
}
else
{
cout << a[i] << " ";
i++;
j++;
}
}
}
int main(){
   std::chrono::time_point<std::chrono::system_clock> start, end;
   double time;
   std::chrono::duration<double> elapsed_seconds;

   int n =5 , m=6;
   int a[n] ,b[m];
   cout<<"Enter "<<n<<" element of array A\n";
   for(int i=0;i<n;i++)cin>>a[i];
   cout<<"Enter "<<m<<" element of array B\n";
   for(int i=0;i<m;i++)cin>>b[i];
  
  
   cout<<"Intersection of both array without sorting \n";
   start = std::chrono::system_clock::now();
   intersection(a,b,n,m);
   end = std::chrono::system_clock::now();
elapsed_seconds = end - start;
time= elapsed_seconds.count();
   cout<<"Time Taken : "<<time<<"\n";
  
   cout<<"\n\nsorting array A \n";
   quicksort(a,0,n-1);
   cout<<"\n\nsorting array B \n";
   quicksort(b,0,m-1);
  
   cout<<"\nIntersection of both array with sorting \n";
   start = std::chrono::system_clock::now();
   inter(a,b,n,m);
   end = std::chrono::system_clock::now();
elapsed_seconds = end - start;
time= elapsed_seconds.count();
   cout<<"Time Taken : "<<time<<"\n";
  
   return 0;
}

//sample output