In Section 5.3 Basic loop algorithms we learned some basic loop algorithms for summing, counting, averaging, and finding minimums and maximums. Those algorithms become a lot more useful now that we know enough to use them with arrays. For instance we can sum or average all the elements in an array of numeric values or count the number of elements of an array that meet some criteria.
Additionally there are some algorithms that are more specific to arrays such as those that operate on pairs of elements and algorithms that modify the order of elements in an array such as by reversing or rotating the elements within an array.
As we have seen before with loops, the accumulator pattern decribes loops that iterate through a set of values while accumulating values into a variable where the accumulation can take on various forms. For instance summing numbers is a form of accumulation. The accumulator pattern has four steps:
To apply this pattern to summing the elements of an array we just need to recognize that the values to loop through in step 2 are just the elements of the array. Since we need to process all the elements in the array to sum them and don’t care about their positions, this is a great use for an enhanced for loop. And we can compute the average by dividing the sum by the array’s length. For example:
int[] values = { 6, 2, 1, 7, 12, 5 };
double sum = 0;
for (int val : values) {
sum += val;
}
double average = sum / values.length;
System.out.println("Sum: " + sum + "; Average: " + average);
Activity6.3.1.
The following program has the correct code to return the average of the first 3 items in the array a, but the code is mixed up. Drag the blocks from the left into the correct order on the right. You will be told if any of the blocks are in the wrong order or are indented incorrectly.
public static double avg3(int[] a)
{
---
double total = 0;
---
for (int i = 0; i < a.length && i < 3; i++)
{
---
total = total + a[i];
---
} // end for
return total / 3;
---
} // end method
Subsection6.3.2Minimizing, maximizing, and counting
As you may recall from Section 5.3 Basic loop algorithms the basic pattern for finding the minimum or maximum value in a sequence is also an accumulator pattern like summing but rather than adding each value into a running total we instead put each smaller (or larger) value we see into our accumulator variable. If we want to find the smallest value in an array we can use a very similar pattern with an enhanced for loop.
// assume numbers is an int[] variable
int min = numbers[0];
for (int num : numbers) {
min = Math.min(min, num);
}
But we can do fancier versions of finding the extreme values in an array. Suppose we had an array of String values containing people’s names and wanted to find the longest one. In this case we will compare the lengths of the values in the array but save the value. We’ll probably need to use an explicit if since there isn’t a convenient method like Math.max that we can pass two String arguments and get back the longer one. Maybe something like this:
// Assume names is a String[] variable containing names
String longest = names[0];
for (String name : names) {
// Check if the new name is longer than the longest we've seen
if (name.length() > longest.length()) {
// Save the new name if it's longer
longest = name;
}
}
Activity6.3.2.
The following method has the correct code to return the largest value in an integer array called vals (an instance variable of the current object), but the code is mixed up. Drag the blocks from the left into the correct order on the right and indent them correctly as well. You will be told if any of the blocks are in the wrong order or not indented correctly.
public int getLargest()
{
---
int largest = vals[0];
---
for (int item : vals)
{
---
if (item > largest)
{
---
largest = item;
---
} // end if
---
} // end for
return largest;
---
} // end method
The code below finds the minimum (smallest element) in an array. Try it in the Java visualizer with the CodeLens button. Can you change it to find the maximum element instead? Can you also compute the average of the elements?
Related to minimizing and maximizing algorithms are counting algorithms where we want to count the number of values that have some particular property. In counting algorithms we also use an if statement but rather than storing new values when we see a larger or smaller one, we instead increment a count whenever we see a value that meets our criteria.
For instance, suppose we wanted to count how many names in our array were longer than ten characters. Compare the code below to the previous maximizing code.
// names is still a String[] variable containing names
int count = 0;
for (String name : names) {
if (name.length() > 10) {
count++;
}
}
In this case our accumulator variable is the int count. And we “accumulate” into it with the ++ operator but only when we see a String longer than ten characters.
The following program segment should count the number of elements in the array that are even using an enhanced for each loop. But, the blocks have been mixed up. Drag the blocks from the left and put them in the correct order on the right. Click the Check button to check your solution.
When we’re summing, minimizing, maximizing, and counting we have to look at every element in the array in order to get our final answer. Searching algorithms often don’t have to look at every elemement because their goal is to find one element that meets some criteria; as soon as we find an element that meets the criteria we’re done and don’t need to look at any more values. It’s like when you’re looking for your keys—there’s a long list of places you can look but as soon as you find them you stop. Which is why your keys are always in the last place you look.
The best way to write a searching algorithm is to put the loop into a method so that we can return from the method as soon as we find a value that meets our criteria. Returning from a method will break us out of the loop immediately, even if the loop would otherwise have run for more iterations. Here’s a method that returns the first name longer than ten characters in the array it is passed.
public static String findLongName(String[] names) {
for (String name : names) {
if (name.length() > 10) {
return name;
}
}
return null;
}
When this method runs it will return the first name in the array that is longer than ten characters. There may be many long names in the array but the goal of this method is just to find the first one. Note the return null at the end of the method. Because the return type of the method is String we have to return something even if we didn’t find any name that met our criteria in the array. Returning null is a traditional way to deal with that situation and makes some sense since it indicates “no object”. That is, the method did not find any actual String longer than ten characters. There are some problems with this idiom and Java gives some better ways to handle this kind of situation but they are beyond the scope of this course. If we were searching for a value in a an array of some primitive type, we couldn’t return null but would have to return some other distinguished value that would not be a possible actual value to be found. For instance methods that are intended to searching in an array of positive int values, often use -1 as a distinguished value.
Note that when searching for an element, while we return from inside the if when we find what we’re looking for, if we don’t find it we need to keep looking and only return null or our other distinguished value after the loop has completed.
Given that array is an array of integers and target is an integer value, which of the following best describes the conditions under which the following code segment will return false?
Yes, the loop returns as soon as checking the first element, whether it is equal to target or not. It needs to check the whole array before returning false. The else statement should not be included.
Whenever array contains any element which equals target.
This would be true if the else statement was not there, but it returns false right away after just checking the first element instead of going through all of the elements to makes sure none of them are equal to target.
Given that array is an array of integers and target is an integer value, which of the following best describes the conditions under which the following code segment will return true?
This would be true if temp was only set to the result of checking if the current element in the array is equal to target when it is false. But, it is reset each time through the loop.
Whenever the last element in array is equal to target.
The variable temp is assigned to the result of checking if the current element in the array is equal to target. The last time through the loop it will check if the last element is equal to val.
Whenever only 1 element in array is equal to target.
What is wrong with the code below? The first time through the loop it will start with the element at index 0 and check if the item at the array index equals the passed target string. If they have the same characters in the same order it will return 0, otherwise it will return -1. But, it has only processed one element of the array. How would you fix the code to work correctly (process all array elements before returning)?
In searching algorithms we’re looking for one value that meets some criteria, like being more than ten characters long. A pair of related questions that we can ask about an array is do any elements of the array meet some criteria or do all elements meet it.
The algorithms to answer these questions are similar to the searching algorithm but instead of returning the value we from in the array, we return a boolean value that answers the question. On the AP exam they will frequently provide a method to use to test the criteria so all you’ll have to do is write the right method structure.
As with a searching algorithm, these work best in a method so we can use return to break out of the loop as soon as we know the answer. One way to think about these is as doing a search and using the fact of whether you found what you were looking for to answer the any or all question. Obviously if any item matches the criteria and you search for that criterial you’ll find one. So an any method is structured very similar to a search:
// Assume hasProperty is a method that tests the criteria we care about
// and returns a boolean when the value it is passed has the property.
public static boolean anyHasProperty(int[] values) {
for (int val : values) {
if (hasProperty(val)) {
return true;
}
}
return false;
}
The difference between this method and a search method just just in the return values: at the point where a search method would return the value it found, we return true, and where a search method would return the distinguished “not found” value, such as null, we return false to indicate that no elements of the array met the criteria.
You might think that to check whether all elements of an array meet some criteria you’d have to loop through the whole array and look at them all. It’s right there in the name, right? However, we can flip things around and realize that saying all the elements meet some criteria is the same as saying there is no element that doesn’t meet the criteria. In other words, if we can find just one counter example then we know not all the elements meet the criteria. So the all pattern is actually almost the same as the any pattern, we just test the opposite condition: !hasProperty(value) rather than hasProperty(value) and then swap the return values, false for true and vice versa:
// Assume hasProperty is a method that tests the criteria we care about
// and returns a boolean when the value it is passed has the property.
public static boolean allHaveProperty(int[] values) {
for (int val : values) {
if (!hasProperty(val)) {
return false;
}
}
return true;
}
Activity6.3.9.
Write the method allOdd to return true if all the values in the array are odd. First write the helper function isEven to return true or false for one value, using %.
Sometimes we need to go beyond testing criteria against individiual elements of the array and test facts about relationships between elements within the array. For instance, suppose we had a sorted array so the elements went from smallest to largest. In a sorted array elements with the same value will be next to each other in the array so we can test whether there are any duplicate elements by looping through the array and checking all the pairs at adjacent indices:
// check for duplicates next to each other
public static boolean anyDuplicatesInSorted(int[] values) {
for (int i = 0; i < values.length - 1; i++) {
if (values[i] == values[i + 1]) {
return true;
}
}
return false;
}
There are a couple things to note about this loop. First off, we need to use a regular for loop since we need an index variable to be able to access the elements at indicies i and i + 1 each time through the loop. And we had to adjust the loop header from the canonical for loop, changing the limit from the normal values.length to values.length - 1. If we looped with a limit of values.length then the last iteration of the loop i would be the largest legal index and i + 1 would be one greater and out of bounds.
The above algorithm only works if the array is sorted. If the array is not necessarily sorted, we need to do a bit more work, using a nested nested loop to compare all pairs of elements in the array. Look carefully at the two loops. The outer loop is a canonical loop, since we need to consider every element of the array against all it’s possible pairs. But the inner loop is unusual in that the initializer starts the loop variable not at 0. Why?
// check for duplicates anywhere in the array
public static boolean anyDuplicates(int[] values) {
for (int i = 0; i < values.length; i++) {
for (int j = i + 1; j < values.length; j++) {
if (values[i] == values[j]) {
return true;
}
}
}
return false;
}
Activity6.3.10.
Create a method sumPairs10(nums) returns true if there are at least two items in the array nums that are adjacent (next to each other) that add up to 10, otherwise return false.
Create a method noDups(nums) returns true if there are no repeated (duplicate) items in the array nums. It should return false if it does find a repeated element using nested loops.
Rotating an array means shifting all the elements in the array to the right or left by one position. For example, if the array is { 6, 2, 5, 3 }, rotating it to the right would give { 3, 6, 2, 5 } after the first three elements have each moved on position to the right and the 3 that was originially the last element is now the first element. Rotating the same initial array to the left would give us { 2, 5, 3, 6 }.
The scrambled code below is for a method that should return a new int[] that is the same as its argument but rotated one position to the right, so { 6, 2, 5, 3 } returns { 3, 6, 2, 5 }. The blocks also include one block that is not needed in a correct solution. Drag the blocks from the left and put them in the correct order on the right. Click the Check button to check your solution.
We can also rotate in place without constructing another array if we use a temporary variable to hold one value while we move all the others to their new position in the array. For instance to rotate left, store the value of the first element and then shift all the other elements one to the left in order. When all the elements have been shifted, put the original first element in the last position to complete the rotation.
The code below rotates array elements to the left in place without constructing another array. Try it in the Java visualizer with the CodeLens button. Can you change it to rotate the elements to the right instead? Hint: use a backwards loop.
Reversing an array is similar to rotating it. However rather than shifting elements one position either up or down, which only requires keeping track of one extra value in a temporary variable, when we reverse an array in place (meaning we are actually moving the values in the original array, not making a new array with the same values in reverse order), we will repeatedly swap elements.
For intance, clearly after we’ve reversed an array, the original first value will be in the last position and the originial last value will be in the first. So we need to swap those two elements, using a a temporary variable.
To see why, imagine that we have a glass of water and a glass of orange juice and we want to swap the contents of the two glasses without making a huge mess? We would need a third glass to temporarily hold the contents of one of the glasses, let’s say the glass of water. Once the water glass is empty we can pour the contents of the glass of orange juice into it. Then we can pour the water from the third glass into the now empty orange juice glass and the contents have been swapped. (At the point we can put the third glass in the dishwasher.) This is the same idea behind swapping elements in an array.
// Swapping 2 elements at index i and j
int temp = array[i]; // pour water into a third glass
array[i] = array[j]; // pour orange juice into original water glass
array[j] = temp; // pour water from third glass into original OJ glass
To completely reverse a list we need to repeatedly swap elements, starting with the first and last, then the second and second to last, and so on, until we get to the middle of the list. As when we rotating arrays, we will need to use a regular for loop to access the elements at specific indices.
The following two programs show how to reverse an array in place by swapping elements. The first uses a for loop and the second a should use a while loop.
The following method reverses an array in place using an indexed for loop and a temp variable to swap the first and last items, but the code blocks are mixed up. Drag the blocks from the left and put them in the correct order on the right. Click the Check button to check your solution.
public static void reverse(int[] a) {
---
int half = a.length / 2;
int max = a.length - 1;
---
for (int i = 0; i < half; i++) {
---
int temp = a[i];
---
a[i] = a[max - i];
---
a[max - i] = temp;
---
} // end for
---
} // end method
The following method reverses an array in place using a while loop and a temp variable to swap the first and last items. But, the blocks have been mixed up and include two extra blocks that are not needed in a correct solution. Drag the blocks from the left and put them in the correct order on the right. Click the Check button to check your solution.
Given the following code segment, which of the following will cause an infinite loop? Assume that temp is an int variable initialized to be greater than zero and that a is an array of integers.
When a contains a value that is less than or equal to zero then multiplying that value by 2 will never make the result larger than the temp value (which was set to some value > 0), so an infinite loop will occur.
