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 k^{th}
largest, then try to find the same in its left or right subarray in a
similar fashion.
If pivot happens to be middle of the array always, then search can
happen in N.logN time.
Worst case is O(n^{2}) 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 k^{th} largest.
Order is O(kN)

Heap Sort: If the data were arranged in a heap to begin with, then k^{th}
maximum can be found in O(klogN) operations.
We delete the maximum from the heap k times to get the k^{th}
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 k^{th}
element.
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: