This week's book giveaway is in the Cloud/Virtualizaton forum.We're giving away four copies of Mesos in Action and have Roger Ignazio on-line!See this thread for details.
Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Finding Nth Largest element of an array without sorting

Anand Hariharan
Rancher
Posts: 272
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

Raj Kumar Bindal
Ranch Hand
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
Posts: 18671

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.

Raj Kumar Bindal
Ranch Hand
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
Posts: 272
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
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,
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
Marshal
Posts: 21123
78
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

Salman Jamali
Greenhorn
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
Posts: 3

Wouter Oet
Saloon Keeper
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.