This is a variation of sorting problem where sorting is limited to only a part of the input.
So we need to analyze different sorting algorithms from a partial sorting perspective.
Pivot element: Choose a
pivot element and put it in its proper place i.e. the place where it
would have been if the array was sorted.
When this is done, all elements to its right will be bigger and all elements to its left
will be smaller.
If current pivot is not the kth
largest, then try to find the same in its left or right subarray in a
If pivot happens to be middle of the array always, then search can
happen in N.logN time.
Worst case is O(n2) but expected order is O(n)
It is also called as Selection Rank algorithm
Bubble Sort: Find maximum element in the array and swap it with the end of the array.
Then find maximum in N-1 array elements. After k iterations, element
at N-k position will be the kth largest.
Order is O(kN)
Heap Sort: If the data were arranged in a heap to begin with, then kth
maximum can be found in O(klogN) operations.
We delete the maximum from the heap k times to get the kth
maximum and each delete operation takes logN time.
So, total order is O (K log N)
Mini-Heap Sort: If the data was not arranged in a heap, we can create a min-Heap of size K
Loop over all the elements and add to the min-Heap
At the end, min-Heap will contain topmost K elements of the array.
Order is O(N log K)
Binary Search Tree: If the data were arranged in a BST, it can be
traversed in in-order to return the kth
This would take O(n) time.
Got a thought to share or found a bug in the code? We'd love to hear from you: