Question

Design an algorithm for the following description. Solution can be done in pseudo-code or steps of the algorithm.

Describe and analyze an algorithm that takes an unsorted array A of n integers (in an unbounded range) and an integer k, and divides A into k equal-sized groups, such that the integers in the first group are lower than the integers in the second group, and the integers in the second group are lower than the integers in the third group, and so on. For instance if A-{4.12.3.8, 7,9. 10.20.5) and k = 3, one possible solution would be A 4,3,5), A2 8,7,9), A 12, 10,20). Sorting A in O(n log n)-time would solve the problem, but we want a faster solution. The running time of your solution should be bounded by O(nk). For simplicity, you can assume that is n a multiple of k, and that all the elements are distinct. Note: k is an input to the algorithm, not a fixed constant.

Answer 1

Solution:

Algorithm:

The algorithm using min heap is defined below:

1. Create a min heap of the k first elements of the given array.
   This costs O(k).
2. For each element (not including in the first k of step 1), compare it with the root of min heap,
   if the element is greater than the root then make it root and call heapify for min heap else ignore it.
   This will cost you O( (n-k) * logk ).
3. Finally, min heap has k largest elements and root of the min heap is the kth largest element.
4. Now, repeat above step up to ((n-k)/k) times to get slots of min k elements till all array element is consumed.

Time complexity: O(k + (n-k)Logk) without sorted output for extracting each K elements of given array

so final time complexity will be O(k + (n-k)Logk) * ((n-k)/k) which is almost equivalent to O(nk).