Categories

Main
Database
Java
Microsoft.NET
Adabas
DB2
Informix
Microsoft SQL Server
MySQL
Oracle
Pervasive.SQL
PostgreSQL
Sybase
Other
ASP
ColdFusion
Crystal Reports
Delphi, C etc
JAVA
Microsoft.NET
Perl and the DBI
PHP
ANSI SQL
Unix Shell Scripts
Visual Basic
XML & XSLT
Corel Paradox
FileMaker
Microsoft Access
Microsoft Excel
Other PC Databases
Applications & Tools
Database Concepts & Design
EJB programming & troubleshooting
EJB design
General J2EE
XML & Web services
Web tier: servlets, JSP, Web frameworks
Performance and scalability
Industry news
TSS feedback
Mobicents Contributors
Mobicents Users
JSLEE Resource Adaptor Types
Planning JavaOne 2008
Sun Tech Days
Other Java conferences
Binary Web Services and XML
Metro and JAXB
GlassFish
GlassFish Plugins
Project jMaki
GlassFish WebTier
Mural
Java Development Tools
Java WS & XML Community News
JAXP
Java SE
6uN Early Access
Java Quick Starter
Java SE Snapshots: Project Feedback
JCK Forum
Feedback and Suggestions
JDK Distros
JDK Open Source
General JSR Discussion
JCP 2.6
JXTA Community Forum
ME Interest
ME Cool Apps
ME General Help
ME Feedback & Suggestions
ME Application Developer Interest
Blu-ray Disc Java
ME Developer Days
Squawk
Mobile Developer Alliance
OpenCable
LWUIT
JavaFX Script Language Discussion
OpenJFX General Discussion
Scene Graph
General Performance Discussion
Your Java Career
NetBeans 6.0
Servlets
JSP
JSF
Portals and Portlets
EJB and Other Java EE Technologies
Distributed Java
Object Relational Mapping
JDBC
Web Services
Swing / AWT / SWT / JFace
JNLP and Web Start
Java Micro Edition
Sockets and Internet Protocols
Threads and Synchronization
Performance
Applets
I/O and Streams
Other Java APIs
Game Development
Java in General (beginner)
Java in General (intermediate)
Java in General (advanced)
Programmer Certification (SCJP)
Developer Certification (SCJD)
Associate Certification (SCJA)
Web Component Certification (SCWCD)
EJB Certification (SCBCD)
Mobile Application Certification (SCMAD)
Architect Certification (SCEA)
Web Services Certification (SCDJWS)
XML Certification
Product and Other Certifications
Mock Exam Errata
Sun Certification Results
Authors' Corral
Book Reviews
Events
Bunkhouse Porch
Teachers' Lounge
Testing
OO, Patterns, UML and Refactoring
IDEs, Version Control and other tools
Ant, Maven and Other Build Tools
Linux / UNIX
Mac OS
HTML and JavaScript
XML and Related Technologies
Agile and Other Processes
General Computing
Security
Groovy
Scala
Other Languages
Struts
Application Frameworks
Other Open Source Projects
BEA/Weblogic
IBM/Websphere
Oracle/OAS
Apache/Tomcat
JBoss
Other Java Products and Servers
JavaRanch
Cattle Drive (java college)
Moderators Only
Trash Can
Jobs Offered
Jobs Wanted
Jobs Discussion
Meaningless Drivel
Programming Diversions
Blatant Advertising
Java Announcements
New To Java
Advanced Java
Java Applets
Networking
Threads and Synchronization
Java 2D
AWT / Swing
SWT / JFace
CLDC and MIDP
CDC and Personal Profile
Sun Java Wireless Toolkit
Enterprise JavaBeans
JavaServer Pages (JSP) and JSTL
Java Servlet
JavaServer Faces
Web Frameworks
Database
XML
Lucene
NetBeans
Eclipse
IntelliJ IDEA
JCreator
Other IDEs
Java Tutorials
Java Tips
Jobs Discussion
Jobs Offered
Jobs Wanted
Professional Certification
Forum Lobby
Java Blogs
Introductions
Reviews / Advertising
Suggestions & Feedback

Resources

Java Database
Linux
Coding
Mobile
Hardware
Software Development
Software Development
iOS,OS X
iOS,OS X
ORACLE
IBM DEVELOPER
IBM DEVELOPER
MSDN
MSDN


Tags

Java in General (beginner)

Java in General (beginner) No question too simple or small . . .

Finding Nth Largest element of an array without sorting


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.

   
   
   
   
   
      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?--------------------Only those people who do nothing do not make mistakes.[JavaRanch FAQ] [HowToAskQuestionsOnJavaRanch] [Blog] [Book Promotions] [DbTamer]

   
   
   
 
   
      It should be something like this (I didn't tried so it might have errors)code:int[] fred = {0, 5, 7, 3, 20, 3, 44};int max = 0;for(int i = 0; i < fred.length; i++){if(i == 0)max = i;else{if(fred[i] > max)max = fred[i];}}System.out.println(max);}--------------------Manuel Leiria --------------Peace cannot be kept by force; it can only be achieved by understanding.              Albert Einstein

   
   

   
   
      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,

   
   

   
   
      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.

   
   

 
   
      Original array should not changed.So ,before you find the Nth largest numberWhy don't you make a copy of that array and sort that arraypick out the Nth largest number from the copy array..This way you are not doing any change in the original array..

   
   

   
   
      Dear vanlalhmangaiha,The prerequisite is you are not allowed to explicitly sort the array...you have to do it without sorting...

   
   
   
   
   
      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 methodcompareTo()of the elements if they ALL implement theComparableinterface or use aComparatoryou will have provided to the method as a paramater.The "Comparable version" of the method could look something like this:code:public <E extends Comparable<E>> E getMaximumElement(List<E> list){E maximumElement = null;for(E currentElement : list){if(maximumElement == null){maximumElement = currentElement;}else{if(maximumElement.compareTo(currentElement) > 0){maximumElement = currentElement;}}}return maximumElement;}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)

   
   

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

   
   

   
   
      Hi AmarbirGSP Khokhar,Please run this demo.............U should give nth value for out side as a coomand line......... like "Java  NthLargest  4"code: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[ July 19, 2007: Message edited by: Jim Yingst ]

   
   
   
 
   
      Here you gocode:public static void main(String[] args) {int[] fred = { 60, 5, 7, 3, 20, 3, 44 };int[] tmp = new int[fred.length];go(fred, 1, tmp, 3);}public static void go(int[] fred, int cnt, int[] tmp, int whatPosition) {int max = 0;int currentPosition = 0;for (int i = 0; i < fred.length; i++) {if (i == 0)max = fred[i];else {if (fred[i] > max) {max = fred[i];currentPosition = i;}}}System.arraycopy(fred, 0, tmp, 0, fred.length);tmp[currentPosition] = 0;cnt++;if(cnt != whatPosition)go(tmp, cnt, tmp, whatPosition);else{for (int i = 0; i < tmp.length; i++) {if (i == 0)max = tmp[i];else {if (tmp[i] > max) {max = tmp[i];}}}System.out.println(max);}}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 ]--------------------Manuel Leiria --------------Peace cannot be kept by force; it can only be achieved by understanding.              Albert Einstein

   
   

 
   
      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 ofbogosortalgorithm? 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. #:^P

   
   
   
 
   
      quote: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.--------------------Manuel Leiria --------------Peace cannot be kept by force; it can only be achieved by understanding.              Albert Einstein

   
   

 
   
      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...code:public static void main(String args[]){int nvalue=Integer.parseInt(args[0]);int[] fred = {0, 5, 7, 54, 20, 3, 44};TreeSet tree_set=new TreeSet();for(int i=0;i<fred.length;i++){tree_set.add(new Integer(fred[i]));}System.out.println(""+tree_set);ArrayList arr=new ArrayList(tree_set);if(nvalue>arr.size()){System.out.println("Nth value too big");}else{System.out.println("Nth Largest Number: "+arr.get(nvalue-1));}}}

   
   
   
   
   
      quote: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

   
   

   
   
      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

   
   

   
   
      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 advancecheers

   
   
   
 
   
      quote: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...code:public static void main(String args[]){int nvalue=Integer.parseInt(args[0]);int[] fred = {0, 5, 7, 54, 20, 3, 44};TreeSet tree_set=new TreeSet();for(int i=0;i<fred.length;i++){tree_set.add(new Integer(fred[i]));}System.out.println(""+tree_set);ArrayList arr=new ArrayList(tree_set);if(nvalue>arr.size()){System.out.println("Nth value too big");}else{System.out.println("Nth Largest Number: "+arr.get(nvalue-1));}}}I think it should becode:System.out.println("Nth Largest Number: " + arr.get(arr.size() - nvalue));code:System.out.println("Nth Largest Number: "+arr.get(nvalue-1));--------------------Manuel Leiria --------------Peace cannot be kept by force; it can only be achieved by understanding.              Albert Einstein

   
   

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

   
   

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

   
   

   
   
      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

   
   

 
   
      quote: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 ... cheersWhy dont you provide some code yourself? Try to experiment abit.. it's my expirience that you learn most by doing it yourself.

   
   

   
   
      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.

   
   

   
   
      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

   
   
   
   
   
      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 ]--------------------Only those people who do nothing do not make mistakes.[JavaRanch FAQ] [HowToAskQuestionsOnJavaRanch] [Blog] [Book Promotions] [DbTamer]

   
   

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

   
   

   
   
      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

   
   
   
 
   
      quote:Originally posted by Ashok Mor:But think about your requirements, all your requirements are so strange likeThat's what homework assignments are like. Their point it to teach the student something about algorithms - which he willnotlearn if solutions are just posted here, as Peter and David pointed out already.--------------------BlogLearn something new on the Java platform: Scheme Prolog

   
   

 
   
      quote:Originally posted by AmarbirGSP Khokhar:complexity is cubic...Cubic's for pocket calculators. My solution (posted way above) hasfactorialcomplexity! That'll tax your computer.--------------------Betty Rubble? Well, I would go with Betty... but I'd be thinking of Wilma. #:^P

   
   

 
   
      quote:Originally posted by Peter Chase:Cubic's for pocket calculators. My solution (posted way above) hasfactorialcomplexity! That'll tax your computer.LOL.. thanks for introducing me to the term "bogosort" by the wayedit:btw= by the way[ July 20, 2007: Message edited by: Svend Rost ]

   
   
   
   
   
      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 ourdisplay name policyandedit your display nameso it looks like the name of a person, not a corporation.Now, this is a homework assignment, right?  Have you hadanyideas 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 ofanysolutions 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".

   
   
   
   
   
      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, pleaseuse code tagsto 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 isnoindentation 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.

   
   
   
 
   
      quote:Originally posted by Ashok Mor:Complex requirements always have complex solutions, think positive.Ashok MorI don't agree.Occam's razor--------------------Manuel Leiria --------------Peace cannot be kept by force; it can only be achieved by understanding.              Albert Einstein

   
   
   
 
   
      quote:Originally posted by Ashok Mor:Complex requirements always have complex solutionsquote:Originally posted by Manuel Leiria:I don't agree.Occam's razorOccam's Razor states that the simplest solution is to be preferred - but the simplest solution could still be very complex.--------------------BlogLearn something new on the Java platform: Scheme Prolog

   
   

 
   
      <reformatted>quote: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.quote: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

   
   
   
   
   
      Everybody, PleaseUseRealWords!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--------------------Only those people who do nothing do not make mistakes.[JavaRanch FAQ] [HowToAskQuestionsOnJavaRanch] [Blog] [Book Promotions] [DbTamer]

   
   

   
   
      quote: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.

   
   
   
 
   
      quote: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--------------------Manuel Leiria --------------Peace cannot be kept by force; it can only be achieved by understanding.              Albert Einstein

   
   
   
   
   
      This discussion was getting derailed from the original question, so I've transferred many of the postshere.  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 ]

   
   

   
   
      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


Related Links

Matrix
Check for String
package problem
Creating new object
abstract
How to find out cgi variables in java?
Date(yy,mm,dd)
Date calculation
Creating directory using mkdirs()
use of interfaces
abstract class
Simple problem with html
fundamental uses of java and different applications
Timer keeps program from exiting
One query about inheritance ??
Need help with add() method