Explain sorting algorithm which is optimal in cost

Assignment Help Data Structure & Algorithms

Reference no: EM1348856

1. Suppose we are given n numbers, initially stored in an array A and we wish to sort them. When the sort concludes, the sorted output is to be in the array A, in ascending order (i.e., the smallest value in A[0], the next smallest in A[1], etc.). Suppose we use, as our measure of time, the number of times we store a value into the array. In other words,

If x is any value, an assignment statement of the form A[i] = x has a cost of 1.

In particular, an assignment statement of the form A[i] = A[j ] has a cost of 1.

Any other operation (including a comparison between two array items A[i] and A[j ], or an assignment x = A[i] where x is not a location in the array A) has a cost of 0.

(a) Under this cost model, give a lower bound on the worst-case time required to sort the array A. Your answer should be an exact expression in terms of n (i.e., it should not involve asymptotic notation).

(b) Describe a sorting algorithm that is optimal with respect to this cost model and uses O(n) space. That is, time used by your algorithm should exactly match the lower bound given in (a).) Explain why your algorithm satis?es the cost and space requirements.

(c) Describe an in-place sorting algorithm that is optimal with respect to this cost model. That is, the time used by your algorithm should exactly match the lower bound given in (a).) Explain why your algorithm satis?es the cost requirement and is in-place.

Reference no: EM1348856

Questions Cloud

Examples of variable cost for a fitness center : One way to own your own fitness business is to buy a franchise. Snap Fitness is a Minnesota-based business that offers franchise opportunities. For a very low monthly fee ($26, without an annual contract) customers can access a Snap Fitness center..

Illustrate marginal tax rate alter his level of charitable : Illustrate by how much (what percentage) does the consumer facing a 15% marginal tax rate alter his or her level of charitable giving as the result of the deductibility of charitable contributions?

Evaluate the appropriate authority and control structure : What factors evaluate the appropriate authority and control structure - a research and development laboratory

Find the last price at stock traded : Machines stock was found in the Thursday, December 14, issue of the Wall Street Journal. AdvBusMach ABM 81.75 1.63 Given this data, answer the questions:

Explain sorting algorithm which is optimal in cost : Explain a sorting algorithm which is optimal with respect to this cost model and uses O(n) space. That is, time used by algorithm should exactly match lower bound

Master of science in psychology : Master of Science in Psychology with a concentration in Industrial Organizational Psychology.

What is the rationale in allowing express oral agencies : Express authority - Explain what is the rationale in allowing express oral agencies (i.e., no prior written contract) to bind principals

How fast must a centrifuge rotate : A 4.25 bullet traveling horizontally with a velocity of magnitude 375 is fired into a wooden block with mass 1.10 , initially at rest on a level frictionless surface. The bullet passes by the block and emerges with its speed reduced to 110 .

Compute the average number of customers in line : Compute the average number of customers in line for both scenarios and What benefit is available by adding the second service line

User Account

All Pages