7.15 Here is a variation on sorting. The problem is to sort a collection of n nu

Question

7.15 Here is a variation on sorting. The problem is to sort a collection of n nuts and n bolts by size. It is assumed that for each bolt in the collection, there is a corresponding nut of the same size, but initially we do not know which nut goes with which bolt. The differences in size between two nuts or two bolts can be too small to see by eye, so you cannot rely on comparing the sizes of two nuts or two bolts directly. Instead, you can only compare the sizes of a nut and a bolt by attempting to screw one into the other (assume this comparison to be a constant time operation). This operation tells you Loc 3588 of 7820 46%

Explanation / Answer

We can use QuickSort Approach to compare NUTS and BOLTS

1. Select last element as partition from bolt array as pivot,

2. Arrange the array of nuts and returns the partition index ' i ' s

In such that all nuts smaller than nuts[i] are on the left side and all nuts greater than nuts[i] are on the right side.

3. Next using the nuts[i] we can partition the array of bolts.


4. Partioning steap we know take O(N) time

Once the partitioning is done, We can call Quicksort Recursively left to pivot -1 and pivot + 1 to right


So Total time taken will be O(nlogn) in average case and O(n^2) in worst case.

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.