Results 1 to 16 of 16
Like Tree5Likes
  • 1 Post By jim829
  • 1 Post By gimbal2
  • 1 Post By JosAH
  • 1 Post By jim829
  • 1 Post By jim829

Thread: Algorithm for determining the maximum value in an array list

  1. #1
    FOX427 is offline Member
    Join Date
    Jun 2011
    Posts
    52
    Rep Power
    0

    Default Algorithm for determining the maximum value in an array list

    Hi All! i am doing review exercises from Java book, basically here is a given code for optimal solution in the book:
    Java Code:
    public BankAccount5 getMaximum()
       {
          if (accounts.size() == 0) return null;
          BankAccount5 largestYet = accounts.get(0);
          for (int i = 1; i < accounts.size(); i++) 
          {
             BankAccount5 a = accounts.get(i);
             if (a.getBalance() > largestYet.getBalance())
                largestYet = a;
          }
          return largestYet;
    now i need to use alternative approach by initializing largestYet with null and go through every element in the list, then compare both methods, so far I am here:
    Java Code:
    public BankAccount5 getMaximum2()
       {
    	   if (accounts.size() == 0) return null;
    	   BankAccount5 largestYet = null;
    	  for (int i = 0; i < accounts.size(); i++)
    	   {
    		   BankAccount5 element = accounts.get(i);
    		   if(.........)
    			   largestYet = element;
    		   
    	   }
    	   return largestYet;
       }
    can some1 give me a hint how to implement if statement so I could finish this code?

  2. #2
    AlexHail is offline Member
    Join Date
    Jul 2013
    Posts
    5
    Rep Power
    0

    Default Re: Algorithm for determining the maximum value in an array list

    Your hint is...

    Since largestYet is set to null you really cant compare it to anything because there is nothing to compare... so when checking all the balances, put the first value you find into a variable. Then check all the other balances in your list against that first variable, set the largest of them to your largestYet and return.

    Let me know if you have any questions, post progress

  3. #3
    ShadowWalker is offline Senior Member
    Join Date
    Mar 2013
    Location
    Greece
    Posts
    112
    Rep Power
    0

    Default Re: Algorithm for determining the maximum value in an array list

    The best Way to find the Max of an ArrayList is to use Sort().. just sort the arrayList and get the first or the last item..

    Java Code:
    Collections.sort(arrayList); // Sort the arraylist
    arrayList.get(arrayList.size()); //gets the last item, largest for an ascending sort

  4. #4
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,417
    Rep Power
    5

    Default Re: Algorithm for determining the maximum value in an array list

    That is a horrible way to get the maximum value because even the best sorting algorithm, on average, is worse than O(n) in efficiency.

    A better way is to assign the first value in the list to some variable max. Then iterate over the list starting with the next value and just doing a simple compare, replacing max with the current value depending on the outcome of the comparison.

    Regards,
    Jim
    Last edited by jim829; 07-29-2013 at 05:20 PM.
    gimbal2 likes this.
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  5. #5
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    3,758
    Rep Power
    5

    Default Re: Algorithm for determining the maximum value in an array list

    I agree with you in general, but I do want to note that performance should not be a definitive reason to choose to not do something. Yes a sort is slow but a sort on a small collection is still fast, so if it is simple code to sort and get the last element to get what you want, why not?
    jim829 likes this.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  6. #6
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,417
    Rep Power
    5

    Default Re: Algorithm for determining the maximum value in an array list

    You've got a valid point. And if the desire was to obtain something for which writing an efficient routine would be very time consuming as opposed to using a combination of the available classes in the JDK API I would be all for it. But finding a maximum value in a list or array is trivial. And I also took issue with someone saying that using a sort is the "best way." If the poster had said that using a sort was a more convenient way of doing it then the efficiency issue would not have entered into the picture.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,375
    Blog Entries
    7
    Rep Power
    20

    Default Re: Algorithm for determining the maximum value in an array list

    If that 'largestYet' element is set to null, the expression in the if-clause can be:

    Java Code:
    if (largestYet == null || largestYet.compareTo(element) < 0)
       largestYet= element;
    kind regards,

    Jos
    jim829 likes this.
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    ShadowWalker is offline Senior Member
    Join Date
    Mar 2013
    Location
    Greece
    Posts
    112
    Rep Power
    0

    Default Re: Algorithm for determining the maximum value in an array list

    gimbal2 really, the sort way isn't better than comparing each item again and again..?? hmmm interesting..
    i believed that using sort method makes the code more clear and not necessary faster but more good looking..
    hmm horrible way ... hmm thx for info.. i didn't know that.

  9. #9
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,417
    Rep Power
    5

    Default Re: Algorithm for determining the maximum value in an array list

    Quote Originally Posted by ShadowWalker View Post
    the sort way isn't better than comparing each item again and again..?? hmmm interesting.
    How do you think you can do a sort without comparing items? Usually, sorting algorithms do more than a single pass thru the array. I woud also say that they are more computationally intensive than just finding a maximum value of a list.
    ...horrible way
    And I said that, not Erik.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  10. #10
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,417
    Rep Power
    5

    Default Re: Algorithm for determining the maximum value in an array list

    After rethinking this I believe my use of the word "horrible" to describe the process was a poor choice. Although I clearly do not believe using sort is the most efficient method the one you posted certainly works in a pinch and may be more convenient. Ironically, several days before your post I had read the article Erik (gimbal2) had posted. It was very enlightening and goes to the point of his comments on your method. I post it again for reference. It was also very enlightening to learn that in certain situations the Java compiler uses StringBuilder to optimize concatenation of String objects.

    Regards,
    Jim

    The Developer Insight Series, Part 1: Write Dumb Code -- Advice From Four Leading Java Developers
    ShadowWalker likes this.
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  11. #11
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    3,758
    Rep Power
    5

    Default Re: Algorithm for determining the maximum value in an array list

    Quote Originally Posted by jim829 View Post
    And I said that, not Erik.
    I thought I was going mad!

    But nope - just bald.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  12. #12
    ShadowWalker is offline Senior Member
    Join Date
    Mar 2013
    Location
    Greece
    Posts
    112
    Rep Power
    0

    Default Re: Algorithm for determining the maximum value in an array list

    Thx for the informations.. i must change a lot of things in my codes :P

  13. #13
    FOX427 is offline Member
    Join Date
    Jun 2011
    Posts
    52
    Rep Power
    0

    Default Re: Algorithm for determining the maximum value in an array list

    to AlexHail
    But isn't it the same as first approach that is listed above? I forgot to mention that book says we need to test whether largestYet is still null. here is what I have now:

    Java Code:
    public BankAccount5 getMaximum2()
       {
           if (accounts.size() == 0) return null;
           BankAccount5 largestYet = null;
          for (int i = 0; i < accounts.size(); i++)
           {
               BankAccount5 element = accounts.get(i);
               if(largestYet==null || largestYet.getBalance() < element.getBalance())
                   largestYet = element;
                
           }
           return largestYet;
       }
    it seems to be working fine...of course second approach seems to be less efficient as we need to redundant checks every time iteration happens...Thank you for your willingness to help! :)
    Last edited by FOX427; 07-30-2013 at 08:19 PM.

  14. #14
    FOX427 is offline Member
    Join Date
    Jun 2011
    Posts
    52
    Rep Power
    0

    Default Re: Algorithm for determining the maximum value in an array list

    Jos, I did something similar:
    public BankAccount5 getMaximum2()
    {
    if (accounts.size() == 0) return null;
    BankAccount5 largestYet = null;
    for (int i = 0; i < accounts.size(); i++)
    {
    BankAccount5 element = accounts.get(i);
    if(largestYet==null || largestYet.getBalance() < element.getBalance())
    largestYet = element;

    }
    return largestYet;
    }
    but I always thought that you can use compareTo method only with strings???

  15. #15
    FOX427 is offline Member
    Join Date
    Jun 2011
    Posts
    52
    Rep Power
    0

    Default Re: Algorithm for determining the maximum value in an array list

    Thank you very much to everyone! I didn't expect that a lot of people will discuss this small exercise review. Appreciate. :)

  16. #16
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,417
    Rep Power
    5

    Default Re: Algorithm for determining the maximum value in an array list

    Actually, I just noticed something. It appears that since the bank account objects are stored in a List then the objects must implement the Comparable interface or a Comparator will need to be passed using a different method call. Otherwise, the Collections.sort() method will generate a compile-time error.

    Regards,
    Jim
    gimbal2 likes this.
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

Similar Threads

  1. Algorithm for finding max and min in an array.
    By Shyamz1 in forum New To Java
    Replies: 4
    Last Post: 10-04-2011, 10:45 PM
  2. Linked List, Array List time complexity
    By Rick99771977 in forum New To Java
    Replies: 4
    Last Post: 08-18-2011, 05:37 AM
  3. Replies: 6
    Last Post: 08-26-2010, 02:26 PM
  4. To find the Maximum and Minimum in an Array of Strings
    By luscious in forum JavaServer Pages (JSP) and JSTL
    Replies: 9
    Last Post: 07-31-2008, 01:51 PM
  5. Maximum size of an array
    By Hasan in forum New To Java
    Replies: 1
    Last Post: 05-20-2007, 11:11 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •