In many applications we want to find the k smallest (or largest) elements in an
ID: 3561451 • Letter: I
Question
In many applications we want to find the k smallest (or largest) elements in an array of n
numbers. Your task it to implement several solutions to this problem. First, ask the user
to enter n and k, with k << n. Then generate a random array A with n elements, and finally print
the k smallest elements in the array (if k==1, your method prints the smallest element in A, if k
==2 it prints the smallest and second smallest, and so on).
To find the smallest elements, implement the following algorithms
1. Sort A using selection sort; output the first k elements of A.
2. Sort A using mergesort; output the first k elements of A.
3. Run k iterations of the inner loop of bubble sort, starting from the end; output the first k
elements of A.
4. Run k iterations of selection sort. In the first iteration you find the smallest element in A
and swap it with A[0], in the second iteration you find the smallest element in
A[1],
Explanation / Answer
Output:
Time Complexity: The above solution involves following steps.
1) Build a min heap which takes O(n) time
2) Heapify k times which takes O(kLogn) time.
Therefore, overall time complexity is O(n + kLogn) time.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.