You are given an array A[1..n]. You are given that for every A[i], A[i] is at mo

Question

You are given an array A[1..n]. You are given that for every A[i], A[i] is at most 20 places from its sorted position (for example, A[30] will be somewhere between A[10] and A[50] in the sorted array. A[5] will be somewhere between A[1] and A[25] in the sorted array.) Give an efficient algorithm to sort A.

(In all algorithm, always explain how and why they work. ALWAYS, analyze the running time complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. Always give arguments as for why what you did is correct. You can not just answer ”yes” or ”no”. NEVER write a program. Only write algorithm in the pseudocode)

Explanation / Answer

Heap Sort is the efficient way to sort A becase Heapsort is a comparison-based sorting algorithm,where having the Time complexity is O(N log(n)).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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