Originally posted by AmarbirGSP Khokhar: Thnx guys I have managed to write an algorithm for finding Nth largest element without sorting with average complexity linear.... 1) Compare the first array element with rest of the elements and whenever the next element is greater than the first element increment the counter...and break whenever the counter is == N-1... Repeat the process untill the counter == N-1.
Unless I have misunderstood your algorithm description, I believe it won't work. E.g., will it work on an input that is sorted in a descending order?
"Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away." -- Antoine de Saint-Exupery
hi Ranchers, Today i have seen this post.. It may be possible that many of you may know the solution as is already told by Amarbir,i am posting the code because i thought it may be helpful to someone..
Raj, I added code tags to your post. Please use these in the future.
You've added a check for j==A.length-1 which was not present in Amarbir's description. This does give correct results, but it has the effect of saying that the break cannot execute until the last time through the loop. In that case, why break at all? Also, the inner loop executes N*N times, where N is the size of the array. That is not linear.
Amarbir, your algorithm doesn't seem to work as described. Perhaps your explanation is incomplete. But I strongly recommend considering Anand's previous advice:
[Anand]: Look up "selection" or "partition" in your algorithm textbook.
"I'm not back." - Bill Harding, Twister
Raj Kumar Bindal
Joined: Apr 15, 2006
Jim,Thanks for adding code tags to my post. you are right,break is not so much helpful here,so we can write, i = A.length; in place of, break;
Originally posted by Raj Kumar Bindal: Jim,Thanks for adding code tags to my post. you are right,break is not so much helpful here,so we can write, i = A.length; in place of, break;
Your for loop goes from zero to A.length - 1. In other words, when i is A.length-1, that is the very last iteration. Further, your "break" statement comes at the very end of your loop's body. Hence the "break" is redundant. This is what Jim Yingst was pointing out.
Setting i = A.length is no more necessary than the break.
Originally posted by Raj Kumar Bindal: And yah,looking up in book can be more fruitful.
In this particular instance, the algorithm to meet Amarbir's requirements is non-trivial to implement.
To pique your (and Amarbir's) interest, perhaps I can tell you how the algorithm goes? Solve this problem:
"Find the median (i.e., the third biggest or third smallest element) of 5 elements using no more than six key comparisons."
They are called non-comparison based algorithms.. & most that we know compare elements hence non-linear. I am sure atleast one of them would work with your data. Once sorted, you can get the fifth element from start.
However, if "sorting" is not at all an option, then you are talking about selection algorithms. The one I remember is Non-randomized selection algorithm:
This topic is almost two years old. And the original poster hasn't posted in almost that long. I think it is safe to assume that the OP has solved the problem, and at the very least, is no longer active on the ranch.
The topic started will probably have found a solution after all these years. And please UseCodeTags when posting code. I'm closing this topic. If you have questions about this topic feel free to open a new one.
"Any fool can write code that a computer can understand. Good programmers write code that humans can understand." --- Martin Fowler
Please correct my English.
subject: Finding Nth Largest element of an array without sorting