aspose file tools*
The moose likes Beginning Java and the fly likes Finding Nth Largest element of an array without sorting Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Reply locked New topic
Author

Finding Nth Largest element of an array without sorting

Anand Hariharan
Rancher

Joined: Aug 22, 2006
Posts: 257

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.

cheers


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?

- Anand


"Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away." -- Antoine de Saint-Exupery
Raj Kumar Bindal
Ranch Hand

Joined: Apr 15, 2006
Posts: 418
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..

[ July 25, 2007: Message edited by: Jim Yingst ]
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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
Ranch Hand

Joined: Apr 15, 2006
Posts: 418
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;

And yah,looking up in book can be more fruitful.
Anand Hariharan
Rancher

Joined: Aug 22, 2006
Posts: 257

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."

- Anand
Salman Jamali
Greenhorn

Joined: Dec 01, 2008
Posts: 5
If the problem is to do it in linear time, then there are three well-known linear time sorting algorithms in theory:

1 - Counting Sort,
2 - Radix Sort, and
3 - Bucket Sort.

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:



I hope it helps!
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18829
    
  40

I hope it helps!


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.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Salman Jamali
Greenhorn

Joined: Dec 01, 2008
Posts: 5
Still, except for the "I hope it helps" thing, I hope it helps many others who read these topics (& all posts) while looking for a solution. I did so. So, I hope it helps them
VennkataReddy Kv
Greenhorn

Joined: Mar 28, 2011
Posts: 3

Wouter Oet
Saloon Keeper

Joined: Oct 25, 2008
Posts: 2700

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.
 
Don't get me started about those stupid light bulbs.
 
subject: Finding Nth Largest element of an array without sorting