What is the minimum number of comparisons needed to sort

Assignment Help Basic Computer Science

Reference no: EM131245364

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 that either the nut is bigger than the bolt, the bolt is bigger than the nut, or they are the same size. What is the minimum number of comparisons needed to sort the nuts and bolts in the worst case?

Reference no: EM131245364

Questions Cloud

Pay particular attention to the stability of the growth rate : We measure economic growth by the percentage change in real GDP. In general terms outline the course of the U.S. output growth rate in recent decades, both in terms of its trend and its changes around trend. Pay particular attention to the stability ..

Devise an algorithm to sort three numbers : Devise an algorithm to sort eight numbers. It should make as few comparisons as possible. How many comparisons and swaps are required in the best, worst, and average cases?

Supply of yen for sale and equilibrium value of the yen : The US relaxes its controls on imports by Japanese companies. Other things being equal, how should this affect the (a) U.S. demand for Japanese yen, (b) supply of yen for sale, and (c) equilibrium value of the yen?

Compare and contrast the three types of unemployment : Compare and contrast the three types of unemployment. Discuss how these three types of unemployment demystify a common myth that "unemployment would not exist if the economy were operating efficiently."

What is the minimum number of comparisons needed to sort : This operation tells you that either the nut is bigger than the bolt, the bolt is bigger than the nut, or they are the same size. What is the minimum number of comparisons needed to sort the nuts and bolts in the worst case?

Explain the concept of the market equilibrium : Explain the effect on demand caused by the following: Why do supply curves slope upward? Explain? What is the difference between a change in supply and a change in demand? Explain the concept of the market equilibrium. What happens when price is set ..

What are three situation that might prompt early termination : What are three situations that might prompt early termination and why? What are the minimum activities (at least three) that need to be performed to properly terminate a project early?

The current dollar-pound exchange rate : You are given the following information. The current dollar-pound exchange rate is $2 per pound. A U.S. basket that costs $100 would cost $120 in the United Kingdom. How much is the dollar overvalued/ undervalued? What do you predict the U.S. real ex..

What is the asymptotic complexity of this algorithm : To solve the problem, compute the distance between each pair of points, using the equivalence processing algorithm to merge clusters whenever two points are within the specified distance. What is the asymptotic complexity of this algorithm? Where ..

User Account

All Pages