2D Array Array Combine Array Length ArrayList for sort try

Array

In Java arrays are a fundamental type, used often inside other types. We find helpful methods in the Arrays class, from java.util.Arrays.

In many programs we only need to store a certain number of elements (like 10 or 20). Arrays are a good fit for these situations.

First example

Arrays use the square brackets to index elements. These brackets are also used in array declarations. Here we do some simple operations on an array.

Part 1 We create an array of five int elements. When created, the ints all have values of 0.

Part 2 We assign three elements into the newly-created int array. The first index in an array is zero.

Part 3 We use length in for-loops as the upper boundary. Every array has a length, even if it has zero elements.

public class Program {
    public static void main(String[] args) {

        // Part 1: create int array.
        int[] array = new int[5];

        // Part 2: assign first three elements.
        array[0] = 1;
        array[1] = 10;
        array[2] = 100;

        // Part 3: loop over elements.
        for (int i = 0; i < array.length; i++) {
            // Get value.
            int value = array[i];
            // Print value.
            System.out.println(value);
        }
    }
}1
10
100
0
0

Types

An array can have any type. Here we create a four-element array of chars. We assign characters to the indexes 0 through 3. And then we use a loop to iterate.

Tip For-each loop syntax is often applied to arrays. This reduces syntax complexity—no index variable is used.

public class Program {
    public static void main(String[] args) {

        // Create an array of four chars.
        char[] values = new char[4];
        values[0] = 'j';
        values[1] = 'a';
        values[2] = 'v';
        values[3] = 'a';

        // Loop over array with for-loop.
        for (char value : values) {
            System.out.println(value);
        }
    }
}j
a
v
a

Initialize

A shorter, simpler syntax can be used to initialize an array. We must use curly brackets. We specify the initial elements within these brackets.

Detail Here we see the syntax for an int array and a String array. Each array in this example has three elements.

public class Program {
    public static void main(String[] args) {

        // Two input arrays.
        int[] array1 = {1, 3, 5};
        String[] array2 = {"frog", "toad", "squirrel"};

        // Array lengths.
        System.out.println(array1.length);
        System.out.println(array2.length);

        // First elements in each array.
        System.out.println(array1[0]);
        System.out.println(array2[0]);
    }
}3
3
1
frog

Loop in reverse

Sometimes we want to do things backwards. To loop over an array from end to start, we begin at the last index (equal to length minus one). We decrement and proceed to 0.

public class Program {
    public static void main(String[] args) {

        boolean[] values = { false, true, true, true };

        // Loop over array elements in reverse order.
        for (int i = values.length - 1; i >= 0; i--) {
            System.out.println(values[i]);
        }
    }
}true
true
true
false

Empty

How can we create an empty array? The array initializer syntax (with curly brackets) works. Or we can allocate a new array, as usual, but specifying zero as its length.

public class Program {
    public static void main(String[] args) {

        // Two empty arrays.
        int[] array1 = {};
        int[] array2 = new int[0];

        // Each has zero length.
        System.out.println(array1.length);
        System.out.println(array2.length);
    }
}0
0

Null arrays

An empty array is different from a null array. With an empty, zero-element array, we safely use fields and methods. With a null array, this provokes a NullPointerException.

Here We try to access the length of the array, but the pointer is null. So we get an exception and the program ends.

public class Program {
    public static void main(String[] args) {

        int[] values = null;
        int size = values.length;
    }
}Exception in thread "main" java.lang.NullPointerException
    at Program.main(Program.java:5)

`Sort`

We sort an array with the Arrays.sort method. This is part of the java.util.Arrays class. This method sorts the array in-place, meaning no value is assigned to the sort method.

Tip The Arrays.sort method by default uses an ascending sort, meaning elements are ordered from low to high.

Tip 2 For large arrays, the parallelSort method can enhance performance (on systems with multiple processor cores).

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

        int[] array = { 100, 20, 0, 200 };

        // Call Arrays.sort on the int array.
        Arrays.sort(array);

        for (int elem : array) {
            System.out.println(elem);
        }
    }
}0
20
100
200

Fill

Often an array needs to be filled with a certain value. We invoke the Arrays.fill method: we specify an array, and a value. Each element is set to that value.

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

        int[] values = new int[10];

        // Fill array with this number.
        Arrays.fill(values, 5);

        for (int value : values) {
            System.out.print(value);
            System.out.print(' ');
        }
    }
}
5 5 5 5 5 5 5 5 5 5

`Arrays.copyOf`

This method creates a copy of a target array. We specify the length of the new array. So we can reduce or increase the size, filling new elements with default values.

Detail This is essentially a resize method. An array's length is not dynamic. Resizing can only be done when copying.

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

        int[] values = { 10, 20, 30, 40 };

        // Copy and display first 3 elements.
        int[] copy = Arrays.copyOf(values, 3);
        for (int value : copy) {
            System.out.println(value);
        }
        System.out.println();

        // Copy five elements.
        int[] copy2 = Arrays.copyOf(values, 5);
        for (int value : copy2) {
            System.out.println(value);
        }
    }
}10
20
30

10
20
30
40
0

`Arrays.copyOfRange`

With this method, we specify a start index and an end index. A new array, containing only that range, is created and returned.

Argument 1 This is the array we are trying to take a copy from. Here we use an int array with several integers in it.

Argument 2 The second argument to copyOfRange is the start index—the element at this index will be copied.

Argument 3 The third argument we pass to Arrays.copyOfRange is the last index int. This value is exclusive (not included).

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

        int[] values = { 0, 10, 20, 30, 40, 50 };

        // Copy elements from index 2 to 5 (2, 3, 4).
        int[] result = Arrays.copyOfRange(values, 2, 5);
        for (int value : result) {
            System.out.println(value);
        }
    }
}20
30
40

Sentinels

In an array, we can store special values that indicate the array ends. These are sentinel elements. In this program, we use the value -1 for a sentinel.

And We readjust the sentinel value without modifying the rest of the array. This is a fast way to change the conceptual length.

Detail We can optimize programs to reuse buffers and arrays—this makes programs faster.

public class Program {

    static void scan(int[] buffer) {
        for (int i = 0; i < buffer.length; i++) {
            // Terminate loop when sentinel element is detected.
            if (buffer[i] == -1) {
                break;
            }
            System.out.println(buffer[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {

        // The sentinel element is the sixth one.
        int[] buffer = { 10, 20, 30, 25, 35, -1, 50, 55 };
        scan(buffer);
        // Make the third element the sentinel.
        buffer[2] = -1;
        scan(buffer);
    }
}10
20
30
25
35

10
20

`Arrays.toString`

This method is helpful when displaying arrays. This is a static method. It uses square brackets and commas to display an array.

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

        int[] values = { 505, 100, 605 };
        // Call Arrays.toString to display the elements.
        System.out.println(Arrays.toString(values));
    }
}
[505, 100, 605]

Merge arrays

This program merges 2 arrays. The second array is placed at the end of the first array—a third array is created to store them together.

Part 1 We allocate 2 arrays. Each has 3 elements, but they can contain any number of elements.

Part 2 This code allocates a third array—it is large enough to hold all elements. We use for-loops to copy into this array.

Part 3 The second loop uses an offset value, equal to values.length to assign into the merged array.

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

        // Part 1: arrays to be merged.
        int[] values = { 10, 20, 30 };
        int[] values2 = { 100, 200, 300 };

        // Part 2: merge the 2 arrays with for-loops.
        int[] merge = new int[values.length + values2.length];
        for (int i = 0; i < values.length; i++) {
            merge[i] = values[i];
        }
        // Part 3: loop with offset.
        for (int i = 0; i < values2.length; i++) {
            merge[i + values.length] = values2[i];
        }

        // Display the merged array.
        System.out.println(Arrays.toString(merge));
    }
}
[10, 20, 30, 100, 200, 300]

Benchmark, `ArrayList`

Arrays are harder to use than ArrayLists. But they yield a speed advantage, even on simple element accesses. We test whether an array is faster than an ArrayList.

Version 1 Here we sum a 100-element array of integers. We use a for-loop to iterate over each element.

Version 2 In this version of the code we sum the elements in an ArrayList. We try to measure the overhead here.

Result We find accessing all elements in a loop is faster with an array. The lower-level code has a benefit in speed.

public class Program {
    public static void main(String[] args) {

        // ... Create array.
        int[] array = new int[100];
        array[0] = 1;

        // ... Create ArrayList.
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        for (int i = 1; i < 100; i++) {
            list.add(0);
        }

        long t1 = System.currentTimeMillis();

        // Version 1: sum all elements in an array.
        for (int i = 0; i < 1000000; i++) {

            int sum = 0;
            for (int v = 0; v < array.length; v++) {
                sum += array[v];
            }
            if (sum != 1) {
                System.out.println(false);
            }
        }

        long t2 = System.currentTimeMillis();

        // Version 2: sum all elements in an ArrayList.
        for (int i = 0; i < 1000000; i++) {

            int sum = 0;
            for (int v = 0; v < list.size(); v++) {
                sum += list.get(v);
            }
            if (sum != 1) {
                System.out.println(false);
            }
        }

        long t3 = System.currentTimeMillis();

        // ... Times.
        System.out.println(t2 - t1);
        System.out.println(t3 - t2);
    }
}38 ms, int[],     array[i]
91 ms, ArrayList, list.get(i)

Benchmark, locality

Elements nearer together in memory are faster to access. We can exploit this principle to optimize programs. Here we use locality of reference in an array.

Version 1 This loop reads the values of 100 elements in an array. The elements are packed together.

Version 2 This loop instead loads 100 elements, but they are spaced 100 elements apart each.

Result The loop that accesses the elements that are packed tight together is faster.

public class Program {
    public static void main(String[] args) {

        // Create an array and fill it with values.
        int[] values = new int[1000000];
        for (int i = 0; i < values.length; i++) {
            values[i] = i;
        }

        long t1 = System.currentTimeMillis();

        // Version 1: sum 100 elements that are packed together.
        for (int i = 0; i < 1000000; i++) {
            int sum = 0;
            for (int x = 0; x < 100; x++) {
                sum += values[x];
            }
            if (sum == 0) {
                System.out.println(false);
            }
        }

        long t2 = System.currentTimeMillis();

        // Version 2: sum 100 elements spaced apart by 100 slots each.
        for (int i = 0; i < 1000000; i++) {
            int sum = 0;
            for (int x = 0; x < 10000; x += 100) {
                sum += values[x];
            }
            if (sum == 0) {
                System.out.println(false);
            }
        }

        long t3 = System.currentTimeMillis();

        // ... Times.
        System.out.println(t2 - t1);
        System.out.println(t3 - t2);
    }
}35 ms,  access 100 packed elements (more locality)
61 ms,  access 100 sparse elements

Arrays are a lower-level construct, of a static memory size. We must create a new array to resize. An advantage of arrays is blazing speed.