Question 3. (4 marks)

Given an unsorted array A of length n and an integer k in {1,...,n}, you need to write a

efficient algorithm to return the k-th smallest element in the array.

Example:

For A=[9,6,1,100,3,8,5,80] and k=3, the answer is 5.

The algorithm below takes O(n log n). It is not very efficient because k can be much smaller than n.

kSmallest(int A[], int n, int k) {

// assume k has already been tested to be in {1,...,n}

heapSort(A); /* takes O (n log n) */

return A[k-1];

}

Provide a more efficient algorithm (as code or pseudocode) and analyse your algorithm in

terms of big-O notation. To get a full mark, its complexity needs to be at most O(n + k log n).

(for example a solution with O (n log k) would receive maximum 3 marks)

Hint: you may use a heap