# Finding Nth Largest element of an array without sorting

posted 9 years ago

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

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

Posts: 418

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 9 years ago

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

Amarbir, your algorithm doesn't seem to work as described. Perhaps your explanation is incomplete. But I strongly recommend considering Anand's previous advice:

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

Posts: 418

posted 9 years ago

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.

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
"Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away." -- Antoine de Saint-Exupery

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

posted 7 years ago

If the problem is to do it in linear time, then

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

I hope it helps!

**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!

Salman Jamali

Greenhorn

Posts: 5

posted 5 years ago

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.