Suppose you have a black box that can take in a set of distinct numbers, and ret

Question

Suppose you have a black box that can take in a set of distinct numbers, and return the median of the numbers (or one median in the case that the set is of even size), plus a partioning of the remaining numbers into two groups: the group of numbers less than the chosen median, and the group of numbers greater than the chosen median. Describe an algorithm that uses the black box to sort an unsorted set of n numbers. The algorithm cannot compare two numbers - only the black box can do that. However, the algorithm can count the number of elements in a set. Don’t worry about low level programming details, just the algorithmic essentials. Suppose the black box takes O(n) operations to process a set of size n. Write out the recurrence relation for the total number of operations this algorithm uses to sort n numbers, including the operations taken by the black box. Solve the recurrence. Explain your work.

Explanation / Answer

function sort( Array ) :

black_box(Array, median, Set1, Set2) ;

// Set1 is elements less than median, Set2 are elements greater then median

sort(Set1)

sort(Set2)

cnt = count_no_of_elements(Set1)

Array[cnt+1] = median

for i = 1 to cnt :

Array[i] = sorted_Set1[i]

for i = cnt+2 to n :

Array[i] = sorted_Set2[i]

return Array

Since there are log(n) levels of separation and each level takes O(n) time

Complexity: O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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