AP Computer Science A Prep, 2024 - Rob Franek 2023
8 Array
Part V: Content Review for the AP Computer Science A Exam
An array is a data structure that makes handling like (as in similar) data easier. An array may store primitive data values or object references. Each piece of data is called an element, and an index is used to specify the location of the element we wish to access. Imagine an airline that sells more than a thousand tickets a day. If we want to process that data to accumulate statistics on origin cities or prices of tickets, each ticket could be instantiated separately, using a unique object reference variable for each ticket. Imagine then invoking a method on each of those object reference variables. By putting the data into an array, and then using a loop to access each element of the array, the code becomes much more efficient.
PRIMITIVES & OBJECTS
In order to instantiate an array, you must first decide what type of data will be contained in the array. Suppose you are creating a program that will keep track of your test grades in your APCS class. Since grades are usually represented by integer numbers, you will create an array of integers. The syntax for instantiating an array of integers is
int [] = new int [];
This format is used if you do not yet know the values that will be stored in the array. Alternatively, if you already know the data values, you can instantiate the array using an initializer list:
int [] = {, ,…, };
Notice the square brackets—these are standard symbols in Java that signify an array is present. The braces (curly brackets) indicate an initializer list. In the beginning of the semester, you do not yet know your grades. In order to create an array called testGrades that will eventually store your first five test grades, you could write a statement like this:
int [] testGrades = new int[5];
This array object will store your test grades and keep them organized using index numbers (or locations). Just as your tests might be organized as Chapter 1 Test, Chapter 2 Test, etc., your data will be accessed through the identifier of the array and index number. The tricky part is that array indices start with the number 0 instead of 1. Therefore, if your Chapter 1 Test is the first test score in the array, it will be stored at index 0. If the first test you have in APCS reviews a previous course, then it’s Chapter 0 instead of Chapter 1. If you did not instantiate the array using an initializer list, then you will assign data values using the index numbers; you will do the same process to access the data regardless of how you created the array. For example, if you scored a 95 on the first test, you could write the line:
testGrades[0] = 95;
Creating an array with five scores at once might look like this,
int [ ] testScores = {90, 80, 100, 85, 92};
Let’s say that, after looking over your test, you realize that your teacher made a grading error, and you actually scored a 98. You can either increment the data value or reassign it:
testGrades[0] += 3;
or
testGrades[0] = 98;
You can also perform any integer operation and also display the value to the user with that same format.
Let’s step it up a notch. Suppose, after all five tests are complete, your teacher feels that the scores are too high and decides to deflate the grades. (You didn’t think this book would discuss only nice teachers, did you?) The programmer can use a simple loop in order to traverse the array and change every value accordingly, rather than writing 5 separate lines. Since an array’s length is well-defined, a for loop is usually appropriate for arrays. Provided that the array is full, meaning all 5 values are assigned, the following loop will traverse the array and subtract 2 points from every grade:
for (int index = 0; index < 5; index++)
testGrades[index] -= 2;
Note the values of index will be 0, 1, 2, 3, and 4, even though it stores five elements. Since the index numbers start at 0, you must stop traversing the array before index 5, or your will receive an ArrayIndexOutOfBoundsException and the program execution will be interrupted. Free-Response Questions on the AP Exam often test your ability to write code that does not go out of bounds.
An array also has a constant value returned by .length that will return the number of elements in the array. The above loop could be written:
for (int index = 0; index < testgrades.length; index++)
testGrades(index) -= 2;
Much better than writing multiple lines, right? The loop systematically changes every value in the array. We are just scratching the surface of the usefulness of arrays, and we have already improved our coding efficiency.
The AP Exam will require you to create, traverse, and modify arrays; free-response questions are loaded with arrays and will specifically state that an array must be created. The Course and Exam Description states, specifically, that free-response questions 3 and 4 have to do with arrays (3 is Array/ArrayList and 4 is 2D Array).
The programmer needs to ensure that every element of the array contains a meaningful value, or undesired results may occur. In an array of integers, the value of an unassigned element will default to 0. Consider the following code segment that will calculate the average of your five test grades:
int total = 0, len = testGrades.length;
double average;
for (int index = 0; index < len; index++)
total += testGrades[index];
average = (double) total / len;
If all five of your test grades are stored in the array, this code segment will calculate the average correctly. If you did not input one of your scores, however, it will remain stored as 0 and incorrectly drag down your average, which is (definitely) an undesired result.
There is an alternative way to execute the previous code segment. This involves using an enhanced-for loop. An enhanced-for loop can be used to automatically go through each element of an array.
int total = 0, len = testGrades.length;
double average;
for (int grade : testGrades)
total += grade;
average = (double) total / len;
In the enhanced-for statement, a previously declared array or an ArrayList (more on ArrayLists later) must be referenced after the colon. The loop will iterate for each element in the list, from index 0 to index length - 1. However, no variable is used to refer to the current index. Instead, the element located at the current index is stored as the variable declared before the colon. (The variable must be of the same type stored in the array.) Therefore, the enhanced-for loop above stores each element—one at a time in increasing order by index—of the array testGrades as grade. It then adds grade to total. Thus, the enhanced-for loop has the same functionality as the for loop in the previous example. The benefits of the enhanced-for loop are that it will not cause an ArrayIndexOutOfBoundsException when traversing an array and that it shortens the notation of the element considerably.
1.Consider the following code segment:
final int[] a1 = {1, 2};
int[] b1 = {3, 4};
a1 = b1;
System.out.print(a1[1]);
What is printed as a result of executing the code segment?
(A) 2
(B) 3
(C) 4
(D) Nothing is printed due to a compile-time error.
(E) Nothing is printed due to a run-time error.
Here’s How to Crack It
This is an easy one if you know your compiler. Since a1 is declared final, its reference cannot be changed. In the third line, the programmer attempts to change a1 to reference the second array, which is not allowed. The answer is (D).
2.Consider the following code segment:
int [] a = {1, 2, 3};
int [] b = {4, 5, 6};
a = b;
for (int i = 0; i < b.length; i++)
{
b[i] *= 2;
}
System.out.println(a[0]);
What is printed as a result of executing the code segment?
(A) 1
(B) 4
(C) 8
(D) Nothing is printed due to a compile-time error.
(E) Nothing is printed due to a run-time error.
Here’s How to Crack It
Remember arrays are objects. An assignment statement assigns the object reference so both a and b are pointing to the same array. If b is changed, a is changed as well. After the loop, b = {8, 10, 12}. Since a is pointing at b, a[0] = 8.
3.Consider the following incomplete method:
public static int mod3(int[] a)
{
int count = 0;
// code not shown
return count;
}
Method Mod3 is intended to return the number of integers in the array that are evenly divisible by 3. Which of the following code segments could be used to replace // code not shown so that Mod3 will work as intended?
I. for (int i = 0; i < a.length; i++)
{
if (i % 3 == 0)
{
count++;
}
}
II. for (int i = 0; i < a.length; i++)
{
if (a[i] % 3 == 0)
{
count++;
}
}
III. int i = 0;
while (a[i] % 3 == 0)
{
count++;
i++;
}
(A) I only
(B) II only
(C) III only
(D) I and II
(E) II and III
Here’s How to Crack It
The while loop in option III has two problems. It will either only execute while encountering an integer in the array that is divisible by 3 (possibly stopping before traversing the entire array) or, if all the entries in the array are divisible by 3, it will go beyond the bounds of the array, causing a run-time error. This eliminates (C) and (E). Option I checks whether the index (or location) is divisible by 3. This eliminates (A) and (D). Option II checks whether the element is divisible by 3. Choice (B) is the answer.
Since objects are typically used to represent real-world phenomena, arrays are also commonly used to organize and manipulate objects. Suppose you have an object class that represents a pair of sneakers. The following code segment would instantiate an array that would store five of these objects:
PairOfSneakers collection[] = new PairOfSneakers[5];
Since each element is an object, however, the default value for each object is null. Since null is not a valid object, operations performed on null will result in a NullPointerException, another error that will halt the execution of the program. Without getting into the specifics of the PairOfSneakers class, a statement that could assign an instantiated pair of sneakers called jordans is
collection[0] = jordans;
Now, suppose PairOfSneakers has a tie() method that will tie the laces of the corresponding pair of sneakers; i.e., jordans.tie() will tie that pair. At this point, index 0 references the jordans object—remember that objects are referenced, not copied—but elements at indices 1—4 are null. To avoid a NullPointerException, check that each object is not equal to null.
for (int i = 0; i < collection.length; i++)
if (collection[i] != null)
collection[i].tie();
When using a loop to traverse an array of objects, be sure the array is full to avoid undesired results.
4.Consider the following code:
public int[] someMethod (int[] array, int value)
{
for (int i = 1, i < array.length — 1; i++)
array[i - 1] += value;
return array;
}
Which of the following statements is true about the method someMethod?
(A) The method will not return the first value in the array.
(B) The method will return the last value in the array.
(C) The method will cause a run-time error.
(D) The method will not increment the first element of the array by value.
(E) The method will not increment the last element of the array by value.
Here’s How to Crack It
The return value must be an array of integers, so eliminate (A) and (B) because array[i] is an integer. The loop traverses the array without going out of bounds and no illegal operations are performed on the elements in the array. There will be no run-time error, so eliminate (C). The array[0] is incremented because the variable i is initialized with a starting value of 1. The method then increments array[i - 1] . By the same reasoning, the last element will not be incremented. The final value of i will be array.length — 1, which is normally used to find the last index within the array, but the assignment statement uses i - 1 (which is now representing the second to the last index of the array). The loop terminates without accessing the last element, so the answer is (E).
5.Consider the following code:
public int[] mystery (int[] array, int num)
{
for(int i = 1, i < array.length - 1; i++)
array[i] = 0;
return array[0];
}
There is an error in method mystery. Which of the following modifications is needed to correct the compiler error?
(A) Change int[] array in the method header parameter to int[] numbers.
(B) Change array.length - 1 to array.length in the loop statement.
(C) Change array[i] = 0; to array[i - 1] = 0;.
(D) Change the return statement to return array;.
(E) None of these choices will make the method compile.
Here’s How to Crack It
The problem with this method is the discrepancy between the return type int[] and the type of value that the method attempts to return, int; (D) addresses this issue. Choice (A) will have no effect on the outcome of the method because array is simply the name of the variable that references the array. Choices (B) and (C), although valid, will not correct the return type issue. Choice (E) is incorrect, again, because the return type issue is keeping the method from compiling. The answer is (D).
SEARCHES
Once data is stored in an array, a common task is to methodically search the array for given data. Consider a line of parked cars in the “Curbside To Go” section of your local chain restaurant. When the server is taking the food to a particular car, she must use a given attribute—say, a license plate number—to find the correct car. Once the correct car is found, the server can deliver the food and then go back inside for the next order, beginning the process all over again…and again…and again.
This same technique is used for searching an array. In APCS, we have two methods of searching arrays, the sequential search and the binary search. Since each of these search methods uses a distinct formula to search through the arrays, they are commonly referred to as search algorithms.
The chain restaurant example given above is an example of a sequential search. All of the cars are “lined up” and the server begins with the first car, checking its license plate number against the one she is looking for. If it’s correct, the server delivers the food and returns. If not, she moves on to the next car and repeats the process; this all ends when either (1) the correct car is found or (2) the correct car is not in the line at all. This sequential process works just fine, although it can be very tedious. The server would have to do much more work if the desired car were at the end of the line, as opposed to at the beginning. Remember, we are programming a computer; the server cannot simply “look” at all of the plates at once, as we might in real life. The computer does not know how to “look,” unless we know how to write the program that enables it!
A code segment that performs a linear search for a number target in an array of integers nums might look like this:
for (int i = 0; i < nums.length; i++)
if (nums[i] == target)
System.out.print(“Found at ” + i);
This segment will correctly traverse the array, searching for target, starting with index 0 and continuing to index length - 1, as desired. Remember that nums.length is the size of the array and therefore nums[length] would be out of bounds. When target is found, the print statement displays its index number. This process will continue until the end of the array is reached. Note that if target is never found, there will be no output.
When writing algorithms that traverse arrays, programmers often implement the enhanced-for loop, which is designed specifically for traversing entire arrays. In cases in which traversing the entire array is not the intent or would cause a runtime error, the enhanced-for loop should not be used. Assuming nums from the previous example would not cause such a problem, the same code segment can be written as an enhanced-for loop structure like this:
int loc = 0;
for (int num : nums)
{
if (num == target)
System.out.print(“found at ” + loc);
i++;
}
Each time the loop iterates, num will be assigned the value of the next element in the array. This structure automatically ensures that the loop does not go out of bounds. In this case, loc is the location or index in which the target is found.
It is important to note that the enhanced-for loop provides a variable that will hold each element of the array. It will NOT automatically provide the index of that element. You will have to add code to keep track of the index if you want to use it. If the variable created to hold each element is modified in any way, the array will not be modified.
A binary search is much more efficient; think of it as a “divide-and-conquer” mechanism. Instead of our restaurant server starting with the beginning of the line of cars, she will start with the middle car. Depending on whether the license plate is “greater” or “less” than the car she is looking for, the server will move in the appropriate direction.
There is a huge obstacle with binary searches, however, or at least, for us with our current level of Java knowledge: these searches work only when there is an inherent order in the data. Suppose the top 21 students in the senior class are lined up in a row. You are looking for a student within that top 21 named Kathy, whom you have never met, and you are not sure where she is in the line. If the students are not lined up in a particular order, a sequential search is your only option, and you might need all 21 tries to find her if she is the last person in the lineup. If they are sorted in alphabetical order by first name, though, you can divide and conquer. Go to the middle person and find out her name…if her name is Sara, you would move toward the front of the line and ignore the back. You then perform the same process, asking the name of the person halfway between the front of the line and Sara, and then ignore the appropriate side. Within a few tries, you will have Kathy.
Here is a code example of how a binary search might look for array nums when searching for target, assuming nums is sorted:
int front = 0, back = nums.length - 1, middle = 0;
boolean isFound = false;
while((front <= back) && (!isFound))
{
middle = (front + back) / 2;
if (nums[middle] < target)
{
front = middle + 1;
}
else if(nums[middle] > target)
{
back = middle - 1;
}
else
{
isFound = true;
}
}
if (isFound)
{
System.out.println(“Found at ” + middle);
}
else
{
System.out.println(“Target Not Found”);
}
On the AP Exam, you will not be required to write a search algorithm; however, you will be required to recognize a search algorithm and trace it, which can be done the easy way if you understand the algorithm, or the hard way by actually tracing the code, step by step. Try to identify the key characteristics of each search; for example, the “sum divided by 2” line is a good indicator of a binary search. The enhanced-for loop will traverse the entire array, which may indicate a sequential search.
6.Which of the following statements is true regarding search algorithms?
(A) Searching for a Twix in a row of unsorted candy is most efficient using a sequential search.
(B) Searching for a Twix in a row of unsorted candy is most efficient using a binary search.
(C) Searching for a Twix in a row of sorted candy is most efficient using a sequential search.
(D) Searching for a Twix in a row of sorted candy is most efficient using a binary search.
(E) None of these
Here’s How to Crack It
Searching is usually more efficient using a binary search, provided the array is sorted—eliminate (B), since you can’t use a binary search on unsorted data. However, a binary search will require more than one comparison if the target is not in the middle, whereas a linear search (also called a sequential search) will need only one comparison if the target is first in line. Therefore, each of the three situations presented in (A), (C), and (D) could be the most efficient, depending on the position of the Twix. The answer is (E).
7.Assuming target is in array a, which of the following methods will correctly return the index of target in sorted array a?
I. public int findTarget(int[] a, int target)
{
for (int x = 0; x < a.length; x++)
if (a[x] == target)
return x;
}
II. public int findTarget(int[] a, int target)
{
int k = 0;
for (int x : a)
{
if (x == target)
return k;
k++;
}
return -1;
III. public int findTarget(int[] a, int target)
{
int f = 0, h = a.length, g = 0;
for (int i = 0; i < h; i++)
{
g = (f + h)/2;
if (a[g] < target)
f = g + 1;
else if (a[g] > target)
h = g — 1;
}
if (a[g] == target)
return g;
return -1;
}
(A) I only
(B) II only
(C) I and II only
(D) II and III only
(E) I, II, and III
Here’s How to Crack It
Notice that Options I and II look like linear searches, while III looks like a binary search. Option I will not compile because a non-void method must return data. An if statement without an else implies data may not be returned—even though the assumption states that will not occur—so the compiler will stop here. Eliminate (A), (C), and (E). Both (B) and (D) include Option II, so it must be correct; skip to Option III. Note that the variables are a bit confusing—but front/middle/back correspond to f/g/h, so they are in alphabetical order. Option III is a nice binary search, and it avoids the return problem in Option I by returning -1 if target is not found, a common practice when writing search algorithms. Therefore, Options II and III are correct and (D) is the answer.
Read Carefully!
This question is about a sorted array! Be sure you read the entire question carefully before you dive in.
SORTS
Probably the most useful algorithms you will learn in AP Computer Science A are sorting algorithms—but they are also probably the most difficult to understand. If you’ve been keeping up within this book so far, then you have a good start.
As the name implies, sorting algorithms will take data in an array and rearrange it into a particular order. We already know that this technique is useful if we want to search for data using the binary search algorithm. But imagine this automated process in real life: a process that automatically sorts the cups in your cabinet in height order, a process that automatically takes your homework assignments and arranges them in time order, and a process that sorts your to-do list in priority order. Needless to say: sorting algorithms are extremely powerful.
The selection sort is the first sorting algorithm we will discuss, and one of the three sorting algorithms you need to know for the AP Exam. This is a search-and-swap algorithm, so you should remember that the selection sort searches and swaps. Similar to a sequential search, the sort will first traverse the array for the lowest value. Once it finds the lowest value, it will swap its position in the array with the data at index 0. Now the first element is sorted. The process then repeats for index 1. The rest of the array will be searched for the lowest value and swapped with the data at index 1. Note that if the lowest value is already in position, it will stay there.
Consider the array below. We would like to sort this array from least to greatest.
Our strategy will be to first find the smallest element in the array and put it in the first position. We will then find the smallest of the remaining elements and put that in the second position. We will continue to do this until the array is ordered.
We can start by looking at every element in the array (starting with the first element) and finding the smallest element. It’s easy for a person to quickly glance through the array and see which element is smallest, but the sorting algorithm that we will implement can compare only two elements at once. So here’s how we can find the smallest element: take the number in the first cell in the array and assign it to a variable called smallestSoFar. We’ll also assign the position of that value to a variable called position. In this case, smallestSoFar will equal 8 and position will be 0. Note that even though we are assigning 8 to smallestSoFar, the first cell of the array will contain 8; we didn’t actually remove it.
smallestSoFar = 8;
position = 0;
Next we’ll walk through the array and compare the next value to smallestSoFar. The next value is 6, which is less than 8, so smallestSoFar becomes 6 and position becomes 1.
smallestSoFar = 6;
position = 1;
Now let’s look at the next value in the array. 10 is larger than 6, so smallestSoFar remains 6.
smallestSoFar = 6;
position = 1;
The next value in the array is 2: 2 is smaller than 6.
smallestSoFar = 2;
position = 3;
And finally, we look at the last element, 4. Because 4 is greater than 2, and we are at the end of the array, we know that 2 is the smallest element.
smallestSoFar = 2;
position = 3;
Now we know that 2 is the smallest element in the array. Because we want to order the array from least to greatest, we need to put 2 in the first cell in the array. We don’t simply want to overwrite the 8 that is in the first cell, though. What we’ll do is swap the 2 with the 8 to get
We now have the smallest element in place. Next we’ll need to find the second smallest element in the array. We can do this using the same approach we employed to find the smallest element. Because we know that 2 is the smallest element, we have to look at the elements only in positions 1 to 4 for the second smallest element.
Start by assigning 6 to smallestSoFar and 1 to position and then compare 6 to 10. Six is the smaller element. Next, compare 6 to 8; 6 is still the smaller element. Finally, compare 6 to 4; 4 is smaller, and because we have no more elements in the array, 4 must be the second smallest element in the array.
Swap 4 with the second element in the array to get
Make another pass through the array to find the third smallest element, and swap it into the third cell. The third smallest element is 6.
Finally, we look at the last two elements. Eight is smaller than 10, so we don’t need to do anything. Our array is now sorted from least to greatest.
Implementation of a Selection Sort
Here is how a selection sort can be implemented in Java. The following implementation will sort the elements from least to greatest and will begin by sorting the smallest elements first.
//precondition: numbers is an array of ints
//postcondition: numbers is sorted in ascending order
1 public static void selectionSort1(int[] numbers)
2 {
3 for (int i = 0; i < numbers.length — 1; i++)
4 {
5 int position = i;
6 for (int k = i + 1; k < numbers.length; k++)
7 {
8 if (numbers[k] < numbers[position])
9 {
10 position = k;
11 }
12 }
13 int temp = numbers[i];
14 numbers[i] = numbers[position];
15 numbers[position] = temp;
16 }
17 }
How could this be useful? Consider a case in which you have an unsorted array of 1,000 Student objects, and each Student object has a method that returns a grade point average for that Student. What if you would like to find the five students with the highest grade point average? In this case, it would be a waste of time to sort the entire array. Instead, we can just run through five cycles of the second implementation of the selection sort shown above, and the top five students will be sorted.
The insertion sort is a little less intuitive. Rather than traversing the entire array, it compares the first two elements and, depending on the comparison, inserts the second value “in front” of the first value into index 0, moving the first value to index 1. The first two elements are now sorted. Then the third element is checked, and the inserting continues. Note that here, also, an already sorted element will remain in its position.
Below is an array with 9 elements. This array is sorted from least to greatest except for the last element.
We would like to move 15 so that the entire array is in order. First, we’ll temporarily assign 15 to a variable. This will give us room to shift the other elements to the right if needed.
temp = 15
We then compare 15 to the first element to its left: 22. Because 22 is larger than 15, we shift 22 to the right.
temp = 15
We then compare 15 to the next element: 17. Because 17 is larger, we shift that to the right also.
temp = 15
Next we compare 15 to 14. Because 15 is larger, we don’t want to shift 14 to the right. Instead, we insert 15 into the empty cell in the array. Now the array is correctly sorted.
Insert 15:
Now we’ll look at how we can use the idea illustrated above to sort an entire array. This example will start at the beginning of the sorting process.
Here is the array that we are going to sort.
First, we’ll look at just the first two elements of the array to make sure that they are sorted relative to each other.
To do this, we’ll pull 6 (the number that is farthest to the right in our subarray) out of the array and temporarily assign it to a variable. We’ll then compare 6 to 8. Because 8 is larger, shift 8 to the right and then put 6 in the cell where 8 was.
temp = 6
Here’s what the array looks like.
Now we need to put 7 in the proper place relative to 6 and 8. We start by assigning 7 temporarily to a variable.
temp = 7
We then compare 7 to the first number to its left: 8. Because 7 is less than 8, we shift 8 one place to the right.
temp = 7
Next, we’ll compare 7 to the next number in the array: 6. Because 6 is less than 7, we don’t want to shift 6 to the right. Instead, we will put 7 in the second cell. Our array now looks like the following:
Now we need to put 10 in its place relative to the first 3 elements in the array.
temp = 10
First we compare 10 to 8; because 8 is smaller than 10, we don’t need to shift 8 to the right. In fact, we can put 10 right back into the cell from which it came.
Implementation of an Insertion Sort
Here is how an insertion sort can be implemented in Java.
//precondition: x is an array of integers; x.length >= 0
//postcondition: x is sorted from least to greatest
1 public static void insertionSort(int[] x)
2 {
3 for (int i = 1; i < x.length; i++)
4 {
5 int temp = x[i];
6 int j = i — 1;
7 while (j >= 0 && x[j] > temp)
8 {
9 x[j + 1] = x[j];
10 j——;
11 }
12 x[j + 1] = temp;
13 }
14 }
Note that like the selection sort, the insertion sort contains nested loops. In this case, we have a while loop nested within a for loop.
The for loop, beginning on line 3, proceeds from index 1 to the end of the array. The while loop goes through the array from i to 0 and shifts elements that are larger than temp to the right on line 9. On line 12, we put the value of temp into its proper place in the array.
Bonus Tips and Tricks…
Check us out on YouTube for additional test-taking tips and must-know strategies at www.youtube.com/ThePrincetonReview
Another type of sort used on the AP Exam is the merge sort. This is a more complex type of sort that uses recursion, which is the technique that uses a method to call itself. (Recursion will be further discussed in Chapter 12.) A merge sort is like a divide-and-conquer. An array is split into two pieces. Each piece is sorted. The two sorted pieces are then merged together into one sorted list. In order to sort each of the two pieces, the same divide-and-conquer method is used.
Below is an array with 8 elements:
The merge sort will divide this array into two pieces:
Let’s look at just the left half of the array. This array is divided into two pieces:
Each of these pieces is similarly divided into two pieces:
Since each remaining piece contains only one element, simply order the two from left to right:
Now merge the two sorted segments. Compare the first element in each piece. The smaller is 3, so this is the first element of the merged array. Now compare the first element in each piece that hasn’t already been copied. These are 8 and 9. The smaller is 8, so this is the second element of the merged array. Again, compare the first element in each piece that hasn’t already been copied. These are 14 and 9. The smaller is 9, so this is the third element of the merged array. Since the second array has no remaining elements that haven’t already been copied, add the remaining element(s) from the first array into the merged array. The only remaining element is 14, so this is the fourth element:
Follow a similar process for the right half of the first array. Divide into two pieces:
Each of these pieces is similarly divided into two pieces:
Since each remaining piece contains only one element, simply order the two from left to right:
Now merge the two sorted segments. Compare the first element in each piece. The smaller is 4, so this is the first element of the merged array. Now compare the first element in each piece that hasn’t already been copied. These are 5 and 12. The smaller is 5, so this is the second element of the merged array. Since the first array has no remaining elements that haven’t already been copied, add the remaining elements from the second array into the merged array. The remaining elements, 12 and 21, become the third and fourth elements of the merged array:
Thus, the two sorted pieces of the original array look like this:
Merge the two sorted arrays. Compare 3 and 4 to get that the first element is 3. Compare 8 and 4 to get that the second element is 4. Compare 8 and 5 to get that the third element is 5. Compare 8 and 12 to get that the fourth element is 8.
Compare 9 and 12 to get that the fifth element is 9. Compare 14 and 12 to get that the sixth element is 12. Compare 14 and 21 to get that the seventh element is 14. Since the first array has no uncopied elements, 21, which is the only remaining uncopied element in the second array, becomes the eighth element of the merged array. Below is the final array:
Implementation of a Merge Sort
Here’s how a merge sort can be implemented in Java.
//precondition: x is an array in integers; x.length >= 0
//postcondition: x is sorted from least to greatest
1 public static void mergeSort (int[] x)
2 {
3 int[] temp = new int[x.length];
4 mergeSortHelper(x, 0, x.length — 1, temp);
5 }
6 public static void mergeSortHelper (int[] x, int lowIndex, int highIndex, int temp)
7 {
8 if (lowIndex < highIndex)
9 {
10 int mid = (lowIndex + highIndex) / 2;
11 mergeSortHelper(x, lowIndex, mid, temp);
12 mergeSortHelper(x, mid + 1, highIndex, temp);
13 merge(x, lowIndex, mid, highIndex, temp);
14 }
15 }
16 public static void merge(int[] x, int lowIndex, int mid, int highIndex, temp)
17 {
18 int l = lowIndex;
19 int m = mid + 1;
20 int n = highIndex;
21 while (l <= mid && m <= highIndex)
22 {
23 if (x[l] < x[m])
24 {
25 temp[n] = x[l];
26 l++;
27 }
28 else
29 {
30 temp[n] = x[m];
31 m++;
32 }
33 n++;
34 }
35 while (l <= mid)
36 {
37 temp[n] = x[l];
38 l++;
39 n++;
40 }
41 while (m <= highIndex)
42 {
43 temp[n] = x[m];
44 m++;
45 n++;
46 }
47 for (n = lowIndex; n <= highIndex; n++)
48 {
49 x[n] = temp[k];
50 }
51 }
This is clearly a more complex sort than the other two and it involves the use of multiple methods. The first method splits the array into two pieces, the second sorts the individual pieces, and the third merges the two pieces into one sorted array.
KEY TERMS
array
initializer list
index numbers
traverse
full
ArrayIndexOutOfBoundsException
enhanced-for loop
null
NullPointerException
sequential search
binary search
search algorithms
sorting algorithms
selection sort
insertion sort
merge sort
recursion
CHAPTER 8 REVIEW DRILL
Answers to review questions can be found in Chapter 13.
1.What is the length of the array numbers after the following code executes?
String word = “Bear”;
int[] numbers = new int[word.length() - 1];
(A) 1
(B) 3
(C) 4
(D) 6
(E) The array will not be created due to a compile-time error.
2.Consider the following code segment:
String[] s = new String[2];
String[] t = {“Michael”, “Megan”, “Chelsea”};
s = t;
System.out.print(s.length);
What is printed as a result of executing the code segment?
(A) 1
(B) 2
(C) 3
(D) Nothing will be printed due to a compile-time error.
(E) Nothing will be printed due to a run-time error.
3.Consider the following code segment:
final int[] a1 = {1, 2};
int[] b1 = {3, 4};
a1 = b1;
System.out.print(a1[1]);
What is printed as a result of executing the code segment?
(A) 2
(B) 3
(C) 4
(D) Nothing will be printed due to a compile-time error.
(E) Nothing will be printed due to a run-time error.
4.Consider the following code segment:
final int[] myArray = {1, 2};
myArray[1] = 3;
System.out.print(myArray[1]);
What is printed as a result of executing the code segment?
(A) 1
(B) 2
(C) 3
(D) Nothing will be printed due to a run-time error.
(E) Nothing will be printed due to a compile-time error.
5.Consider the following incomplete method:
public static int mod3(int[] numbers)
{
int count = 0;
for (int i = 0; i < numbers.length; i++)
{
/* mystery code */
}
return count;
}
Method mod3 is intended to return the number of integers in the array numbers that are evenly divisible by 3. Which of the following code segments could be used to replace /* mystery code */ so that mod3 will work as intended?
I. if (i % 3 == 0)
{
count++;
}
II. if (numbers[i] % 3 == 0)
{
count++;
}
III. while (numbers[i] % 3 == 0)
{
count++;
}
(A) I only
(B) II only
(C) III only
(D) I and II
(E) II and III
6.Assume that an array arr of integer values has been declared and initialized with random numbers. Which of the following code segments correctly swaps the values stored in arr[0] and arr[3]?
(A) arr[0] = 3;
arr[3] = 0;
(B) arr[0] = arr[3];
arr[3] = arr[0];
(C) int k = arr[3];
arr[3] = arr[0];
arr[0] = k;
(D) int k = arr[3];
arr[0] = arr[3];
arr[3] = k;
(E) int k = arr[0];
arr[3] = arr[0];
arr[0] = k;
7.Consider the following code segment:
int [] scores = {75, 63, 52, 80};
for (int s : scores)
{
if (s < 75)
{
s += 5;
}
}
for (int s : scores)
{
System.out.print(s + “ ”);
}
What is printed as a result of executing the code segment?
(A) 75 63 52 80
(B) 75 68 57 80
(C) 80 68 57 80
(D) 80 68 57 85
(E) Nothing will be printed due to a compile-time error.
8.Consider the following code segment:
String [] names = {“Abi”, “Brianna”, “Jada”, “Kiara”, “Tiffany”, “Vanessa”};
int middle = names.length/2 - 1;
for (int x = 0; x < middle; x++)
{
String hold = names[x];
names[x] = names [names.length - x - 1];
names[names.length - x - 1] = hold;
}
for (String n: names)
{
System.out.print(n + “ ”);
}
What is printed as a result of executing the code segment?
(A) Abi Brianna Jada Kiara Tiffany Vanessa
(B) Abi Jada Brianna Vanessa Kiara Tiffany
(C) Vanessa Tiffany Kiara Jada Brianna Abi
(D) Vanessa Tiffany Jada Kiara Brianna Abi
(E) Vanessa Brianna Jada Kiara Tiffany Abi
Summary
o An array is a grouping of a fixed length of variables of the same data type or objects of the same class.
o Arrays are indexed beginning at 0 and ending at length —1.
o An enhanced-for loop automatically performs the loop for each element of an array.
o A sequential search looks for an element of an array beginning at index 0 until the desired element is found and returns the index. If the element is not found, it returns —1.
o A binary search begins searching in the middle of an array and moves to higher or lower indices to find the desired element. A binary search tends to be more efficient but can be used only on an ordered list.
o A selection sort orders an array by swapping the smallest elements to the first index and then repeatedly finding the second smallest element to swap into the second index, and so on.
o An insertion sort orders an array by finding the appropriate location for an element, shifting other elements to take its place, and then placing the element into the appropriate location.
o A merge sort orders an array by recursively dividing the array into smaller pieces. The smaller pieces are sorted and merged with other pieces.