Question

Bob has a set A of n nuts and a set B of n bolts, such that each nut in A has a unique matching bolt in B. Unfortunately, the nuts in A all look alike, and the bolts in B all look alike as well. The only kind of a comparison that Bob can make is to take a nut-bolt pair (a, b), such that a is in A and b is in B, and test to see if the threads of a are larger, smaller, or a perfect match with the Bob to match up all of his nuts and bolts Here efficiency is measured in terms of the number of nut-bolt comparisons. Note that we cannot have any nut-nut or bolt-bolt type comparisons. We can obviously compare every nut against every bolt, but that would require 0(n2) comparisons. Can we do better? Hint: think about QuickSort.]

Answer 1

Code:

import java.util.Arrays;

public class NutsAndBoltsProblem {

public static void main(String[] args) {

int bolts[]={3,2,9,5,7,1,6,8,10,4};

int nuts[]={6,1,8,2,9,10,3,5,4,7};

quickSort(bolts,nuts,0,bolts.length-1);

System.out.println("BOLTS[] = "+Arrays.toString(bolts));

System.out.println("NUTS[] = "+Arrays.toString(nuts));

}

public static void quickSort(int bolts[],int nuts[],int bstart,int bend)

{

if(bstart>bend)

return ;

int pivot=bolts[bend];

pivot=partition(nuts,bstart,bend,pivot);//based on bolt comparison

pivot=partition(bolts,bstart,bend,pivot);//based on nut comparison

quickSort(bolts,nuts,bstart,pivot-1);

quickSort(bolts,nuts,pivot+1,bend);

}

public static int partition(int ar[],int start,int end,int pivot)

{

int pindex=start;

int loc=end;

for(int i=start;i<=end;i++)

{

if(ar[i]<pivot)

{

swap(ar,pindex,i);

pindex++;

}

if(pivot==ar[i])

loc=i;

}

swap(ar,loc,pindex);

return pindex;

}

public static void swap(int ar[],int x,int y)

{

int temp=ar[x];

ar[x]=ar[y];

ar[y]=temp;

}

}

OUPUT:

EXPLAINATION:

In the quicksort function, what i am doing is taking the end of bolts array as the pivot .

now , use the partition logic to partition the NUTS array based on this pivot. I have added a location variable in the partition method, that will set the location as i , where Nut[i]==pivot (comparing nut with bolt). swapping the pindex with this location and returning the pindex.

now use this nut pivot (pindex from nut) to partition the bolts array as done above.

else remain the same logic of quicksort.

っ indee on- and HuA