4A: Consider the general problem of finding the median of n entries. We might at

Question

4A: Consider the general problem of finding the median of n entries. We might attempt to adapt the basic idea in the Quicksort routine to solve this problem. Explain how to change the quickSort() code to find the median. Eliminate unnecessary work wherever possible. For simplicity, YOU MAY ASSUME THAT n IS ODD (so that the the definition of 'median' is unambiguous).

4.1B: Based on your algorithm in 4A, give a precise function for the worst-case time complexity of your algorithm on a set of n (random) entries. As you explain how you arrived at your formula, BE SURE TO MENTION the type of data arrangement that will yield these worst-case results.

Explanation / Answer

A.

In quick sort code we take last element as pivot element and place it in it s correct position all element on left are less than this element and all on right side are bigger. So instead of taking last element as pivot element we choose median os number and make it pivot element.

So evert time we call quick sort partition and find if pivot elemet is middle element of array or not if it is middle than this is the median of array.

Algorithm:

B.

every time we left n/2 element and run for remaining element.

n,n/2,n/4,n/8......

So it gp sum

= n/(1/2) = 2n

so worst case complexity : O(N)

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

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