6: Arrays

What We Will Cover

Illuminations

Homework Questions?

Viewing WebCT Assignment Results and Solutions

Questions from last class?

^ top

6.1: Arrays

Learner Outcomes

At the end of the lesson the student will be able to:

  • Declare and allocate memory for arrays
  • Write code to initialize arrays
  • Use arrays with loops

^ top

6.1.1: Using Lists for Data

  • Often times we need to process a group of the same types of data
  • For instance:
    • Bank account transactions
    • Salaries for employees in a company
    • Test scores for a group of students
    • Temperature data over some period of time
  • Consider how we might process following student test scores:
    90
    95
    87
    89
    98
  • With this data, we can calculate statistics like:
    • Highest score
    • Lowest score
    • Average (mean) score
    • Difference (deviation) of each score from the average
  • We can write a program to read this data and make the calculations
  • However, to calculate the difference from the mean, we need to first find the mean
  • Thus, we have to process all the data twice: one to find the mean and another to calculate the difference of each score from the mean
  • To process the data more than once, the best approach is to keep all the data in main memory

Storing Lists of Data

  • If we know there are 10 inputs, we can use 10 separate variables
  • Using separate variables quickly becomes prohibitive as the list gets larger (100 scores)
  • One way to store lists of data in main memory is to use arrays

Array: a data structure that organizes a list of identically-typed variables such that each variable is accessed using an index

^ top

6.1.2: Declaring and Allocating Arrays

  • The general syntax for declaring an array is: 
    dataType[] arrayName;
or
dataType arrayName[];
  • Where:
    • dataType: the data type of all the array items
    • arrayName: the name you make up for the array
  • For example, to declare an array named scores of type int: 
    int[] scores;
  • The syntax to allocate memory space for an array is:
    • arrayName = new dataType[size];
  • Where:
    • arrayName: the name of the array
    • dataType: the data type of all the array items
    • size: the number of data items the array can hold
  • For example, to allocate memory for 5 items of the scores array declared above: 
    scores = new int[5]
  • You can combine the declaration and allocation in one statement like: 
    int[] score = new int[5];  // Java style
  • Which is equivalent to: 
    int score[] = new int[5];  // C++ style
  • This is like declaring 5 variables of type int numbered as follows:
    • score[0], score[1], score[2], score[3], score[4]
  • The value in brackets is called an index or subscript
  • Individual values in an array are called items, elements
  • The number of indexed variables in an array is the size of the array
    • The largest index is one less than the size
    • The first index value is zero
  • Arrays can be of any data type
  • All the variables of an array are always of the same data type
    • Known as the base type of the array
  • Once allocated, you cannot change the number of elements

^ top

6.1.3: Referencing Array Elements

  • As you can see from the new operator, an array is an object: 
    int[] score = new int[5];
  • However, it is convenient to think of an array as contiguous slots in memory like this:

    scores = 
     
     
     
     
     
    [0]
    [1]
    [2]
    [3]
    [4]

  • Each of the memory slots can hold one of the data types, in this case an int
  • Each array element is referenced by name and an index inside of square brackets
  • For instance: 
    scores[3] = 98;
  • In Java, the slots of arrays are numbered starting at 0, as shown below:

    scores = 
     
     
     
    98
     
    [0]
    [1]
    [2]
    [3]
    [4]

  • Thus, the assignment to the slot with index 3 is put into the fourth slot
  • The index can be any integer expression
    • int n = 2;
score[n + 1] = 99;
  • You can use an indexed array variable like any regular variable
    • score[0] = score[1] + 1;

^ top

6.1.4: Initializing Array Values

  • You can assign a value to an array element any time after the array is declared: 
    int[] score = new int[5];
score[0] = 90;
score[1] = 95;
score[2] = 87;
score[3] = 89;
score[4] = 98;

Static Initialization

  • You can also initialize array elements in the declaration statement
    • Called static initialization
    • Use a comma-separated list inside curly-braces
    int[] score = {90, 95, 87, 89, 98};
  • This statement produces the same array as the previous six statements
  • The compiler counts the number of elements and allocates an array of the correct size

Default Values

  • Uninitialized array elements are assigned default values:
    • Integer (byte, short, int, long): 0
    • Floating-point (float, double): 0.0
    • Character (char): '\u0000'
    • Boolean: false
    • Objects: null

^ top

6.1.5: Processing Array Values in a Loop

  • Array processing is easily done in a loop
  • A for loop is commonly used to process array elements
  • For example, to initialize array elements to a known value: 
    double[] scores = new double[5];
for (int i = 0; i < scores.length; i++) {
    scores[i] = 100;
}
  • Note the use of the length instance variable in the array loop
  • One of the advantages of using a class type is that an array always knows how many elements it has allocated

Displaying an Array

  • Similarly, we can also use a loop to display the contents of an array: 
    System.out.println("You entered:");
for (int i = 0; i < scores.length; i++) {
    System.out.println(scores[i]);
}

Initializing From the Keyboard

  • We can also use a loop to initialize values from the keyboard
  • This is shown in the example application below
  • Note that the loop counter and array index counts from 0 to length - 1

Example of Initializing from the Keyboard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.Scanner;

public class ScoreReader {
    public static void main(String[] args) {
        Scanner input  = new Scanner(System.in);

        System.out.print("Enter your scores.\n"
            + "Number of scores: ");
        int num = input.nextInt();

        double[] scores = new double[num];
        for (int i = 0; i < scores.length; i++) {
            System.out.print("Enter score "
                + (i + 1) + ": ");
            scores[i] = input.nextDouble();
        }

        System.out.println("You entered:");
        for (int i = 0; i < scores.length; i++) {
            System.out.println(scores[i]);
        }
    }
}

^ top

6.1.6: Using the Enhanced for Loop with Arrays

  • In addition to the standard for loop, Java provides an enhanced for loop
  • This loop is specially designed to work with arrays and other collections of data
    • In other languages, this loop is known as the foreach loop
  • Syntax: 
    for (dataType variableName : arrayName) {
    // statements to execute
}
  • Where:
    • dataType: the data type of all the array items
    • variableName: the name to use for each variable
    • arrayName: the name of the array
  • Note that you do not code initialization, test and increment statements
  • Instead, you declare a variable that refers to each array element
  • Within the loop, you use this variable to access each array element
  • To understand how this works, lets look at an example

Example of Enhanced for Loop

int[] score = {90, 95, 87, 89, 98};
for (double aScore : score) {
    System.out.println(aScore);
}

Example Comparison to Regular for Loop

int[] scores = {90, 95, 87, 89, 98};
for (int i = 0; i < scores.length; i++) {
    System.out.println(scores[i]);
}

^ top

6.1.7: Array Index Out of Range

  • A common error is using a nonexistent index
  • For an array of length 5, the indexes are 0 through 4
  • An index beyond this is out of bounds
  • Using an out of range index value produces an error message!
    • ArrayIndexOutOfBoundsException
  • For example, using the following code:
1
2
3
4
5
6
7
8
9
10

public class WeekDays {
    public static void main(String[] args) {
        String[] day = {"Sunday", "Monday",
            "Tuesday", "Wednesday", "Thursday",
            "Friday", "Saturday"};
        for (int x = 0; x < day.length; x++) {
            System.out.println(day[x]);
        }
    }
}
  • Trying to use an index less than 0 or more than length - 1 causes an error
    • ArrayIndexOutOfBoundsException

^ top

6.1.8: Arrays and Objects

  • The elements of an array of objects are not actual objects, but rather references to objects
  • This is an important point that can cause confusion
  • Allocating an array of objects only allocates space for a reference to each object
  • Space is not allocated for the actual object until you create the object and assign it to the array element
  • For example, the following code declares an array of String object references 
    String names [] = new String [4];
  • All the elements of the array are assigned a default value of null
  • Actual objects are not assigned until the following lines: 
    names [0] = new String("Hi");
names [1] = "Mom";
names [2] = someObject.toString();
  • The following diagram illustrates this point

    array of objects

  • The analog in C/C++ is an array of pointers to objects
  • However, Java automatically dereferences the pointers unlike C/C++
  • Thus it may seem like you are working with an array of actual objects rather than references to objects

Example of An Array of Objects

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class ArrayObjs {
    public static void main(String[] args) {
        String[] weekdays = new String[7];
        weekdays[0] = "Unknown";
        weekdays[1] = "Tuesday";
        weekdays[2] = "Wednesday";
        weekdays[3] = "Thursday";
        weekdays[4] = "Friday";

        for (int i = 0; i < weekdays.length; i++) {
            System.out.println(weekdays[i]);
        }
        System.out.println();

        weekdays[0] = "Monday";
        weekdays[5] = "Thursday";
        weekdays[6] = "Friday";

        for (String day : weekdays) {
            System.out.println(day);
        }
        System.out.println();
    }
}

^ top

6.1.9: Summary

  • Arrays are convenient ways to process a list of data
  • You declare an array with a single statement:
    • DataType[] arrayName = new DataType[length];
  • Each array element is referenced by name and an index inside of square brackets
  • You can use an indexed array variable like any regular variable
    • score[0] = score[1] + 1;
  • You can initialize array elements individually with an assignment statement
    • score[0] = 90;
  • A more convenient way is to use an initializer list
    • int score[] = {90, 95, 87, 89, 98};
  • You can use loops to assign values to an array and to display array values
  • The programmer must be very careful to keep the array index within bounds
  • Otherwise an error message will result
    • ArrayIndexOutOfBoundsException

Check Yourself

  1. What is an array?
  2. When should you use an array?
  3. What are the two ways of declaring an array?
  4. How do you access an array element?
  5. What are two ways that you can initialize array elements?
  6. How can you check the capacity of an array while your program is running?
  7. If an array named scores had 100 elements in it, what code would you write to display all the elements?
  8. What happens if you try to print the tenth item of an eight item array?

^ top

Exercise 6.1

Take one minute to prepare an answer the following questions.

  1. Is it possible to create arrays of length zero?
  2. Given the following declaration: 
    String[] word = new String[5]
    what is:
    1. the array name?
    2. the base type?
    3. The length of the array?
    4. the range of values an index accessing this array can have?
    5. the value of one of the elements of this array

^ top

6.2: Arrays and References

Learner Outcomes

At the end of the lesson the student will be able to:

  • Pass arrays as arguments
  • Use arrays in methods
  • Return arrays from methods
  • Obtain values from the array passed to the main method

^ top

6.2.1: Arrays Are Objects

  • Just like other class types, an array variable is a reference
  • For example, an array of doubles named prices is stored like this:

  • As you can see there are two ways to view an array:
    1. as a collection of indexed variables
    2. as a single reference variable
  • Arrays in most languages, such as C/C++, are reference types as well

^ top

6.2.2: Arrays as Method Parameters

  • You can use an entire array as an argument to a method
  • When passing the array as an argument, you use just the array name and no brackets: 
    showArray(days);
  • Within the method you can access the array elements
  • For example: 
    public static void print(int[] values) {
    System.out.println("You entered "
        + values.length + " numbers:");
    for (int item : values) {
        System.out.println(item);
    }
}
  • Within the method, you can determine the array size from the length variable

Changing Array Elements in Methods

  • Recall that an array argument is actually a reference type
  • Thus any action taken on the parameter is actually taken on the original argument
  • This means you can change array elements in methods
  • You can see this in the following example

Example Changing Array Elements in a Method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import java.util.Scanner;

class ArrayInput {
    public static void main(String [] args) {
        Scanner input = new Scanner(System.in);
        System.out.print("How many items? ");
        int numItems = input.nextInt();
        int[] data = new int[numItems];

        fillUp(data);
        print(data);
    }

    // Fills an array with values from the keyboard
    public static void fillUp(int data[]) {
        Scanner input = new Scanner(System.in);
        for (int i = 0; i < data.length; i++) {
            System.out.print("Enter number " + (i + 1)
                + ": ");
            data[i] = (int) input.nextDouble();
        }
    }

    // Displays an array to the screen
    public static void print(int[] values) {
        System.out.println("You entered "
            + values.length + " numbers:");
        for (int item : values) {
            System.out.println(item);
        }
    }
}

^ top

6.2.3: Returning an Array

  • Methods can return an array reference
  • You can see this in the following example

Example Returning an Array

1
2
3
4
5
6
7
8
9
10
11
12

public class ArrayMaker {
    public static void main(String arg[]) {
        char[] vowels = makeVowelsArray();
        for(char ch : vowels)
            System.out.println(ch);
    }

    public static char[] makeVowelsArray() {
        char[] vowelArray = {'a', 'e', 'i', 'o', 'u'};
        return vowelArray;
    }
}

^ top

6.2.4: Command-line Arguments

  • Recall that every Java application must have a method called main() 
    public static void main(String[] args) { }
  • Notice that the parameter args is an array of Strings
  • Arguments are passed to the program by the operating system
  • All words after the class name passed in the args array
    • java ArgEcho Java Rules!
  • Number of parameters can be determined from args.length
    • System.out.println(args.length);
  • args is a parameter of type String[]

Example of Processing Command-line Arguments

1
2
3
4
5
6
7
8

public class ArgEcho {
    public static void main(String[] args) {
        for (int i = 0; i < args.length; i++) {
            System.out.print("Arg " + i + ": ");
            System.out.println(args[i]);
        }
    }
}
  • Produces the output:
    • >java ArgEcho Hi Mom!
Arg 0: Hi
Arg 1: Mom!

^ top

6.2.5: Summary

  • You can pass an array to a method
  • A method may return an array
  • Can change the array element within a method body
    • Because arrays are reference types
    • Location of the array passed to the method
    • When an element is accessed, the original location is used
  • Operating system sends arguments to the String[] parameter of method main
  • Can access these elements like any other array

Check Yourself

  1. What is the header for a method named "showArray" that accepts an integer array?
  2. If the fillUp() method has an array parameter, and you change elements of the array inside the method, what happens to those changed elements when the method returns?
  3. What is the header for a method named makeArray() that accepts no parameters but returns a char array?
  4. The main() method has a String[] parameter. For a program named ArgEcho, what would you type at the command line to pass the values "hello" and "world" to the program?

^ top

Exercise 6.2

Take one minute to prepare an answer the following question:

  1. What is wrong with the following method definition?
    2. public void doubleSize(int[] a) {
    a = new int[a.length * 2];
}
    1. An array length must be a literal integer and cannot be created from a calculated expression.
    2. The length of the array a is unknown when declaring the new array.
    3. Parameter a already has an array assigned and you cannot assign a new value to parameter a.
    4. The code is useless because parameter a goes out of scope when the method returns.

^ top

6.3: Programming With Arrays

Learner Outcomes

At the end of the lesson the student will be able to:

  • Test array equality
  • Compute statistics on arrays of data
  • Search an array
  • Sort an array
  • Choose the best algorithm for searching an array

^ top

6.3.1: Using Arrays Interactively

  • The size of an array is known as its dimension
  • Sizing an array at run time is referred to as run-time dimensioning
  • The following example uses a value read from the keyboard to allocate space for an array

Example of Run-Time Dimensioning

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import java.util.Scanner;

class ArrayInput {
    public static void main(String [] args) {
        Scanner input = new Scanner(System.in);
        System.out.print("How many items? ");
        int numItems = input.nextInt();
        int[] data = new int[numItems];

        fillUp(data);
        print(data);
    }

    // Fills an array with values from the keyboard
    public static void fillUp(int data[]) {
        Scanner input = new Scanner(System.in);
        for (int i = 0; i < data.length; i++) {
            System.out.print("Enter number " + (i + 1)
                + ": ");
            data[i] = (int) input.nextDouble();
        }
    }

    // Displays an array to the screen
    public static void print(int[] values) {
        System.out.println("You entered "
            + values.length + " numbers:");
        for (int item : values) {
            System.out.println(item);
        }
    }
}

Check Yourself

  1. When is the size of the array decided?
  2. What does the data array contain before the user enters any values?
  3. What is the value of data.length after one item has been entered?
  4. How do we know how many items have been entered by the user?

^ top

6.3.2: Testing Array Equality

  • Remember that arrays are objects
  • Thus, array variables are reference types

  • Tests using == checks if the memory addresses are the same
    • if (a == b)
  • For example, what does the following code print?
1
2
3
4
5
6
7
8
9
10
11

public class ArrayChecker {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        int[] b = {1, 2, 3};
        if (a == b) {
            System.out.println("a == b");
        } else {
            System.out.println("a != b");
        }
    }
}
  • Both arrays have the same elements
  • However, they are stored at different locations in memory
  • Thus, they do not have the same memory address

Testing Array Elements for Equality

  • To test array elements for equality, need to check each element
  • Define an equals method that returns true if and only if all the array elements are equal
  • Arrays must also be the same length
  • Updating our original code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class ArrayTester {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        int[] b = {1, 2, 3};

        if (a == b) {
            System.out.println("a == b");
        } else {
            System.out.println("a != b");
        }

        if (equals(a, b) == true) {
            System.out.println("a equals b: ");
        } else {
            System.out.println("a not equal to b");
        }
    }

    public static boolean equals(int[] a, int[] b) {
        boolean match = true; //tentatively
        if (a.length != b.length) {
            match = false;
        } else {
            for (int i = 0; i < a.length; i++) {
                if (a[i] != b[i]) match = false;
            }
        }
        return match;
    }
}

^ top

6.3.3: Searching an Array

  • Searching an array is about finding the index where a value is stored
  • Many techniques for searching an array for a particular value
  • Easiest technique is sequential search, whose algorithm is:
    1. Start at the beginning of the array
    2. Compare each value in sequence
    3. If the value is found, then return the index
    4. Continue until you reach the end of the array
    5. If no match is found, return -1
  • The following program defines a method that implements this algorithm

Example of Searching an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

import java.util.Scanner;

public class ArraySearch {
    /**
        Finds the position of an item in an array.

        @param arr The array with the elements to search
        @param item The value to search for.
        @return The index of the first match, or -1 if
            not found.
     */
    public static int find(int[] arr, int item) {
        for (int i = 0; i < arr.length; i++) {
            if (item == arr[i]) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String [] args) {
        int[] arr = {12, -3, 9, -5, 10, 42};
        for (int i = 0; i < arr.length; i++) {
            System.out.println(i + ": " + arr[i]);
        }

        Scanner input = new Scanner(System.in);
        System.out.print("\nEnter a search value: ");
        int key = input.nextInt();
        int slot = find(arr, key);
        if (slot >= 0) {
            System.out.println("Found " + key
                +" in slot " + slot);
        } else {
            System.out.println(key + " not found");
        }
    }
}

^ top

6.3.4: Removing Elements

  • Once we find an item in a list, we may want to remove it
  • However, what does it mean to remove an element from an array?
  • The problem with arrays in Java, and many other languages, is that the size of an array is fixed
  • What we can do is shift the elements to overwrite the element we want to remove
  • For instance, we could write a method like this: 
    public static void remove(int[] arr, int pos) {
    for (int i = pos; i < arr.length - 1; i++) {
        arr[i] = arr[i + 1];
    }
}
  • Note that the last element is now "extra" and must not be used
  • When arrays have unused elements at the end, they are sometimes called partially-filled arrays
  • The following diagram shows the remove operation
Shift items down the list

Using arraycopy()

  • Rather than using a loop, you should use arraycopy()
  • System.arraycopy() is a method designed to copy array elements efficiently
  • General syntax: 
    arraycopy(src, srcPos, dest, destPos, length);
  • Where:
    • src: the source array
    • srcPos: the starting position of the copy operation in the source array
    • dest: the destination array
    • destPos: the starting position of the copy operation in the destination array
    • length: the number of elements to copy
  • If the dest array is the same as the src array, the copy is made in the same array
  • To see how to use arraycopy(), we rewrite our remove() method using arraycopy(): 
    public static void remove(int[] arr, int pos) {
    int numItems = arr.length - (pos + 1);
    System.arraycopy(arr, pos + 1, arr, pos, numItems);
}
  • In this method, we are copying from pos + 1 to pos within the same array
  • We specify the number of elements to copy using the formula: 
    int numItems = arr.length - (pos + 1);
  • The following example applications shows the remove() method

Removing Elements of an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.util.Scanner;

public class ArrayRemove {
    /**
        Removes an item from the vector preserving the
        order.

        @param arr The array with the elements to search.
        @param pos The number of the element to remove.
     */
    public static void remove(int[] arr, int pos) {
        int numItems = arr.length - (pos + 1);
        System.arraycopy(arr, pos + 1, arr, pos, numItems);
    }

    public static void main(String [] args) {
        int[] arr = {12, -3, 9, -5, 10, 42};
        for (int i = 0; i < arr.length; i++) {
            System.out.println(i + ": " + arr[i]);
        }

        Scanner input = new Scanner(System.in);
        System.out.print("\nEnter position to remove: ");
        int key = input.nextInt();
        remove(arr, key);

        for (int i = 0; i < arr.length; i++) {
            System.out.println(i + ": " + arr[i]);
        }
    }
}

^ top

6.3.5: Inserting Elements

  • If we want to insert an element into an array, we have to be careful about the last element
  • If we shift elements up by one, that last element is overwritten and the data lost
  • One solution is to use a partially-filled array to allow room for the last element
  • Then only the data in an unused element is lost
  • The following method uses this approach: 
    public static void insert(int[] arr, int pos, int data) {
    int numItems = arr.length - (pos + 1);
    System.arraycopy(arr, pos, arr, pos + 1, numItems);
    arr[pos] = data;
}
  • Also, the following diagram shows the insert operation
Add new element and move items up

Growing an Array

  • Another approach to inserting is to increase the size of the array by some number of elements before the insertion operation
  • The insertion operation follows these steps:
    1. Increase the size of the array by a fixed amount, such as 1
    2. Move all elements above the insertion location up by one slot
    3. Assign the value at the insertion location
  • For example: 
    public static int[] insert2(int[] arr, int pos, int data) {
    int[] newArr = new int[arr.length + 1];
    System.arraycopy(arr, 0, newArr, 0, pos);
    int numItems = arr.length - pos;
    System.arraycopy(arr, pos, newArr, pos + 1, numItems);
    newArr[pos] = data;
    return newArr;
}
  • We show both these methods in the following example code

Inserting Elements into an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

import java.util.Scanner;

public class ArrayInsert {
    /**
        Inserts an item into an array, overwriting the last
        element.

        @param arr The array with the elements to search.
        @param pos The number of the element to remove.
        @param data The element to insert.
     */
    public static void insert(int[] arr, int pos, int data) {
        int numItems = arr.length - (pos + 1);
        System.arraycopy(arr, pos, arr, pos + 1, numItems);
        arr[pos] = data;
    }

    /**
        Inserts an item into an array, growing the size of
        the array by one, and returning the new larger array.

        @param arr The array with the elements to search.
        @param pos The number of the element to remove.
        @param data The element to insert.
        @return A new array with the item inserted.
     */
    public static int[] insert2(int[] arr, int pos, int data) {
        int[] newArr = new int[arr.length + 1];
        System.arraycopy(arr, 0, newArr, 0, pos);
        int numItems = arr.length - pos;
        System.arraycopy(arr, pos, newArr, pos + 1, numItems);
        newArr[pos] = data;
        return newArr;
    }

    public static void main(String [] args) {
        int[] arr = {12, -3, 9, -5, 10, 42};
        for (int i = 0; i < arr.length; i++) {
            System.out.println(i + ": " + arr[i]);
        }

        Scanner input = new Scanner(System.in);
        System.out.print("\nEnter position to insert: ");
        int key = input.nextInt();
        System.out.print("\nEnter value to insert: ");
        int data = input.nextInt();
        insert(arr, key, data);
//        arr = insert2(arr, key, data);

        for (int i = 0; i < arr.length; i++) {
            System.out.println(i + ": " + arr[i]);
        }
    }
}

Performance of Insertions and Deletions

  • When an array changes size, it is called a dynamic array
  • Creating a new array, copying elements from the old array and deleting the old array takes computer time and memory
  • The time and memory is proportional to the length of the array, or O(n) using big O notation
  • To improve the performance of dynamic array, it is common to use a partially-filled array until the array is full
  • When more capacity is needed in a filled array, the array size is increased
  • Typically, array size is doubled when the capacity is increased
  • Java has a library, called the Java Collections Framework, that includes dynamic arrays
  • We will study dynamic structures, such as dynamic arrays, later in the course

^ top

6.3.6: Sorting an Array

  • Sorting is a common task for computers, for example:
    • Sort numbers in ascending order
    • Sort numbers in descending order
    • Sort strings in alphabetic order
  • Many different algorithms for sorting, including:
    • Bubble sort - move item up until in right place
    • Insertion sort - add elements to list one at a time
    • Selection sort - pick 1st, then 2nd, etc.
    • Quick sort - divide and conquer

Selection Sort

  • Selection sort is one of the easiest -- but not the most efficient
  • General algorithm:
    1. Find the smallest element
    2. Swap with the first element
    3. Find the smallest element in the rest of the list
    4. Swap with the first element of the rest of the list
    5. Repeat until the list is sorted
Pass a[0] a[1] a[2] a[3] a[4] a[5] a[6]
Original 10 7 29 14 -4 -12 21
First -12 7 29 14 -4 10 21
Second -12 -4 29 14 7 10 21
Third -12 -4 7 14 29 10 21
Fourth -12 -4 7 10 29 14 21
Fifth -12 -4 7 10 14 29 21
Sixth -12 -4 7 10 14 21 29

Selection Sort Code

  • Following is selection sort code
  • Have added some statements to show action for each pass
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

public class SelectionSort {
    public static void main(String [] args) {
        int[] a = {10, 7, 29, 14, -4, -12, 21};

        System.out.print("Original array: ");
        print(a);
        sort(a);
        System.out.print("\nSorted array: ");
        print(a);
    }

    public static void print(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + ", ");
        }
        System.out.println();
    }

    public static void sort(int[] a) {
        int index, indexOfMin;
        for (index = 0; index < a.length - 1; index++) {
            indexOfMin = findMin(a, index, a.length - 1);
            swap(a, index, indexOfMin);
            System.out.print("Pass#" + index + ": ");
            print(a);
        }
    }

    public static int findMin(int[] a, int start, int end) {
        int indexOfMin = start;
        for (int i = start + 1; i <= end; i++) {
            if (a[i] < a[indexOfMin]) {
                indexOfMin = i;
            }
        }
        return indexOfMin;
    }

    public static void swap(int[] a, int first, int second) {
        System.out.println("\nSwapping " + a[first]
            + " with " + a[second]);
        int temp = a[first];
        a[first] = a[second];
        a[second] = temp;
    }
}
  • Note that every element in the array must have a value
  • Can the array have duplicate items?
  • Also note that the larger task was broken into smaller tasks using methods
    • Helps to organize program and improve clarity

What About Bubble Sort?

  • Another sorting algorithm that is easy to understand and use
  • General algorithm:
    1. Make array.length passes through the array
    2. For each pass, compare each array element with the next element
    3. If the current element is larger than the next one, swap them
  • Not an efficient sorting algorithm
  • Sometimes simple algorithms perform poorly
  • Simple algorithms are still useful because: easy to program and understand
  • If better performance is needed, you replace them with a faster algorithm
  • More information: Sorting Algorithms
    • Includes Java source code
  • Also: Sorting Algorithms

^ top

6.3.7: Binary Search

  • Once an array is sorted, you can use binary search to find an item
  • Binary search is much faster than sequential search

Binary Search Algorithm

  • A key value is searched for among the values stored in the array.
  • Two index variables lowIdx and highIdx are used to limit the scope of the search.
  • The search proceeds until the element searched for is found or the scope between lowIdx and highIdx is exhausted.
    • The index middleIdx is computed as (lowIdx + highIdx) / 2.
    • If key = data[middleIdx] the search is successful.
    • If key < data[middleIdx], highIdx is lowered to middleIdx.
    • If key > data[middleIdx], lowIdx is raised to middleIdx.
    • If the scope between lowIdx and highIdx is exhausted, the search is unsuccessful.
  • Demonstration applet: BinarySearch

Binary Search Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

import java.util.Scanner;

public class BinarySearch {
    // find the index of key in array a
    // return -1 if key is not found
    public static int binarySearch(int[] a, int key) {
        int step = 0;
        int lowIdx = 0;
        int highIdx = a.length - 1;
        int middleIdx;
        while (lowIdx <= highIdx) {
            step++;
            middleIdx = (lowIdx + highIdx) / 2;
            System.out.println("Step#" + step
                    + " lowIdx=" + lowIdx
                    + " highIdx=" + highIdx
                    + " middleIdx=" + middleIdx);
            if (a[middleIdx] == key) {
                return middleIdx; // just right
            } else if (a[middleIdx] < key) {
                lowIdx = middleIdx + 1; // too small
            } else {
                highIdx = middleIdx - 1; // too big
            }
        }
        return -1; // not found
    }

    public static void main(String [] args) {
        int[] data = {-12, -4, 7, 10, 14, 21, 29};
        System.out.print("Searching array: ");
        for (int item : data) {
            System.out.print(item + " ");
        }
        System.out.println();
        Scanner input = new Scanner(System.in);
        System.out.println("Enter a search value: ");
        int key = input.nextInt();
        int slot = binarySearch(data, key);
        if (slot >= 0) {
            System.out.println("Found " + key
                +" in slot " + slot);
        } else {
            System.out.println(key + " not found");
        }
    }

}

How Much Faster is Binary Search?

  • Given the sorted array:

    • a[0] a[1] a[2] a[3] a[4] a[5] a[6]
    -12 -4 7 10 14 21 29

  • How many steps to find the value of 14 using sequential search?
  • How many steps to find the value of 14 using binary search?
  • On average for an array of n elements:
    • Sequential search takes n / 2 steps
    • Binary search takes 2 * log2(n) + 2 steps maximum
  • Translating to some array sizes:

    • Array Size floor(log2(n)) + 1
    1 1
    10 4
    100 7
    1000 10
    10,000 14

  • Binary search quickly becomes worth the effort of its implementation
  • Binary search is one algorithm a programming professional should know!

^ top

6.3.8: Summary

  • Arrays can be dimensioned at run time
  • Also, you can easily enter values into an array for later processing
  • When comparing arrays, you must be careful not to use the == operator
  • The == operator returns tru if two array reference refer to the same array
  • The == operator does not determine if two seperate arrays have the same content
  • To compare the content of two arrays, you can use a loop as we discussed: 
    public static boolean equals(int[] a, int[] b) {
    boolean match = true; //tentatively
    if (a.length != b.length) {
        match = false;
    } else {
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) match = false;
        }
    }
    return match;
}
  • We looked at several algorithms for use with arrays including:
    • Linear search of an array for a specific value
    • Removing an elementfrom an array
    • Inserting an element into an array
    • Sorting an array
    • Binary search of a sorted array

Check Yourself

  1. When is the size of the array decided: compile time or run time?
  2. After declaring an int array of 10 elements, and before assigning any values to the array, what value does each array element hold?
  3. If two separate arrays, array1 and array2, contain the same values, what does the following statement print? 
    System.out.println(array1 == array2);
  4. If an int array named scores had 100 elements in it, what code would you write to find the index of the first occurrence of 98?
  5. Do all sorting algorithms take the same amount of time to sort arrays?
  6. What is binary search?
  7. Why is binary search faster than linear search on average?
  8. In what condition must all the elements of an array be to use binary search?

^ top

Exercise 6.3

Take one minute to prepare an answer the following question:

  1. What would be the contents of the following array after each pass of SelectionSort?
    2. int[] array = {9, 21, -7, 2, 87, -19, 47}

^ top

6.4: Multidimensional Arrays

Learner Outcomes

At the end of the lesson the student will be able to:

  • Use two-dimensional (2D) arrays
  • Apply the techniques of 2D arrays to higher dimensions

^ top

6.4.1: Introducing Multidimensional Arrays

  • Arrays in Java are objects
  • Array elements can be objects, such as Strings
  • Thus, array elements can reference other arrays
  • This allows Java to have arrays of multiple dimensions
    • String[] one;
double[][] two;
char[][][] three;
  • Each added dimension requires one more pair of square braces
  • We will focus on two-dimensional (2D) arrays in this section
  • You then use similar techniques for multidimensional arrays

Rows and Columns

  • Two-dimensional (2D) arrays are like a spreadsheet or table
    • First dimension is the row
    • Second dimension is the column
    • Array elements are the intersection of a row and column
  • For the array named data:

    • data[0][0] data[0][1] data[0][2]
    data[1][0] data[1][1] data[1][2]

^ top

6.4.2: Declaring and Allocating 2D Arrays

  • To declare as a 2D int array:
    • int[][] data;

    or

    int data[][];

    or even

    int[] data[];
  • You can allocate 2D arrays dynamically
    • int data[][]; // C-style
data = new int[2][3];

    or

    int[][] data = new int[2][3];

    or

    int[][] data = new int[2][];
data[0] = new int[3];
data[1] = new int[3];

^ top

6.4.3: Initializing 2D Arrays

  • Like one-dimensional arrays, 2D array elements are assigned default values based on the array type:
    • Integer (byte, short, int, long): 0
    • Floating-point (float, double): 0.0
    • Character (char): '\u0000'
    • Boolean: false
    • Objects: null
  • You can initialize 2D arrays with static initializers or loops
  • For example: 2 row by 3 column array using static initializers:
    • int[][] data = {{1,2,3}, {4,5,6}};
  • You can process multi-D arrays by nesting loops
  • Each loop has its own counter that corresponds to an index
1
2
3
4
5
6
7
8
9
10
11
12

public class Array2D {
    public static void main(String[] args) {
        int[][] data = {{1, 2, 3}, {2, 4, 6}};
        for (int i = 0; i < data.length; i++) {
            System.out.print("Row " + i + ": ");
            for (int j = 0; j < data[i].length; j++) {
                System.out.print(data[i][j] + ", ");
            }
            System.out.println();
        }
    }
}
  • Produces the output:
    • Row 0: 1, 2, 3,
Row 1: 2, 4, 6,

^ top

6.4.4: Example: Creating a Table

  • Methods may have multi-D array parameters
  • Methods may return a multi-D array as the value returned
  • Similar to 1D arrays, but with more brackets
  • Example: 2D int array of the multiplication table

Example of a Two-Dimesnional Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class MultTable {
    public static void main(String[] args) {
        int[][] table = makeTable(9);
        print(table);
    }

    public static int[][] makeTable(int size) {
        int[][] table = new int[size][size];
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < table[i].length; j++) {
                table[i][j] = (i + 1) * (j + 1);
            }
        }
        return table;
    }

    public static void print(int[][] table) {
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < table[i].length; j++) {
                if (table[i][j] < 10) {
                    System.out.print(" ");
                }
                System.out.print(table[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Notes on the Code

  • Method makeTable returns a 2D table 
    public static int[][] makeTable(int size) {
  • Method print takes a 2D int array as a parameter 
    public static void print(int[][] table) {

^ top

6.4.5: Ragged Arrays

  • Ragged arrays have rows of unequal length
  • Rows can have arrays assigned of different lengths
  • Produces rows with different numbers of columns
  • For example:
    • int data[][];
data = new int[3][];  // allocate columns
data[0] = new int[5]; // allocate row 0
data[1] = new int[0]; // allocate row 1
data[2] = new int[3]; // allocate row 2
  • Can also use static initialization and get the same result
    • int[][] data = {{1,2,3,4,5}, {}, {6,7,8}};

Example of a Ragged Array

1
2
3
4
5
6
7
8
9
10
11
12

public class ArrayRagged {
    public static void main(String[] args) {
        int[][] data = {{1,2,3,4,5}, {}, {6,7,8}};
        for (int i = 0; i < data.length; i++) {
            System.out.print("Row " + i + ": ");
            for (int j = 0; j < data[i].length; j++) {
                System.out.print(data[i][j] + ", ");
            }
            System.out.println();
        }
    }
}

^ top

6.4.6: Summary

  • Arrays can have more than one index
  • Each index is called a dimension
  • Thus, multidimensional arrays have multiple indexes,
  • For example, an array with two indexes is a two-dimensional array.
  • 2D array can be thought of as a grid or table with rows and columns:
  • One index is for the row, the other for the column.
  • Multi-dimensional arrays in Java are implemented as arrays of arrays,
  • 2D array is a 1D array of 1D arrays.

^ top

Exercise 6.4

Take one minute to prepare an answer the following question:

  1. Which one of the following 2D array declarations and initializations is not valid?
    1. int[] a[] = {{1, 2}, {1}, {}, {1, 2, 3, 4}};
    2. int b[] = new int[2] {1, 2};
    3. int[] c = new int[] {1, 0, 2, 3};
    4. int d[] = new int[] {1, 2};
    5. int e[][] = {{1,2}, new int[2]};

^ top

Wrap Up

Due Next:
A5-Paradise Roller (3/18/09)
A6-Card Games (3/25/09)

^ top

Home | Blackboard | Announcements | Schedule | Room Policies | Course Info
Help | FAQ's | HowTo's | Links
Last Updated: March 29 2009 @18:00:19