Make delicious recipes!

Find kthmaximum in an unsorted array


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 similar fashion.
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 element.
This would take O(n) time.







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal