[20 points] Given a set of n distinct numbers, we wish to find the k largest in

Question

[20 points] Given a set of n distinct numbers, we wish to find the k largest in sorted order using a comparison-based algorithm. Give an algorithm that implements each of the following methods, and analyze the running times of the algorithms in terms of n and k - you should provide an upper bound for the worst-case time complexity if your algorithm is determinstic, and expected running time if your algorithm is randomized. You should make your algorithm as fast (asymptotic) as possible and your bound tight. Slower algorithms /analysis receive fewer point. (What we describe below are not full algorithms. You need to give pseudo-code to implement each idea as an algorithm, and output the k largest numbers in sorted order. In your psudo-code, you can use any algorithm we described in class as subroutine: such as MergeSort), Heap-ExtractMax0, etc.) 2.a Sort the numbers, and then list the k largest. 2.b Build a max-priority queue from the numbers, and then extract the largest k elements. 2.c Use a selection algorithm to find the k-th largest number, and the retrieve the largest knumbers.

Explanation / Answer

2.a) Sort the numbers and then list the k largest

In this method, we can use any sorting alogorithm to sort and print the last k elements. Since merge/quick sort performs better in comparision based algorithm. We see quick sort for analysis.

Here it takes O(n^2) in the worst case since we are always picking last element of array as pivot and array can be in sorted order.

If we randomly pick the pivot from random position instead of last position, even if the array is sorted it is always guaranteed that the worst case is O(nlogn) and then printing elements will take O(k) time so T= O(nlogn+k)

2.2) Build a max priority queue from numbers and extract k largest elements

In this method building a max heap from whole array takes O(n) and extracting k largest elements from max heap would take k*logn time so effectively worst case time complexity would be T=O(n+k*logn)

2.3) Using Selection sort algorithm

In this method instead of sorting entire array we can just find out maximum k elements from the array and print them.

Following is the pseudo code:

for i =1:min(k,n-1)

maxElementAtIndexI = i;

for j=i+1 to n

if(array.j> array.maxElementAtIndexI)

maxElementAtIndexI=j;

swap values at ith index and maxElementAtIndexI

The outer for-loop runs k times and finds the maximum element each time from i the index onwards so that array will be sorted in descending order.

The time complexity of this method would be O(n*k)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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