aspose file tools*
The moose likes Java in General and the fly likes Largest/Greatest of n numbers Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Largest/Greatest of n numbers" Watch "Largest/Greatest of n numbers" New topic
Author

Largest/Greatest of n numbers

Sudhir Srinivasan
Ranch Hand

Joined: Jun 08, 2011
Posts: 90

Hi,

The program takes input from the user,

- a number specifying the total size of the array[max. size 11 in this case]
- and the number for each array element,

sorts the numbers entered and writes to screen the greatest/largest number from them.


The code works just fine - output 1 below the code - when the array variable 'arr' is dimensioned with an index value [line no.10]. However, if the variable is declared as after taking the initial user input[value representing array size stored in num], the program executes upto the sorting part of the code but throws ArrayIndexOutOfBoundsException - kindly refer output 2 below the code - when encountering the comparison part of the program [lines 54-56].

Due to the array size dimensioned with a variable index value as opposed to with a static value, the for loop in lines 54-56 increments array element beyond the scope of the array thereby resulting in the above mentioned exception.

Could any of the experts suggest a workaround to this.

thanks,
Sudhir





output 1:
----------

init:
deps-jar:
compile-single:
run-single:
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
5
You have input: 5
Enter value:
5000
Value entered is: 5000
Enter value:
100
Value entered is: 100
Enter value:
350
Value entered is: 350
Enter value:
60
Value entered is: 60
Enter value:
400
Value entered is: 400
Numbers input sorted:
60
100
350
400
5000
Greatest of numbers input is: 5000
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
8
You have input: 8
Enter value:
1000
Value entered is: 1000
Enter value:
100
Value entered is: 100
Enter value:
300
Value entered is: 300
Enter value:
20
Value entered is: 20
Enter value:
90
Value entered is: 90
Enter value:
60
Value entered is: 60
Enter value:
45
Value entered is: 45
Enter value:
55
Value entered is: 55
Numbers input sorted:
20
45
55
60
90
100
300
1000
Greatest of numbers input is: 1000
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
0
BUILD SUCCESSFUL (total time: 58 seconds)


output 2:
----------
init:
deps-jar:
compile-single:
run-single:
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
4
You have input: 4
Enter value:
300
Value entered is: 300
Enter value:
50
Value entered is: 50
Enter value:
75
Value entered is: 75
Enter value:
20
Value entered is: 20
Numbers input sorted:
20
50
75
300
java.lang.ArrayIndexOutOfBoundsException: 4
at TestGreatestnNum.main(TestGreatestnNum.java:49)
BUILD SUCCESSFUL (total time: 16 seconds)
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11494
    
  16

1) the best way to figure this out is to put System.out.println statements in your code.

2) the code you posted won't run:

C:\slop>java TestGreatestnNum
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
5
You have input: 5
Enter value:
java.util.InputMismatchException
at java.util.Scanner.throwFor(Unknown Source)
at java.util.Scanner.next(Unknown Source)
at java.util.Scanner.nextInt(Unknown Source)
at java.util.Scanner.nextInt(Unknown Source)
at TestGreatestnNum.main(TestGreatestnNum.java:29)


3) I'm not sure the code you posted matches the error/is what is being run. The error says the problem was on line 49, but line 49 of the code you posted is simply a closing brace.



There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19781
    
  20

The error Fred's getting can be solved by changing line 23 to use the actual line break, not \n. Fred's probably using Windows, which uses \r\n. That causes the \r to be part of the match, causing the number to not be an int.
Anyway, I tried it and never got an exception. There is a problem however; arr is defined to store at most 11 elements on line 10, and it's never changed afterwards. That means that your code will never allow more than 11 numbers. You can fix this by removing line 10, and adding the following line after line 20:
You'll then get another error for line 55 which is caused by j going up to num - 1 but you use j+1 inside the loop.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Madhan Sundararajan Devaki
Ranch Hand

Joined: Mar 18, 2011
Posts: 312

You may do the following.
1. Move line number 10 to line number 24
2. Move line 54 below current line number 34
3. Comment or remove current lines 35 to 57
4. Add the following lines, after the current line number 57


S.D. MADHAN
Not many get the right opportunity !
Sudhir Srinivasan
Ranch Hand

Joined: Jun 08, 2011
Posts: 90

Thank you Madhan. Your suggestions

You may do the following.
1. Move line number 10 to line number 24
2. Move line 54 below current line number 34
3. Comment or remove current lines 35 to 57
4. Add the following lines, after the current line number 57


and the use of the predefined arrays class/sort method

1. Arrays.sort(arr);
2. result = arr[arr.length-1];


has certainly reduced my code length[sorting the numbers and then writing the result to screen] and also finds the greatest for any no. of values input.

Below is the modified code and its output.

regards,
Sudhir




output:
----------

init:
deps-jar:
compile-single:
run-single:
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
8
You have input: 8
Enter value:
3000
Value entered is: 3000
Enter value:
1500
Value entered is: 1500
Enter value:
500
Value entered is: 500
Enter value:
750
Value entered is: 750
Enter value:
900
Value entered is: 900
Enter value:
200
Value entered is: 200
Enter value:
50
Value entered is: 50
Enter value:
450
Value entered is: 450
Greatest of numbers input is: 3000
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
15
You have input: 15
Enter value:
300
Value entered is: 300
Enter value:
100
Value entered is: 100
Enter value:
200
Value entered is: 200
Enter value:
500
Value entered is: 500
Enter value:
150
Value entered is: 150
Enter value:
50
Value entered is: 50
Enter value:
75
Value entered is: 75
Enter value:
25
Value entered is: 25
Enter value:
40
Value entered is: 40
Enter value:
30
Value entered is: 30
Enter value:
80
Value entered is: 80
Enter value:
700
Value entered is: 700
Enter value:
35
Value entered is: 35
Enter value:
85
Value entered is: 85
Enter value:
90
Value entered is: 90
Greatest of numbers input is: 700
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
0
BUILD SUCCESSFUL (total time: 1 minute 23 seconds)
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19781
    
  20

I wouldn't sort the array just to find the largest value. First of all, if this is a homework assignment, it probably defies the purpose of the assignment. Secondly, sorting is at least an O(n log n) operation, whereas a simple loop is an O(n) operation. That means that as the arrays grow larger, the simple loop becomes more and more efficient compared to the sorting.

If you don't know what O(n log n) and O(n) mean, please check out http://en.wikipedia.org/wiki/Big_O_notation.
Wouter Oet
Saloon Keeper

Joined: Oct 25, 2008
Posts: 2700

Since you only need the greatest value you could also just compare the previous value with the new value and store the greatest value.


"Any fool can write code that a computer can understand. Good programmers write code that humans can understand." --- Martin Fowler
Please correct my English.
Sudhir Srinivasan
Ranch Hand

Joined: Jun 08, 2011
Posts: 90

Rob Spoor wrote:First of all, if this is a homework assignment, it probably defies the purpose of the assignment.


The assignment was for finding the largest of 3 nos. For my learning, I extended the same by trying to find the largest of 'n' numbers input and therefore used the sorting.

Rob Spoor wrote:I wouldn't sort the array just to find the largest value.


Assuming array is dimensioned to 10 or 20 etc. and not num, without the sort, the for loop containing the comparison part of the code - result = arr[j] > arr[j+1] ? arr[j] : arr[j+1]; - would traverse the list only once comparing the previous array element with the current one and return the largest value for, say 3 numbers input, as shown

output 1:
------------
init:
deps-jar:
compile-single:
run-single:
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
3
You have input: 3
Enter value:
100
Value entered is: 100
Enter value:
50
Value entered is: 50
Enter value:
500
Value entered is: 500
Greatest of numbers input is: 500

If the array size grows to take in 7 values,

output 2:
-------------
init:
deps-jar:
compile-single:
run-single:
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
7
You have input: 7
Enter value:
1000
Value entered is: 1000
Enter value:
500
Value entered is: 500
Enter value:
700
Value entered is: 700
Enter value:
300
Value entered is: 300
Enter value:
150
Value entered is: 150
Enter value:
10
Value entered is: 10
Enter value:
600
Value entered is: 600
Greatest of numbers input is: 600
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
0
BUILD SUCCESSFUL (total time: 1 minute 3 seconds)

the comparison of arr[j] with arr[j+1] in this case returns 600 and not 1000 as the incrementor in the for loop moves the position of the previous and current array element such that,

for(int j = 0; j < num; j++) {

result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
arr[0] > arr[1] ? arr[0] : arr[1];
result = arr[0] containing 1000

result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
arr[1] > arr[2] ? arr[1] : arr[2];
result = arr[2] containing 700

result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
arr[2] > arr[3] ? arr[2] : arr[3];
result = arr[2] containing 700

result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
arr[3] > arr[4] ? arr[3] : arr[4];
result = arr[3] containing 300

result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
arr[4] > arr[5] ? arr[4] : arr[5];
result = arr[4] containing 150

result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
arr[5] > arr[6] ? arr[5] : arr[6];
result = arr[6] containing 600

}

Even if the array size is 3, the above logic returns the largest value as 75 instead of 300 for the following inputs (as opposed to 500 in output 1 as it happened to be the largest value of the array stored in array element arr[2] which is current value compared to previous value 50 of arr[1])

output 3:
------------

init:
deps-jar:
compile-single:
run-single:
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
3
You have input: 3
Enter value:
300
Value entered is: 300
Enter value:
50
Value entered is: 50
Enter value:
75
Value entered is: 75
Greatest of numbers input is: 75
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
0
BUILD SUCCESSFUL (total time: 22 seconds)

So, in the above 3 outputs, the absence of the for loops containing the sort

for(int i = 0; i < num; i++) { //for every pass
//In pass i, compare the first num-i elements with the next elements
for(int j = 0; j < num - 1; j++) {
if(arr[j] > arr[j+1]) { //comparison
int temp;
//swapping and ordering of elements
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}

ensures there is only one traversal of list and no subsequent passes for comparison and sorting.

Note: In the above loops, I think I've made a mistake. variable 'i' should be initialized to 1 and not 0.


Rob Spoor wrote:Secondly, sorting is at least an O(n log n) operation, whereas a simple loop is an O(n) operation. That means that as the arrays grow larger, the simple loop becomes more and more efficient compared to the sorting.


-- Got it, the rate of increase in running time of the sort is directly proportional to the increase in the volume of input data [array size]. Considering the precedence of the orders of growth, O(n) is certainly more efficient to O(n log n). But since the sort is required, i guess O(n log n) is not too bad given its position in the big-O order of growth.

However, if there is still a way to avoid the sort with just the loop(s), please show the alternative.


Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19781
    
  20

A sort is definitely not required; finding the maximum in a List or array really only requires one single loop. But you must loop after you have all the values, and store the maximum of all elements you already inspected as an intermediate value:
As you see, a single loop, and at the end max will be the maximum value in the array. There is no need of comparing each element to any element except the maximum you found so far.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40027
    
  28
Have you really read all the answers you have been given?
Sorting an array runs in at best O(nlogn) time and searching for the largest (or smallest) values runs in linear time = O(n)

If you still haven't got it working, I would make the following suggestions:
  • 1: Forget what you have done to date.
  • 2: Write down a series of numbers, and go through them by hand looking for the largest (or smallest) values.
  • 3: Write down exactly what you are doing, in words of one syllable.
  • 4: Now you have pseduocode, you can easily change that to real code
  • Hint: When you only have one number n, the smallest number seen to date is n, and the lrgest number seen to date is n. When you have two different numbers, that will change.
    Your while loop with while (number != 0) is a good way to proceed, as long as you are happy that 0 is a correct termination value.
    Sudhir Srinivasan
    Ranch Hand

    Joined: Jun 08, 2011
    Posts: 90

    Thank you Rob for your patience and answers. Your enhanced for loop


    1. int max = -1; // assuming you only have positive numbers
    2. for (int value: arr)
    3. {
    4. if (max < value) max = value;
    5. }


    certainly simplifies my earlier code and does away with the sort! As explained, from the single dimension array 'arr', each data element is copied and stored in 'value' and the largest of this compared to max.

    Thank you Campbell, your suggestions

    # If you still haven't got it working, I would make the following suggestions:
    1: Forget what you have done to date.
    # 2: Write down a series of numbers, and go through them by hand looking for the largest (or smallest) values.
    # 3: Write down exactly what you are doing, in words of one syllable.
    # 4: Now you have pseduocode, you can easily change that to real code
    Hint: When you only have one number n, the smallest number seen to date is n, and the lrgest number seen to date is n. When you have two different numbers, that will change.


    also brought about the much needed clarity as i was confused with my own code!!
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 40027
        
      28
    That for-each loop looks so much neater and more elegant, but I can see a possible enhancementThat means you start off guessing that the first value is the largest. You can do exactly the same for minimum; in fact it is probably best to do it in the same loop. You may wish to start with the subsequent values after my assignmentThat will give the correct values for any array size except a 0-length array, which will produce an ArrayOutOfBoundsException.
    Sudhir Srinivasan
    Ranch Hand

    Joined: Jun 08, 2011
    Posts: 90
    Campbell Ritchie wrote:That for-each loop looks so much neater and more elegant, but I can see a possible enhancement


    The suggested enhancement certainly works by initializing



    which assumes the max and min values is the first array element.

    Campbell Ritchie wrote:
    That means you start off guessing that the first value is the largest. You can do exactly the same for minimum; in fact it is probably best to do it in the same loop. You may wish to start with the subsequent values after my assignmentThat will give the correct values for any array size except a 0-length array, which will produce an ArrayOutOfBoundsException.


    So, for an array size of 4, the output is




    max = 1000(arr[0])
    min = 1000(arr[0])

    arr[1] arr[2] arr[3]
    1000 < 2000 2000 < 500 2000 < 750
    max = 2000 max = 2000 max = 2000

    1000 > 2000 1000 > 500 500 > 750
    min = 1000 min = 500 min = 500


    and for an array size of 10, the output is



    max=500(arr[0])
    min=500(arr[0])

    arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] arr[7] arr[8] arr[9]
    500 < 5000 5000 < 2500 5000 < 1000 5000 < 3200 5000 < 600 5000 < 450 5000 < 700 5000 < 225 5000 < 675
    max = 5000 max = 5000 max = 5000 max = 5000 max = 5000 max = 5000 max = 5000 max = 5000 max = 5000

    500 > 5000 500 > 2500 500 > 1000 500 > 3200 500 > 600 500 > 450 450 > 700 450 > 225 225 > 675
    min = 500 min = 500 min = 500 min = 500 min = 500 min = 450 min = 450 min = 225 min = 225

    many thanks,
    Sudhir




    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 40027
        
      28
    You're welcome and you have finally got it working.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Largest/Greatest of n numbers