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


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Java » Beginning Java
Reply locked New topic
Author

Finding Nth Largest element of an array without sorting

Amarbir Singh
Greenhorn

Joined: Jun 26, 2007
Posts: 20
dear frnz...

I need help I am not able to figure out a generic code for finding nth largest element of an array without sorting it.
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

Hi, welcome to the Ranch.

I don't know what a 'frnz' is, but this sounds like a homework assignment and you haven't specified whether the solution must be Java. Also, not being allowed to sort is a strange requirement. Care to explain?
Manuel Leiria
Ranch Hand

Joined: Jul 13, 2007
Posts: 171
It should be something like this (I didn't tried so it might have errors)



Manuel Leiria<br /> <br />--------------<br />Peace cannot be kept by force; it can only be achieved by understanding. <br /> Albert Einstein
Amarbir Singh
Greenhorn

Joined: Jun 26, 2007
Posts: 20
Dear David,
frnz means friends.... sorry for not being descriptive...!

and i have mentioned that generic code doesnt matter in java or in c++...
Actually the motive is to keep the complexity linear..and you are not allowed to sort the array.

e.g int a[] = new int[]{10,19,2,3,1,98,75,65,8500,850000};

and I have to find Fifth largest element (65) in the array a[] without sorting the array.


Dear Manuel,
Amarbir Singh
Greenhorn

Joined: Jun 26, 2007
Posts: 20
Dear Manuel,

Thnks for reply...but dear your code will only return the largest element of the array and not the nth largest element of array.
vanlalhmangaiha khiangte
Ranch Hand

Joined: Sep 11, 2006
Posts: 169
Original array should not changed.
So ,before you find the Nth largest number
Why don't you make a copy of that array and sort that array
pick out the Nth largest number from the copy array..
This way you are not doing any change in the original array..
Amarbir Singh
Greenhorn

Joined: Jun 26, 2007
Posts: 20
Dear vanlalhmangaiha,

The prerequisite is you are not allowed to explicitly sort the array...you have to do it without sorting...
Francesco Bianchi
Ranch Hand

Joined: Jun 22, 2007
Posts: 62
Create a method which goes through the entire array and compares every single element with a "temporary one". You can do the comparison by calling the method compareTo() of the elements if they ALL implement the Comparable interface or use a Comparator you will have provided to the method as a paramater.

The "Comparable version" of the method could look something like this:



Three considerations:
1. you could avoid using Generics..but they make the method safer.
2. I've dangerously assumed that the array cannot contain any Null element...never do it at home..shame on you if you do it at work ^_^
3. (I've never run the code..but it seems to be correct and, at least on Eclipse, it compiles)


SCJP 5 & 6, SCWCD 5, SCBCD 5
Amarbir Singh
Greenhorn

Joined: Jun 26, 2007
Posts: 20
Dear Bianchi ,

This code'll return the 1st Largest element ... and our requirement is to get the nth largest element of the array without sorting the array....
Ashok Mor
Ranch Hand

Joined: Jul 17, 2007
Posts: 43
Hi AmarbirGSP Khokhar,

Please run this demo.............U should give nth value for out side as a coomand line......... like "Java NthLargest 4"

Ashok Mor
[ July 19, 2007: Message edited by: Jim Yingst ]
Manuel Leiria
Ranch Hand

Joined: Jul 13, 2007
Posts: 171
Here you go

The ideia is:
Create a temporary array with the original contents of the original array, then, at the first iteration, iterate through the orignal array to find the max value. Nest, copy the contents to the temporary array and set the max value found to zero. Recursevly call the method but now call it with the temp array until your temp array has the largest element.
The code is a little bit uggly. There's a lot of improvements that should be done but it will get you started.

If you have doubts, I'll be glad to help
[ July 19, 2007: Message edited by: Manuel Leiria ]
Peter Chase
Ranch Hand

Joined: Oct 30, 2001
Posts: 1970
Please don't give out full solutions to obvious homework questions. Try to help the person towards writing their own program that they understand.

How about a variation of bogosort algorithm? Here's how it would work: -

1) Pick N numbers at random from the original set.

2) See if there are any other numbers in the original set bigger than the ones you picked.

3) If yes, go to (1)

4) Return the smallest of the numbers you picked.

This method is optimised for a parallel quantum computer, capable of executing all the possible random combinations simultaneously.
[ July 19, 2007: Message edited by: Peter Chase ]

Betty Rubble? Well, I would go with Betty... but I'd be thinking of Wilma.
Manuel Leiria
Ranch Hand

Joined: Jul 13, 2007
Posts: 171
Originally posted by Peter Chase:
Please don't give out full solutions to obvious homework questions. Try to help the person towards writing their own program that they understand.


Yes, I know but in my case there's a lot of improvements that should be done in order to have a nice solution.
vanlalhmangaiha khiangte
Ranch Hand

Joined: Sep 11, 2006
Posts: 169
Hey using collections would also be useful...

I don't know whether you are allowed to use this things...but it saves a lot of code...


Francesco Bianchi
Ranch Hand

Joined: Jun 22, 2007
Posts: 62
Originally posted by AmarbirGSP Khokhar:
Dear Bianchi ,

This code'll return the 1st Largest element ... and our requirement is to get the nth largest element of the array without sorting the array....


Sorry, I should have paid more attention reading your needs. Beg your pardon
Ashok Mor
Ranch Hand

Joined: Jul 17, 2007
Posts: 43
Hi AmarbirGSP Khokhar,

Please run this demo.............U should give nth value for out side as a coomand line......... like "Java NthLargest 4"



public class NthLargest {

int array[] = {10,19,2,3,1,98,75,65,8500,850000};
public static void main(String args[]) throws MyException{
new NthLargest(Integer.parseInt(args[0]));
}

public NthLargest(int n)throws MyException{

int skip[] = new int[n];
int i,j,k,l,skipIndex=0,maxJ=0;
int nthMaxValue=0;
boolean skipLoop = false;

if(n>array.length) throw new MyException("Out of scope to grab this number");

for(i=0; i<array.length; i++){
int val=array[i];
maxJ = i;
for(j=0; j<array.length; j++) {

for(k=0; k<skip.length; k++)
if(skip[k] == j)
skipLoop = true;

if(skipLoop){
skipLoop = false;
continue;
}
if(val < array[j]) {
val = array[j];
maxJ = j;
}
}
if(skipIndex == n){
nthMaxValue = array[skip[n-1]];
break;
}

skip[skipIndex++]=maxJ;
}
System.out.println(n+" largest value is : "+nthMaxValue);
}
}

class MyException extends Exception{
String msg="";
MyException(String msg){
this.msg = msg;
}
public String getMessage(){
return msg;
}
}


Ashok Mor
Amarbir Singh
Greenhorn

Joined: Jun 26, 2007
Posts: 20
Dear Ashok,

Your code'll work but the complexity is cubic ... So we have to find more efficient solution...

e.g If we could find First , Second , Third ... largest element upto the value user has asked for e.g 4th largest etc..

Than either we can put this in the stack or in array .....and the last inserted will be our result....

Think in this context... Thnks in advance
cheers
Manuel Leiria
Ranch Hand

Joined: Jul 13, 2007
Posts: 171
Originally posted by vanlalhmangaiha khiangte:
Hey using collections would also be useful...

I don't know whether you are allowed to use this things...but it saves a lot of code...





I think it should be



Amarbir Singh
Greenhorn

Joined: Jun 26, 2007
Posts: 20
Dear Manuel,

your code'll work but we have to think of the best possible solution like...
If you want to use another array you can keep the size n where n = no of largest element that we have to find.

Dear All,
Think of something like searching the 1st , 2nd ... nth largest and subsequently add them to some array or stack...

The concept is clear in my mind the only problem i am facing is How to keep the complexity in average case to LINEAR ....
bart zagers
Ranch Hand

Joined: Feb 05, 2003
Posts: 234
I think something around this algorithm might do the trick:

1: Determine bucket ranges.
2: Assign elements into appropriate buckets.
3: Find bucket B containing the nth element.
4: Recursively call the algorithm on B (or call std::nth element on B).
Amarbir Singh
Greenhorn

Joined: Jun 26, 2007
Posts: 20
Dear Bart,

If you can provide the pseudo code... or more details ...code level..because there are many theoretical solutions but when puting them to practice....It becomes very complicated ....

thnks ... cheers
Svend Rost
Ranch Hand

Joined: Oct 23, 2002
Posts: 904
Originally posted by AmarbirGSP Khokhar:
Dear Bart,

If you can provide the pseudo code... or more details ...code level..because there are many theoretical solutions but when puting them to practice....It becomes very complicated ....

thnks ... cheers


Why dont you provide some code yourself? Try to experiment abit.. it's my expirience that you learn most by doing it yourself.
bart zagers
Ranch Hand

Joined: Feb 05, 2003
Posts: 234
Well,

Take two 'buckets' and a random pivot.
Do something quicksort-like.
Check were your target is based on the sizes of the 'buckets'.
Recalculate which element you are searching for if it is in the second 'bucket'.
Don't bother about 'uninteresting buckets'

I think the rest is up to you.
Ashok Mor
Ranch Hand

Joined: Jul 17, 2007
Posts: 43
Dear AmarbirGSP Khokhar,

You might not have seen code, because it is working on same funda, please have a look into code, paste code into any java editor, like eclipse and give proper spacing.

You solution can be done so simply by collection framework.

Look into collection framework overview.


Ashok Mor
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

Please don't provide complete solutions, pseudo code only.
We like to encourage people to learn for themselves. Writing code for them only helps you.
[ July 19, 2007: Message edited by: David O'Meara ]
Amarbir Singh
Greenhorn

Joined: Jun 26, 2007
Posts: 20
Thanks guys....

Dear Ashok,

We are not allowed to use any inbuilt function or utility ..... like collections....

and I have executed your code...it runs fine...but the complexity is cubic...
Ashok Mor
Ranch Hand

Joined: Jul 17, 2007
Posts: 43
You are welcome dear AmarbirGSP Khokhar,

But think about your requirements, all your requirements are so strange like :

Not allow to use built in methods,
Not allow to use collection framework,
Not allow to use sorting,

And even though you are expecting logic for nthLargest elements in N number of arraysize?



Complex requirements always have complex solutions, think positive.



Ashok Mor
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 39575
    
  27
Originally posted by Ashok Mor:
But think about your requirements, all your requirements are so strange like


That's what homework assignments are like. Their point it to teach the student something about algorithms - which he will not learn if solutions are just posted here, as Peter and David pointed out already.


Ping & DNS - updated with new look and Ping home screen widget
Peter Chase
Ranch Hand

Joined: Oct 30, 2001
Posts: 1970
Originally posted by AmarbirGSP Khokhar:
complexity is cubic...


Cubic's for pocket calculators. My solution (posted way above) has factorial complexity! That'll tax your computer.
Svend Rost
Ranch Hand

Joined: Oct 23, 2002
Posts: 904
Originally posted by Peter Chase:

Cubic's for pocket calculators. My solution (posted way above) has factorial complexity! That'll tax your computer.

LOL.. thanks for introducing me to the term "bogosort" by the way

edit:btw= by the way
[ July 20, 2007: Message edited by: Svend Rost ]
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
AmarbirGSP - what sort of name is that, anyway? What's that "GSP" doing there? If it's a company name, it shouldn't be part of your disyplay name at all. Please see our display name policy and edit your display name so it looks like the name of a person, not a corporation.

Now, this is a homework assignment, right? Have you had any ideas of your own at all on this? Or done any work to take one of these sample ideas and improve on it? It looks like you're just sitting and waiting for someone to provide you with a solution. You will learn a lot more if you do some work yourself here.

["AmarbirGSP"]: Actually the motive is to keep the complexity linear..and you are not allowed to sort the array.

Linear with respect to what? The length of the array (call it L), or N, the number of the element to find? Or some combination? It's pretty easy to write something with two loops (nested) and complexity O(L*N). I'm pretty sure it's also possible to write something that's O(L * log N) by building a tree of some sort which effectively sorts just N elements, while leaving the remainder unsorted. I can't think of any solutions that don't effectively sort elements 1 to N at least. I'm not sure what you think is "good enough" here; you may need to refine what you mean by "linear".


"I'm not back." - Bill Harding, Twister
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Ashok Mor - first, please pay attention to David O'Meara's point about not posting complete solutions. Then, if you do want to post some code, please use code tags to preserve the indentation of your code. I've added them to your first post above. I didn't add them to the second, because when I looked at the source of that post there is no indentation at all. (!) As far as I can tell it's just a repeat of the first post - did you make any changes? I suggest editing your second post (use the ) to either add code tags and indentation, or delete the post entirely if it's just a copy of the first. Thanks.
Manuel Leiria
Ranch Hand

Joined: Jul 13, 2007
Posts: 171
Originally posted by Ashok Mor:


Complex requirements always have complex solutions, think positive.



Ashok Mor

I don't agree.
Occam's razor
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 39575
    
  27
Originally posted by Ashok Mor:
Complex requirements always have complex solutions


Originally posted by Manuel Leiria:
I don't agree.
Occam's razor


Occam's Razor states that the simplest solution is to be preferred - but the simplest solution could still be very complex.
Anand Hariharan
Rancher

Joined: Aug 22, 2006
Posts: 257

<reformatted>

Originally posted by AmarbirGSP Khokhar:

e.g int a[] = new int[]{10,19,2,3,1,98,75,65,8500,850000};

and I have to find Fifth largest element (65) in the array a[] without sorting the array.



Look up "selection" or "partition" in your algorithm textbook.


Actually the motive is to keep the complexity linear..and you are not allowed to sort the array.


FWIW, the algorithm is indeed linear, but the constant factor is so large that unless you have more than say 66,000 elements in your array, you might just as well (or better) off using a sort.

HTH,
- 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
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

Everybody, Please UseRealWords!

I was trying to hint this with my initial 'frnz' remark, but 'R', 'FWIW', 'HTH' and all of the rest of them make posts harder to read. Please err on the side of legibility.

Dave
Ashok Mor
Ranch Hand

Joined: Jul 17, 2007
Posts: 43
Originally posted by Ulf Dittmer:


Occam's Razor states that the simplest solution is to be preferred - but the simplest solution could still be very complex.


Ulf Dittmer, You are right.
Manuel Leiria
Ranch Hand

Joined: Jul 13, 2007
Posts: 171
Originally posted by Ashok Mor:


Ulf Dittmer, You are right.


Perhaps I didn't explained myself right. What I meant was that amongst several solutions, usualy the simplest one is the right one
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
This discussion was getting derailed from the original question, so I've transferred many of the posts here. If you have any further comments on our "Use Real Words" policy, please put them in that other thread. This thread is for discussion of the original problem, finding the Nth largest element of an array without sorting. Thank you.
[ July 20, 2007: Message edited by: Jim Yingst ]
Amarbir Singh
Greenhorn

Joined: Jun 26, 2007
Posts: 20
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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Finding Nth Largest element of an array without sorting
 
Similar Threads
Nth Node from Last ???
Using real words (Was: Finding Nth Largest element of an array without sorting
arrays?
Largest/Greatest of n numbers
ArrayIndexOutOfBounds