Lets say that I want to find the K max values in an array of n elements , and also return them in a sorted output. k may be -
k = 30 , k = n/5 ..
I thought about some efficient algorithms but all I could think of was in complexity of O(nlogn). Can I do it in `O(n)? maybe with some modification of quick sort?
Thanks!
There is a way of sorting elements in nearly O(n), if you assume that you only want to sort integers. This can be done with Algorithms like Bucket Sort or Radix Sort, that do not rely on the comparison between two elements (which are limited to O(n*log(n))).
However note, that these algorithms also have worst-case runtimes, that might be slower than O(n*log(n)).
More information can be found here.
No comparison based sorting algorithms can achieve a better average case complexity than O(n*lg n)
There are many papers with proofs out there but this site provides a nice visual example.
So unless you are given a sorted array, your best case is going to be an O(n lg n) algorithm.
There are sorts like radix and bucket, but they are not based off of comparison based sorting like your title seems to imply.
The problem could be solved using min-heap-based priority queue in
O(NlogK) + (KlogK) time
If k is constant (k=30 case), then complexity is equal to O(N).
If k = O(N) (k=n/5 case), then complexity is equal to O(NlogN).
Another option for constant k - K-select algorithm based on Quicksort partition with average time O(N) (while worst case O(N^2) might occur)
