Skip to main content

Section 9.13 Chapter Summary

Subsection 9.13.1 Technical Terms

array initializer array length
binary search data structure
element element type
insertion sort multidimensional array
one-dimensional array polymorphic sort method
selection sort sequential search
sorting subscript
two-dimensional array

Subsection 9.13.2 Important Points

  • An array is a named collection of contiguous storage locations, each of which stores a data item of the same data type. Each element of an array is referred to by a subscript —that is, by its position in the array. If the array contains N elements, then its length is N and its indexes are 0, 1, … , N-1.
  • Array elements are referred to using the following subscript notation arrayname[subscript], where arrayname is any valid identifier, and subscript is an integer value in the range 0 to arrayname.length - 1. The array’s length instance variable can be used as a bound for loops that process the array.
  • An array declaration provides the name and type of the array. An array instantiation uses the keyword new and causes the compiler to allocate memory for the array’s elements: 
    int arr[]; // Declare a one-dimensional array variable
arr = new int[15];// Allocate 15 int locations for it
  • Multidimensional arrays have arrays as their components: 
    int twoDarr[][]; // Declare a two-dimensional array variable
twoDarr = new int[10][15]; // Allocate 150 int locations
  • An array’s values must be initialized by assigning values to each array location. An initializer expression may be included as part of the array declaration.
  • Insertion sort and selection sort are examples of array sorting algorithms. Both algorithms require several passes over the array.
  • When an array is passed as a argument to a method, a reference to the array is passed rather than the entire array itself.
  • Swapping two elements of an array, or any two locations in memory, requires the use of a temporary variable.
  • Sequential search and binary search are examples of array searching algorithms. Binary search requires that the array be sorted.
  • For multidimensional arrays, each dimension of the array has its own length variable.
  • Inheritance and polymorphism are useful design features for developing a hierarchy of computer games.

Solutions 9.13.3 Solutions to Self-Study Exercises

9.2 One-Dimensional Arrays
9.2.3 Array Allocation

Self-Study Exercises

9.2.5 Assigning and Using Array Values

Self-Study Exercises

9.2.5.5.
Solution. 
double farr[] = {1.1, 2.2, 3.3, 4.4, 5.5};
for (int k=0; k < farr.length; k++) {
  System.out.print(farr[k] + " ");
}

9.3 Simple Array Examples

Self-Study Exercise

9.3.1. Square Roots.
Solution.

9.4 Example: Counting Letter Frequencies
9.4.2 A Class to Count Letter Frequencies

Self-Study Exercises

9.4.2.1. Letter Frequencies.
Solution. 
public static void main(String[] argv) {
  AnalyzeFreq af = new AnalyzeFreq();
  af.countLetters("Now is the time for all good students" +
    " to study computer related topics.");
  af.printArray();
} //main()

9.5 Array Algorithms: Sorting
9.5.1 Insertion Sort

Self Study Exercise

9.5.1.3. Insertion sort trace 2.
Solution.
Answer: 0 1 18 24 90 85 34 18
The entire sort would go like this: 
24 18 90 1  0  85 34 18 // Initial
18 24 90 1  0  85 34 18 // Pass 1
18 24 90 1  0  85 34 18 // Pass 2
1  18 24 90 0  85 34 18 // Pass 3
0  1  18 24 90 85 34 18 // Pass 4 
0  1  18 24 85 90 34 18 // Pass 5
0  1  18 24 34 85 90 18 // Pass 6
0  1  18 18 24 34 85 90 // Pass 7

9.5.2 Selection Sort

Self-Study Exercises

9.5.2.1. Selection sort trace 1.
Solution.
Answer: >0 18 90 1 24 85 34 18
The first pass would select the smallest number and place it in the first array location: 
24 18 90 1   0   85 34 18 // Initial
0  18 90 1   24  85 34 18 // Pass 1
9.5.2.2. Selection sort trace 2.
Solution.
Answer: 0 1 18 18 24 85 34 90
The four smallest numbers would be sorted at the left of the array. 
24 18 90 1   0   85 34 18 // Initial
0  18 90 1   24  85 34 18 // Pass 1
0  1  90 18  24  85 34 18 // Pass 2
0  1  18 90  24  85 34 18 // Pass 3
0  1  18 18  24  85 34 90 // Pass 4
0  1  18 18  24  85 34 90 // Pass 5
0  1  18 18  24  34 85 90 // Pass 6
0  1  18 18  24  34 85 90 // Pass 7

9.5.3 Algorithm: Swapping Memory Elements

Self-Study Exercises

9.5.4 Passing a Value and Passing a Reference

Self-Study Exercise

9.5.4.3. Selection sort.
Solution. 
smallest = k; 
for (int i k+1; i<arr.length; i++) {
   if (arr[i] < arr[smallest])
     smallest = j;
}
swap(arr, k, smallest);

9.6 Array Algorithms: Searching
9.6.2 Binary Search

Self-Study Exercise

9.6.2.1. Binary search.
Solution.
Answer: 6, 10, 8, 9 
key  iteration  low   high    mid
21   0          0     13      6
21   1          7     13      10
21   2          7     9       8
21   3          9     9       9
21   4          10    9       failure

9.7 Two-Dimensional Arrays
9.7.1 Example: Rainfall Array

Self-Study Exercises

9.7.1.1. Two-D array.
Solution.

9.7.3 Passing Part of an Array to a Method

Self-Study Exercises

9.7.3.1. Newspaper sales.
Solution.

9.9 OBJECT-ORIENTED DESIGN: Polymorphic Sorting (Optional)
9.9.3 The java.util.Arrays.sort() Method

Self-Study Exercises

9.9.3.1. Polymorphic Sort.
Solution.
  1. A compareTo() for LetterFreq: 
    public int compareTo(Object lf) {
    LetterFreq  letFreq = (LetterFreq)lf;
    if (freq < letFreq.getFreq())
        return -1;
    else if (freq > letFreq.getFreq())
        return +1;
    else return 0; //The frequencies must be equal.
} //compareTo()
  2. A sort() for AnalyzeFreq: 
    public void sort() {
    java.util.Arrays.sort(freqArr);
} //sort()
  3. A new AnalyzeFreq.main() that uses sort(): 
    public static void main(String[] argv) {
  AnalyzeFreq af = new AnalyzeFreq();
  af.countLetters("Now is the time for all good students" +
    " to study computer-related topics.");
  af.sort();
  af.printArray();
} //main()
You have attempted of activities on this page.
PrevTopNext