Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!
    Bookmark Topic Watch Topic
  • New Topic

Finding Nth Largest element of an array without sorting

 
Anand Hariharan
Rancher
Posts: 272
C++ Debian VI Editor
  • Mark post as helpful
  • send pies
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Report post to moderator
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.
 
Raj Kumar Bindal
Ranch Hand
Posts: 418
  • Mark post as helpful
  • send pies
  • Report post to moderator
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
C++ Debian VI Editor
  • Mark post as helpful
  • send pies
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Report post to moderator
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
Marshal
Pie
Posts: 20902
76
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Report post to moderator

 
Wouter Oet
Saloon Keeper
Posts: 2700
IntelliJ IDE Opera
  • Mark post as helpful
  • send pies
  • Report post to moderator
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.
 
    Bookmark Topic Watch Topic
  • New Topic