Chapter 5 - Arrays

ian@purpletrust.org
Mantra:
Coding is fun!
Chapter 5 Arrays
• Introducing Arrays
• Declaring Array Variables, Creating Arrays, and Initializing Arrays
• Passing Arrays to Methods
• Copying Arrays
• Multidimensional Arrays
• Search and Sorting Methods
 Introducing Arrays
Array is a data structure that represents a collection
of the same types of data.
double[] myList = new double[10];

myList reference myList[0]

myList[1]
myList[2] An Array of 10
myList[3] Elements
myList[4] of type double
myList[5]
myList[6]
myList[7]
myList[8]
myList[9]
Declaring Array Variables
• datatype[] arrayname;
Example:
double[] myList;

• datatype arrayname[];
Example:
double myList[];
 Creating Arrays
arrayName = new datatype[arraySize];

Example:
myList = new double[10];

myList[0] references the first element in the array.

myList[9] references the last element in the array.
Declaring and Creating
in One Step

• datatype[] arrayname = new

datatype[arraySize];
double[] myList = new double[10];

• datatype arrayname[] = new

datatype[arraySize];
double myList[] = new double[10];
 The Length of Arrays
• Once an array is created, its size is fixed. It
cannot be changed. You can find its size using

arrayVariable.length

For example,
myList.length returns 10
 Initializing Arrays
• Using a loop:
for (int i = 0; i < myList.length; i++)
myList[i] = i;

• Declaring, creating, initializing in one step:

double[] myList = {1.9, 2.9, 3.4, 3.5};
This shorthand syntax must be in one statement.
 Declaring, creating, initializing Using the
Shorthand Notation
double[] myList = {1.9, 2.9, 3.4, 3.5};
This shorthand notation is equivalent to the following statements:
double[] myList = new double[4];
myList[0] = 1.9;
myList[1] = 2.9;
myList[2] = 3.4;
myList[3] = 3.5;
 CAUTION
Using the shorthand notation,
you have to declare, create,
and initialize the array all
in one statement. Splitting it
would cause a syntax error.
For example, the following is
wrong:
double[] myList;

myList = {1.9, 2.9, 3.4, 3.5};

Example 5.1
Testing Arrays
• Objective: The program receives 6 numbers from
the keyboard, finds the largest number and
counts the occurrence of the largest
number entered from the keyboard.
Suppose you entered 3, 5, 2, 5, 5,
and 5, the largest number is 5 and its
occurrence count is 4.
Example 5.2
Assigning Grades
• Objective: read student scores (int) from the
keyboard, get the best score, and then assign
grades based on the following scheme:
• Grade is A if score is >= best–10;

• Grade is B if score is >= best–20;

• Grade is C if score is >= best–30;

• Grade is D if score is >= best–40;

• Grade is F otherwise.
 Passing Arrays to Methods
Java uses pass by value to pass parameters to
a method. There are important differences
between passing a value of variables of
primitive data types and passing arrays.
• For a parameter of a primitive type value, the
actual value is passed. Changing the value of
the local parameter inside the method does not
affect the value of the variable outside the
method.
• For a parameter of an array type, the value of
the parameter contains a reference to an array;
this reference is passed to the method. Any
changes to the array that occur inside the
method body will affect the original array that
was passed as the argument.
Example 5.3
Passing Arrays as Arguments

• Objective: Demonstrate differences

of passing primitive data type
variables and array variables.
 Example 5.3, cont.
swap(a[0], a[1]) a[0] 1 a[1] 2

Pass by value

swap( n1, n2) n1 1 n2 2

swapFirstTwoInArray(a) a Reference a[0]

: a[1]
Pass by value (Reference value)

swapFirstTwoInArray(array) array Reference

Example 5.4 Computing Deviation
Using Arrays
n n

 xi  i
( x  mean ) 2

mean  i 1 deviation  i 1

n n 1
 One char [] for
Example 5.5
alphabet
Another [] to store the
random chars
Counting Occurrence of Each
Letter
Math.random()

• Generate 100 lowercase letters randomly

and assign to an array of characters.
• Count the occurrence of each letter in Create another
method for this
the array.
• Find the mean and standard deviation of
the counts.
 Example 5.6
Copying Arrays
In this example, you will see that a simple
assignment cannot copy arrays in the
following program. The program simply
creates two arrays and attempts to copy
one to the other, using an assignment
statement.
Copying Arrays

Before the assignment After the assignment

list2 = list1; list2 = list1;

list1 list1
Contents Contents
of list1 of list1

list2 list2
Contents Contents
of list2 of list2
Garbage
 Copying Arrays
Using a loop:
int[] sourceArray = {2, 3, 1, 5, 10};
int[] targetArray = new
int[sourceArray.length];

for (int i = 0; i < sourceArrays.length; i++)

targetArray[i] = sourceArray[i];
The arraycopy Utility
arraycopy(sourceArray, src_pos,
targetArray, tar_pos, length);

Example:
System.arraycopy(sourceArray, 0,
targetArray, 0, sourceArray.length);
 Multidimensional Arrays
Declaring Variables of Multidimensional Arrays and Creating Multidimensional
Arrays

int[][] matrix = new int[10][10];

or
int matrix[][] = new int[10][10];
matrix[0][0] = 3;

for (int i=0; i<matrix.length; i++)

for (int j=0; j<matrix[i].length; j++)
{
matrix[i][j] = (int)(Math.random()*1000);
}

double[][] x;
Multidimensional Array Illustration

0 1 2 3 4 0 1 2 3 4 0 1 2
0 0 0 1 2 3

1 1 1 4 5 6

2 2 7 2 7 8 9

3 3 3 10 11 12

4 4 int[][] array = {
{1, 2, 3},
matrix = new int[5][5]; matrix[2][1] = 7; {4, 5, 6},
{7, 8, 9},
{10, 11, 12}
};
Declaring, Creating, and Initializing Using Shorthand Notations
You can also use a shorthand notation to declare, create and
initialize a two-dimensional array. For example,
int[][] array = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
{10, 11, 12}
};

This is equivalent to the following statements:

int[][] array = new int[4][3];
array[0][0] = 1; array[0][1] = 2; array[0][2] = 3;
array[1][0] = 4; array[1][1] = 5; array[1][2] = 6;
array[2][0] = 7; array[2][1] = 8; array[2][2] = 9;
array[3][0] = 10; array[3][1] = 11; array[3][2] = 12;
Lengths of Multidimensional Arrays

int[][] array = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
{10, 11, 12}
};

array.length
array[0].length
array[1].length
array[2].length
 Ragged Arrays
Each row in a two-dimensional array is
itself an array. So, the rows can have
different lengths. Such an array is known
as a ragged array. For example,
int[][] matrix = {
{1, 2, 3, 4, 5},
{2, 3, 4, 5},
{3, 4, 5},
{4, 5},
{5}
};
 Example 5.7
Adding and Multiplying Two Matrices

• Objective: Use two-dimensional arrays to

create two matrices, and then add and
multiply the two matrices.
 a 11 a 12 a 13 a 14 a 15   b11 b12 b13 b14 b15   a 11  b11 a 12  b12 a 13  b13 a 14  b14 a 15  b15 
     
 a 21 a 22 a 23 a 24 a 25   b 21 b 22 b 23 b 24 b 25   a 21  b 21 a 22  b 22 a 23  b 23 a 24  b24 a 25  b25 
 a 31 a 32 a 33 a 34 a 35    b31 b32 b33 b34 b35    a 31  b31 a 32  b32 a 33  b33 a 34  b34 a 35  b35 
     
 a 41 a 42 a 43 a 44 a 45   b 41 b 42 b 43 b 44 b 45   a 41  b 41 a 42  b 42 a 43  b43 a 44  b 44 a 45  b45 
 a 51 a 52 a 53 a 54 a 55   b51 b52 b53 b54 b55   a 51  b51 a 52  b52 a 53  b53 a 54  b54 a 55  b55 
     
 Example 5.7 (cont) Adding and
Multiplying Two Matrices
 a 11 a 12 a 13 a 14 a 15   b11 b12 b13 b14 b15   c11 c12 c13 c14 c15 
     
 a 21 a 22 a 23 a 24 a 25   b 21 b 22 b 23 b 24 b 25   c 21 c 22 c 23 c 24 c 25 
 a 31 a 32 a 33 a 34 a 35    b31 b32 b33 b34 b35    c 31 c 32 c 33 c 34 c 35 
     
 a 41 a 42 a 43 a 44 a 45   b 41 b 42 b 43 b 44 b 45   c 41 c 42 c 43 c 44 c 45 
 a 51 a 52 a 53 a 54 a 55   b51 b52 b53 b54 b55   c 51 c 52 c 53 c 54 c 55 
     

cij =
ai1b1j+ai2b2j+ai3b3j+ai4b4j+ai5b5j
 Example 5.8
Grading Multiple-Choice Test
• Objective: write a
Students’ Answers to the Questions:
program that grades
0 1 2 3 4 5 6 7 8 9

Student 0 A B A C C D E E A D
multiple-choice test.
Student 1 D B A B C A E E A D
Student 2 E D D A C B E E A D
Student 3 C B A E D C E E A D Key to the Questions:
Student 4 A B D C C D E E A D
Student 5 B B E C C D E E A D 0 1 2 3 4 5 6 7 8 9
Student 6 B B A C C D E E A D
Student 7 Key D B D C C D A E A D
E B E C C D E E A D
 Example 5.9
Calculating Total Scores
• Objective: write a program that calculates the total score for
students in a class. Suppose the scores are stored in a three-
dimensional array named scores. The first index in scores
refers to a student, the second refers to an exam, and the
third refers to the part of the exam. Suppose there are 7
students, 5 exams, and each exam has two parts--the
multiple-choice part and the programming part. So, scores[i][j]
[0] represents the score on the multiple-choice part for the i’s
student on the j’s exam. Your program displays the total score
for each student, .
Searching Arrays
Searching is the process of looking for a specific
element in an array; for example, discovering
whether a certain score is included in a list of
scores. Searching, like sorting, is a common task
in computer programming. There are many algorithms
and data structures devoted to searching. In this
section, two commonly used approaches are
discussed, linear search and binary search.
Linear Search
The linear search approach compares the key
element, key, with each element in the array
list[]. The method continues to do so until the
key matches an element in the list or the list is
exhausted without a match being found. If a match
is made, the linear search returns the index of
the element in the array that matches the key. If
no match is found, the search returns -1.
Example 5.10
Testing Linear Search

• Objective: Implement and test the linear

search method by creating an array of 10
elements of int type randomly and then
display this array. Prompt the user to enter
a key for testing the linear search.
Binary Search
For binary search to work, the elements in the
array must already be ordered. Without loss of
generality, assume that the array is in ascending
order.
e.g. 2 4 7 10 11 45 50 59 60 66 69 70 79
The binary search first compares the key with the
element in the middle of the array. Consider the
following three cases:
Binary Search, cont.
· If the key is less than the middle element, you
only need to search the key in the first half of
the array.
· If the key is equal to the middle element, the
search ends with a match.
· If the key is greater than the middle element,
you only need to search the key in the second half
of the array.
Binary Search, cont.
key = 11

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
list 2 4 7 10 11 45 50 59 60 66 69 70 79

key < 50 mid

[0] [1] [2] [3] [4] [5]

2 4 7 10 11 45

key > 7 mid

[3] [4] [5]

10 11 45

key = 11 mid
Example 5.11
Testing Binary Search

• Objective: Implement and test the binary

search method. The program first
creates an array of 10 elements of
int type. It displays this array
and then prompts the user to enter
a key for testing binary search.
Example 5.12
Using Arrays in Sorting

• Objective: Use the selectionSort method to write a

program that will sort a list of double floating-point
numbers.

int[] myList = {2, 9, 5, 4, 8, 1, 6}; // Unsorted

Sort it to produce 1, 2, 4, 5, 6, 8, 9

2, 9, 5, 4, 8, 1, 6
 Example 5.12: (Cont) Using Arrays in Sorting
int[] myList = {2, 9, 5, 4, 8, 1, 6}; // Unsorted
Find the largest element in myList and swap it with the last element
in myList.
2, 9, 5, 4, 8, 1, 6 => 2, 6, 5, 4, 8, 1, 9 (size = 7)
2, 6, 5, 4, 8, 1 => 2, 6, 5, 4, 1, 8 (size = 6)
2, 6, 5, 4, 1 => 2, 1, 5, 4, 6 (size = 5)
2, 1, 5, 4 => 2, 1, 4, 5
2, 1, 4 => 2, 1, 4,
2, 1 => 1, 2
Sort it to produce 1, 2, 4, 5, 6, 8, 9
 Exercise 5.5: Bubble Sort
int[] myList = {2, 9, 5, 4, 8, 1, 6}; // Unsorted

Pass 1: 2, 5, 4, 8, 1, 6, 9
Pass 2: 2, 4, 5, 1, 6, 8, 9
Pass 3: 2, 4, 1, 5, 6, 8, 9
Pass 4: 2, 1, 4, 5, 6, 8, 9
Pass 5: 1, 2, 4, 5, 6, 8, 9
Pass 6: 1, 2, 4, 5, 6, 8, 9