Chapter 3: Arrays

3.1The idea of an array

Picture a program that stores the exam scores of 40 students. Forty separate variables (score1, score2, …, score40) are tedious and nearly useless: averaging them means writing out forty names, and a 41st student means changing the program. We want all forty scores under one name, each reachable by its position. That is what an array provides.

3.1.1What is an array?

An array stores many values of the same type, in order, under one name. Each value is an element, and its position number is its index. In Java, C, and many other languages indices start at 0: the first element has index 0, the second index 1.

Each part of the definition matters:

• Same type. An int array holds only integers, a String array only strings. So every element takes the same number of bytes, which makes an element’s location easy to compute.
• Fixed size. The size is set at creation and never changes. A five-element array cannot grow a sixth cell; for more room we create a bigger array and copy the elements into it.
• Contiguous memory. Elements are packed back to back with no gaps: element 1 directly follows element 0, element 2 follows element 1.

Fixed size does not mean fixed contents: the 4 in cell 2 can become 40 at any time. What is fixed is the number of cells, so insertion and deletion mean something special for arrays. Inserting in the middle shifts the elements to its right one cell over to make room; deleting shifts them left to close the gap. Sections 3.5.5 and 3.5.6 work out what these shifts cost.

Figure 3.1 shows the most useful picture of an array: a row of numbered boxes, values inside, indices above. Don’t confuse the two. Here the element at index 2 is 4, while the element whose value is 2 sits at index 3.

Arrays appear wherever many values of one type are processed together:

• Matrices. Tables of numbers in rows and columns live in two-dimensional arrays (3.4).
• Images. A digital image is a grid of pixels, each with a color value, stored in a two-dimensional array.
• Sound. A recording is a sequence of amplitude samples, taken thousands of times a second and stored in time order in a one-dimensional array.

3.1.2Indexing and address arithmetic

To reach an element, write the array’s name and the index in square brackets: arrayName[index]. This code creates a five-element array and reads its first and last elements:

int[] arr = {7, 2, 9, 5, 1};
int first = arr[0];      // 7
int last = arr[arr.length - 1];      // 1

arr[0] is 7. The last index is one less than the length, which every Java array carries in its length field; here arr.length is 5, so the last element is arr[arr.length - 1], that is, arr[4] = 1. Going through length instead of writing 4 keeps the code correct if the size ever changes.

Indices start at 0 because of how elements are found in memory. Memory is a sequence of bytes, each with a numbered address. Creating an array reserves a contiguous region big enough for all its elements; the address of its first byte is the array’s base address. An int takes 4 bytes, so element 0 is at the base address, element 1 four bytes later, element 2 eight bytes later. In general, element i is at

address(i) = base + i × element size

Starting at 0, the first element’s address is the base itself and the formula needs no “−1.” An index is really the element’s distance from the start, counted in elements.

This is the array’s greatest strength. The time to reach an element depends neither on the array’s size nor on the element’s position: arr[i] takes as long in an array of five elements as in one of five million. This is random access — “random” meaning any element you like, directly — and it costs O(1) (3.5.2).

3.1.3Kinds of arrays

Arrays are named by how many directions their elements extend in; Figure 3.2 shows three kinds.

• One-dimensional array. A single row of elements, each reached with one index, like every example so far: int[] a = new int[5];
• Two-dimensional array. Rows and columns, like a table, also called a matrix. Each element takes two indices, row first, then column: int[][] m = new int[3][3];
• Multidimensional array. Anything needing more than two indices, such as video frames indexed by time × row × column: int[][][] k = new int[3][3][3];

Each dimension adds a pair of brackets to the declaration, and the element count is the product of the dimensions: new int[3][3] holds 9, new int[3][3][3] holds 27. How Java actually stores multidimensional arrays may surprise you; see Section 3.4.2.

3.1.4Strengths and weaknesses

Choosing a structure means knowing where it is strong and where it is weak. Table 3.1 does this for arrays.

Most strengths come from contiguous memory. Access is fast because of the address arithmetic of Section 3.1.2. “No extra references” is clearest next to a linked list, where every element carries a reference to the next one, costing memory. In an array the next element is simply next door, so all the memory goes to data.

Contiguity also makes arrays cache-friendly. The processor fetches memory in blocks and keeps them in a small, very fast cache beside it. Reading element 0 brings elements 1, 2, and 3 from the same block along, so a pass through the array finds most elements already waiting. Of two algorithms taking the same number of steps, the one working on an array is therefore usually faster in practice.

Most weaknesses share that source. With no gaps between elements, inserting in the middle requires making room. A full array cannot gain a cell at the end, because the memory right after it may belong to other data. And if the element count is unknown in advance, we must allocate generously and waste the unused cells.

The last row of the table, covariance, needs a closer look.

3.1.5Array covariance and ArrayStoreException

Java classes are related by subtyping: String is a subtype of Object, so every String is an Object and Object o = "Ann"; is legal. Is an array of Strings then a subtype of an array of Objects? Java says yes.

Covariance buys flexibility: one method static void print(Object[] a) accepts a String[], an Integer[], or any other array of references. But it has a price:

String[] names = {"Ann", "Alice"};
Object[] objects = names; // compiles
objects[0] = 42;   // compiles, but
                    // throws at run time!

Line 1 creates a two-element String array. Line 2 gives objects a reference to the same array — legal thanks to covariance — so two variables now point to one array on the heap. On line 3 the compiler sees an Object[] receiving 42 (boxed as an Integer, an Object) and has no complaint. But the object really is a String[] and cannot hold an integer. The Java Virtual Machine (JVM) notices at the moment of the assignment and throws ArrayStoreException: java.lang.Integer.

An error caught at compile time shows up on the programmer’s desk; one caught at run time may surface months later in front of a user. Array covariance moves a type error from the first to the second — that is the hole in type safety.

Java’s later generics were designed to close it. Generic lists are not covariant: List<String> is not a subtype of List<Object>, so List<Object> l = new ArrayList<String>(); does not compile, and the same mistake is caught by the compiler.

3.2Arrays in Java

Every language has arrays, but each declares them and lays them out in its own way. In Java an array is an object, and that one fact decides where it lives, what an assignment copies, and what a method receives when passed an array. This section goes from syntax down to memory layout.

3.2.1Declaring arrays and default values

A Java array is declared and created with this pattern:

DataType[] arrayName = new DataType[arraySize];

• DataType is the element type, such as int, double, or String; the [] says the variable refers to an array, not a single value.
• arrayName names the reference variable that points to the array, for example nums.
• arraySize is the number of elements. It need not be a constant; 5, n, or 2 * n, computed at run time, all work.

The left side declares a reference variable — a value that records where an object is in memory, not the object itself. The right side, new DataType[arraySize], creates a new array object, and the assignment stores its reference in the variable. This distinction underlies the discussion of copying in Section 3.2.6.

int[] nums = new int[5];
// → [0, 0, 0, 0, 0]

No values have been assigned here, but the five elements are not empty: every element of an array created with new gets its type’s default value, 0 for int. Table 3.2 lists the defaults.

Here arrays differ from local variables: reading an unassigned local int x; is a compile error, but array elements always have a value, because the JVM zeroes every cell at creation. That zeroing is work too, so creating an array of n elements takes O(n) time.

The char default, '\u0000', is an invisible character, not a space. A String array defaults not to empty strings ("") but to null, the reference that points to no object; calling a method through such an element (names[0].length()) throws a NullPointerException.

3.2.2Access, initialization, and length

When the values are known in advance, list them in braces instead of filling cells one by one; this is an initializer list. The code below shows initialization, reading, writing, and length:

int[] nums = {10, 20, 30, 40, 50};   // 5 initializers → size 5
int first    = nums[0];            // 10
int second = nums[1];            // 20
nums[4] = 55;                         // last element updated
int size   = nums.length;     // 5

nums = new int[] {1, 2, 3};          // later assignment needs new int[]
int[] bad = new int[3] {1, 2, 3};   // compile error: size + list

• Line 1: The five values set the size; no size is written. Java creates the array, stores the values in order, and assigns the reference to nums.
• Lines 2 and 3: Reading: nums[0] is 10, nums[1] is 20.
• Line 4: Writing uses the same syntax on the left of an assignment; the last cell (index 4) changes from 50 to 55.
• Line 5: nums.length is 5. length is a field, not a method, so no parentheses follow it.
• Line 7: A bare initializer list is allowed only in a declaration; elsewhere it needs new int[] in front.
• Line 8: A compile error: the list already fixes the size, so you cannot also give one. Write new int[] {1, 2, 3}.

3.2.3Code trace: reading and writing elements

Here is what that code does in memory. The traced lines:

int[] nums = {10, 20, 30, 40, 50};
int first    = nums[0];
int second = nums[1];
nums[4] = 55;
int size   = nums.length;
nums = new int[] {1, 2, 3};

Line 1 creates two things: a five-element int[] object on the heap, and the variable nums, which holds only the object’s reference — the arrow in Figure 3.4, left.

Line 2 reads with the address arithmetic of Section 3.1.2, base + 0 × 4, in one step whatever the size; line 3 does the same for index 1. On line 4 the same syntax stands left of an assignment, so it writes: the last cell becomes 55. Line 5 reads the length, fixed when the array was created.

The last line teaches the most. new int[] {1, 2, 3} creates a new array, and nums now points to it. The old array still holds [10, 20, 30, 40, 55], but no reference leads to it, so the program can never reach it again. Java’s garbage collector (GC) finds such unreachable objects and reclaims their memory.

Note too that size is still 5. Line 5 copied the value of nums.length at that moment; size is not tied to the array and does not follow its changes.

3.2.4Sample code: declare, fill, print

This complete program creates an array, fills it in a loop, and prints it two ways:

public class ArrayExample {
    public static void main(String[] args) {
        int[] nums = new int[5];            // 5-element array
        for (int i = 0; i < nums.length; i++)
            nums[i] = (i + 1) * 10;              // 10, 20, 30, 40, 50

        System.out.println("First element: " + nums[0]);
        System.out.println("Third element: " + nums[2]);

        System.out.print("Elements: ");
        for (int x : nums)                       // for-each: when no index is needed
            System.out.print(x + " ");
    }
}

The output:

First element: 10
Third element: 30
Elements: 10 20 30 40 50

This is the skeleton of most array code:

• Create. new int[5] gives five zeros.
• Fill. The loop runs i from 0 while i < nums.length, writing (i + 1) * 10 into nums[i]: 10, 20, 30, 40, 50.
• Print single elements. nums[0] and nums[2]; the third element has index 2.
• Print all elements. The for-each loop for (int x : nums) reads “for each x in nums”; x takes each element’s value in turn.

The loop’s real gain over five assignments is independence from the size: it works unchanged for 500 elements, as long as the bound is nums.length. A bound of i < 5 works today but, once the size changes, either fills half the array or runs off its end.

System.out.println ends its output with a line break; System.out.print does not, so the last loop prints all elements on one line, separated by spaces.

For-each reads better when no index is needed, but has two limits. It does not know the index, so “where did we find it?” needs a separate counter. And x is a copy of the value, so x = 0 leaves the array unchanged. To write into an array, use an indexed for.

3.2.5Code trace: fill and print

Table 3.4 traces the fill loop and the print statements.

The final test is easy to overlook: at i = 5, 5 < 5 is false, so nums[5] is never touched. With <=, the last iteration would write to a nonexistent cell 5 and the program would stop with an exception.

The body ran 5 times, one multiplication and one assignment each; with n elements, n times. Any loop that visits every element once costs O(n) (3.5).

3.2.6Copying arrays: reference or copy?

A Java array is an object: it lives on the heap, and a variable holds its reference, not the object. The most surprising consequence is that = does not copy an array:

int[] arr = {1, 2, 3, 4, 5};
int[] ref = arr;   // same object
int[] copy =
    Arrays.copyOf(arr, arr.length);
ref[0] = 99;

We trace it in four steps, numbering the heap arrays #1 and #2.

Three common ways give a real copy, each creating a new array and copying element by element in O(n):

• Arrays.copyOf(arr, newSize) returns an array of the requested size, padding with default values or truncating. This is also how a full array is grown.
• arr.clone() returns a same-size copy.
• System.arraycopy(src, srcPos, dest, destPos, length) copies a given number of elements into an existing array, starting at given positions.

The same rule holds for method calls: a method receives the array’s reference, so a change it makes inside the array is visible to the caller. That is why median in Section 3.3.4 copies the array before sorting.

3.2.7Ready-made operations: java.util.Arrays

Java arrays have no sorting, searching, or printing methods of their own. Those come as static methods of the Arrays class in java.util, called through the class name — Arrays.sort(a), not a.sort() — after import java.util.Arrays;. Table 3.5 lists the common ones.

Most are O(n), touching each element once. sort costs more, O(n log n) for a good algorithm (3.5.7). binarySearch costs less but needs a sorted array. Binary search compares the target with the middle element and continues in the left half if the target is smaller, the right half if larger. The range halves each step, so about log₂ n steps suffice: 20 for a million elements.

The two most common array mistakes show why the class is needed:

int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
a == b              // false: different objects
Arrays.equals(a, b) // true: same contents
println(a)          // [I@1b6d3586

a and b are separate arrays with equal contents. == compares references — do both variables point to the same object? — so it gives false. Arrays.equals(a, b) compares the lengths, then the elements one by one, and gives true.

The second mistake is printing an array directly. System.out.println(a) prints something like [I@1b6d3586: [I means “array of int,” and the part after @ is an object-specific number that may change between runs. System.out.println(Arrays.toString(a)) prints [1, 2, 3].

3.2.8Variable-length argument lists

A method that averages numbers might be called with two, three, or ten of them. For such cases Java offers varargs: three dots after the parameter type.

static double average(double... arr) {
    if (arr.length == 0)
        return Double.NaN;  // undefined
    var sum = 0.0;
    for (var value : arr)
        sum += value;
    return sum / arr.length;
}

double... arr accepts any number of double arguments; the compiler packs them into a double[] and passes that. Inside, arr is an ordinary array with a length, traversable by index or for-each. The rules:

• The varargs parameter must come last.
• A method can have only one.
• An existing array can be passed directly: average(new double[] {1, 2}).

An empty call, average(), is checked separately and returns Double.NaN (“Not a Number”), a special double marking an undefined result — the average of no numbers is undefined. And var declares a local whose type comes from the value on the right: 0.0 is a double, so sum is too. Table 3.6 shows several calls.

The idea is familiar: every program’s main(String[] args) receives its command-line arguments as an array, and String.format and System.out.printf take variable-length argument lists.

3.2.9Code trace: average(4, 8, 15)

In average(4, 8, 15) the integer arguments are widened to double, giving the array [4.0, 8.0, 15.0].

Each element is added once: n additions, O(n) time, and no memory beyond sum, value, and the argument array. For average(), length is 0 and line 3 returns Double.NaN. Without the check the result would still be NaN, since the floating-point division 0.0 / 0 yields it; the explicit check shows the case is handled on purpose.

3.2.10Arrays in memory: the stack and the heap

We keep saying “the variable on the stack” and “the array on the heap.” A running Java program divides memory into these two regions, which do different jobs and are managed differently.

• The stack holds method calls and local variables. Each call gets a stack frame with its parameters and locals, removed automatically when the method returns.
• The heap holds every object created with new. Every Java array lives there; only its reference is on the stack.

The garbage collector of Section 3.2.3 manages the heap, periodically freeing objects no reference points to. Nobody deletes objects by hand; Java has no command for it.

The different lifetimes matter: an array created in a method outlives the method. The frame and the local holding the reference disappear, but the array stays on the heap, and if the method returned the reference, the caller keeps using it. readArray in Section 3.3.1 works exactly this way.

An array lives while at least one reference to it exists. When the last one goes — the variable gets another array, is set to null, or its method returns — the array is unreachable and may be collected.

3.2.11“Static” and “dynamic” arrays: C and Java

Books often contrast static arrays with dynamic arrays. The terms fit C and C++ best, where an array can live in two places. Table 3.9 compares the languages.

In C, int a[10]; puts the array in the function’s stack frame; its size is known at compile time and it vanishes with the frame. Such arrays are “static.” An array whose size is known only at run time is allocated on the heap with malloc (C) or new (C++) and called “dynamic.” In C the programmer must free it when done: forgetting leaks memory, and freeing twice is undefined behavior, usually a crash.

Java has no such split. Every array is on the heap, its size computed at run time if need be but fixed afterward:

int[] dynArr = new int[n];   // room for n elements on the heap
dynArr = null;               // GC may collect it if no other reference exists

Line 1 creates an array of as many elements as n currently holds. Line 2 does not delete it; it drops the reference in dynArr, and if nothing else points to the array, the GC collects it when convenient. Even System.gc() only asks the JVM; it guarantees nothing.

“Dynamic array” also means an array that grows by itself when full, like Java’s ArrayList: it keeps an ordinary array inside and, when it fills, copies the elements into a larger one. Such a structure is built on a fixed-size array whose own size still never changes.

3.2.12Index out of bounds

Valid indices run from 0 to n − 1. An index outside that range — negative, or at least length — makes Java throw an ArrayIndexOutOfBoundsException, a subclass of IndexOutOfBoundsException.

int[] arr = new int[5];
arr[5] = 1;  // Index 5 out of
              // bounds for length 5
arr[-1] = 1; // same error

There is no cell 5. arr[5] = 1 compiles, since the compiler usually cannot know an index’s value, but the JVM checks every index at run time and throws, with a plain message: Index 5 out of bounds for length 5. arr[-1] fails the same way. Uncaught, the exception ends the program there.

This check is a major safety feature that sets Java apart from C. C computes the address of a[5] anyway and reads or overwrites whatever follows the array, silently corrupting any variable stored there; the bug may surface only when the program misbehaves somewhere else. Such overflows have caused many security holes. Java reports the error on the line that made it, at the price of one small comparison per access.

An index that comes from the user or a calculation can be checked first:

if (index >= 0
        && index < arr.length) {
    int value = arr[index];
} else {
    System.out.println("Invalid");
}

The access is safe when both conditions hold: the index is at least 0 and less than length.

3.3Array algorithms

These algorithms are small but instructive, and each uses the array differently: one pass, sort first, or work inward from both ends. The surest way to understand one is to trace every step on paper with a small input, as the trace tables below do.

3.3.1Reading an array from the user

The mean, median, and mode programs all begin by asking how many numbers will be entered and then reading them. That shared work belongs in a helper method:

import java.util.Scanner;

static double[] readArray(Scanner scanner) {
    System.out.print("Enter the array size: ");
    int size = scanner.nextInt();
    double[] arr = new double[size];  // size known only at run time
    for (int i = 0; i < size; i++) {
        System.out.print("Enter element " + (i + 1) + ": "); // count from 1
        arr[i] = scanner.nextDouble();
    }
    return arr;
}

The Scanner is created outside and passed in so the whole program uses one; several scanners on the same input can mix up what they read.

1. The prompt asks for the size; print adds no line break, so the cursor waits beside it.
2. nextInt() reads the integer into size.
3. new double[size] creates the array, its size known only now, at run time — no problem in Java. Every cell starts at 0.0.
4. The loop reads the elements. The user sees i + 1: the array counts from 0, people from 1, and “Enter element 0” would confuse them.
5. The array’s reference is returned.

The last step is the memory model of Section 3.2.10 at work: the local arr vanishes when the method returns, but the array survives on the heap and is used through the reference the caller stores.

Table 3.10 summarizes the three statistics of this section: same array, different costs.

3.3.2Code trace: readArray(sc)

Suppose the user enters 4 as the size, then 4, 8, 15, and 16 (Table 3.11).

The array does not exist until the user types the size (Figure 3.11), and nextDouble() reads the user’s 4 as 4.0, since the array holds doubles.

Reading n elements takes n reads, O(n). In practice most of the time goes to waiting for the user, but the algorithm’s work is proportional to the element count.

3.3.3Computing the mean

The mean is the sum of the values divided by their number. This main reads the array with readArray, computes the average, and prints it:

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    double[] arr = readArray(sc);
    double sum = 0;
    for (int i = 0; i < arr.length; i++)
        sum += arr[i];
    double average = sum / arr.length;
    System.out.println("Array: "
        + Arrays.toString(arr));
    System.out.println("Average: "
        + average);
    sc.close();
}

At its heart is an accumulator: sum starts at 0 and each iteration adds an element. The same pattern underlies finding a maximum, counting elements that meet a condition, or computing a product.

sum is a double initialized with the integer 0, which Java widens to 0.0; the division is done in double, so the result keeps its fraction. Arrays.toString(arr) formats the array — println(arr) would print something like [D@… (Section 3.2.7) — and sc.close() closes the Scanner.

n elements take n additions, O(n) time. Beyond the array the algorithm uses only sum, i, and average, however large n grows, so the extra memory is O(1).

Consider the edge case. A size of 0 creates a valid, empty array; the loop never runs and 0.0 / 0 is computed, a floating-point division that raises no error and yields NaN. “Average: NaN” is technically right but unhelpful; a warning such as “no numbers entered” would be better.

3.3.4The median

The mean is very sensitive to extreme values. If five people earn 3, 5, 7, 9, and 1000 units a month, the mean is (3 + 5 + 7 + 9 + 1000) / 5 = 204.8, a figure that describes none of them. The income of the person in the middle says more.

Sorted, the incomes are 3, 5, 7, 9, 1000, and the median is 7 — still 7 if 1000 became 10 or a million. Extreme values do not move the median.

static double median(double[] arr) {
    double[] s = arr.clone(); // copy
    Arrays.sort(s);             // O(n log n)
    int size = s.length;
    double median;
    if (size % 2 == 0) {       // even
        int m1 = size/2 - 1, m2 = size/2;
        median = (s[m1] + s[m2]) / 2;
    } else {                    // odd
        median = s[size / 2];
    }
    return median;
}

1. Copy. arr.clone() copies the array, because the next step sorts and sorting arr itself would scramble the caller’s array (3.2.6). Asking for a median should not rearrange your data.
2. Sort. Arrays.sort(s) sorts the copy ascending, in O(n log n).
3. Odd or even? size % 2 is the remainder on division by 2; 0 means even.
4. The middle value. For an even size, average the values at m1 = size/2 − 1 and m2 = size/2; for an odd size, return s[size / 2], where integer division gives exactly the middle index.

3.3.5Code trace: median()

We call the method on an even-sized and an odd-sized array: {6, 2, 8, 4}, then {9, 3, 11, 7, 5}.

The last row shows the copy paying off: only s was sorted, and the callers’ arrays keep their order.

Sorting decides the cost: copying is O(n), sorting O(n log n), reading the middle O(1), so the total is the largest term, O(n log n). The copy needs O(n) extra memory. Advanced algorithms find the median without sorting in O(n) average time, but sorting is the easiest route to understand.

3.3.6The mode

Counting each value’s occurrences by rescanning the whole array costs n × n comparisons. Sorting first is better: equal values end up side by side, so one left-to-right pass counts every run.

static int mode(int[] arr) { // not empty
    int[] s = arr.clone();
    Arrays.sort(s);  // equal values side by side
    int best = s[0], bestCount = 1;
    int count = 1;
    for (int i = 1; i < s.length; i++) {
        if (s[i] == s[i - 1]) count++;
        else count = 1;   // new value
        if (count > bestCount) {
            bestCount = count;
            best = s[i];
        }
    }
    return best;
}

• s: a sorted copy, made for the same reason as in median.
• count: how many times in a row the current value has appeared so far.
• best, bestCount: the record — value and length of the longest run so far.

Initially s[0] has been seen once and holds the record. From index 1, each element is compared with its left neighbor: equal means the run continues and count grows; different means a new value, and count resets to 1. After each comparison, a count that beats the record replaces it.

Using > is deliberate. A value that repeats as often as the record only ties it and cannot beat it, so the record stays with the value seen first — in an ascending array, the smallest of the tied values. With >=, ties would go to the largest.

The comment “not empty” is a precondition: an empty array has no s[0], and the method would throw an ArrayIndexOutOfBoundsException. The caller must not pass one.

3.3.7Code trace: mode()

In mode({4, 1, 4, 2, 1, 4}) the equal values are scattered; the sorted copy is s = {1, 1, 2, 4, 4, 4}. Initially best = 1, bestCount = 1, count = 1.

The method returns 4, which occurs three times. Row i = 4 shows the tie rule: 4 has appeared twice, matching the record, so 2 > 2 fails and 1 keeps it. Had the array ended there, the method would return 1, seen first; here 4 appears once more and takes the record at i = 5.

Sorting costs O(n log n) and the scan O(n), so the total is O(n log n), with O(n) extra memory for the copy.

3.3.8Reversing an array in place

Reversing an array moves the first element to the end, the last to the front, the second to the second-to-last place, and so on: {3, 8, 1, 9, 4, 6} becomes {6, 4, 9, 1, 8, 3}. Copying back to front into a new array, result[i] = arr[n - 1 - i], works but needs a second array of n elements. The job can be done within the array itself.

An algorithm that works on the array itself, without an extra array, is in-place. Here: exchange the first and last elements, then the second and second-to-last, and so on to the middle. Exchanging two elements is a swap.

static void reverse(int[] arr) {
    int start = 0;
    int end = arr.length - 1;
    while (start < end) {
        // swap the two outermost elements
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;   // move inward
        end--;
    }
}

The indices start and end begin at the two ends; since they “point at” positions, they are also called pointers. Each iteration swaps the elements they point to and moves both one step inward. When they meet, start < end fails and the loop ends.

A swap needs three assignments and a temporary. The first saves the left value in temp; the second copies the right value over it, so the old left value now exists only in temp; the third writes it to the right. Without temp, arr[start] = arr[end]; arr[end] = arr[start]; would leave both cells equal and lose the left value.

Six elements took three swaps. With an odd count the middle stays put: in {1, 2, 3, 4, 5}, 1 swaps with 5, 2 with 4, and 3 is untouched, giving {5, 4, 3, 2, 1}.

Copying into a new array also takes O(n) time; the difference is memory, O(n) extra versus O(1). With tight memory or a huge array, reverse in place; if the original is still needed elsewhere, copying has the advantage of leaving it intact.

3.3.9Application: the Caesar cipher

The Caesar cipher, named after Julius Caesar, replaces every letter with the one a fixed k places further along the alphabet, wrapping around at the end. With k = 3, A → D, B → E, C → F, and X → A, Y → B, Z → C. With only 25 keys, all easy to try, it offers no security, but it is a fine exercise in character arrays and the remainder operator.

static String encrypt(String message, int k) {
    char[] chars = message.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        int pos = chars[i] - 'A';        // 0..25 (A–Z only)
        chars[i] = (char) ('A' + (pos + k) % 26);
    }
    return new String(chars);
}

• toCharArray(). Java Strings are immutable, so the letters are copied into a char[], whose elements can be changed in place.
• chars[i] - 'A'. A char is an integer code, and the capital letters have consecutive codes, so subtracting 'A' gives a letter’s alphabet position: 0 for 'A', 4 for 'E', 25 for 'Z'.
• (pos + k) % 26. The position advances by k; past 25, the remainder wraps it around: (25 + 3) % 26 = 2.
• (char) ('A' + …). Adding the position to 'A' and casting gives the letter back.
• new String(chars). The modified array becomes a string again.

Tracing encrypt("ZEKA", 3):

The method returns "CHND". The first row shows the wraparound: Z is at 25, three steps on is 28, and 28 % 26 = 2 is C.

Decryption needs no new method: 3 steps forward plus 23 more make 26, a full trip around the alphabet, so calling the same method with k = 26 − 3 = 23 decrypts: encrypt("CHND", 23) gives "ZEKA".

Each letter is processed once, so n letters take O(n); toCharArray and new String add one O(n) copy each, which does not change the total.

3.4Multidimensional arrays

Some data naturally forms a table: a weekly timetable, a chessboard, the pixels of an image, a table of distances between neighborhoods. It can be squeezed into a one-dimensional array, but then every access must turn a row and a column into one index. A two-dimensional array leaves that to the language.

3.4.1Two-dimensional arrays

A two-dimensional array arranges elements in rows and columns, like a table; it is programming’s version of the mathematical matrix. An element takes two indices, matrix[row][col], row first, both starting at 0.

int[][] matrix = new int[3][3];
matrix[1][2] = 7;   // 2nd row, 3rd column

Line 1 creates a 3 × 3 matrix of zeros; line 2 writes 7 into column 2 of row 1 — counting the human way, the third column of the second row.

Two-dimensional arrays suit chessboards (8 × 8), images, and spreadsheets. In an image, image[y][x] is the color of the pixel in row y from the top and column x from the left.

3.4.2Matrices in Java: arrays of arrays

Some languages store a two-dimensional array as one block, row after row. Java has no true two-dimensional type: a matrix is an array of arrays, and int[][] is an array whose elements are int[].

int[][] matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
matrix.length      // 3 (number of rows)
matrix[0].length   // 3 (number of columns)

This creates four arrays: an outer array of three references, and three int arrays, one per row. Each outer cell points to a row, and matrix points to the outer array.

• matrix.length is the outer array’s length, the number of rows (3).
• matrix[0] is a row, and matrix[0].length its length, the number of columns (3).
• matrix[1][2] takes two steps: matrix[1] reaches row 1, then element 2 of that row is read: 6.
• The initializer states no sizes; the inner lists determine them.

Most important, each row is a separate array, so rows may differ in length. Such an array is a jagged array.

3.4.3A jagged array: Pascal’s triangle

Pascal’s triangle is a natural example. Each row is one longer than the last, both ends are 1, and each inner number is the sum of the two above it:

p[i][j] = p[i−1][j−1] + p[i−1][j]

The first four rows are 1; 1 1; 1 2 1; 1 3 3 1. A square matrix would give every row the room of the longest and leave nearly half its cells empty; a jagged array gives each row just what it needs. This code builds 4 rows:

int n = 4;
int[][] p = new int[n][];          // no rows yet
for (int i = 0; i < n; i++) {
    p[i] = new int[i + 1];         // length i + 1
    p[i][0] = p[i][i] = 1;
    for (int j = 1; j < i; j++)
        p[i][j] = p[i-1][j-1] + p[i-1][j];
}

new int[n][] creates only the outer array; the empty second brackets mean no rows yet, so all four cells are null. Each iteration creates row i with length i + 1 and sets both ends to 1. p[i][0] = p[i][i] = 1 is a chained assignment, evaluated right to left: p[i][i] = 1 first, then its value, 1, goes into p[i][0]. The inner loop computes the cells between the ends from the row above.

In row 0, p[0][0] is both first and last cell, so it gets 1 twice. Rows 0 and 1 have no inner cells, so the inner loop never runs. Row 3 comes from row 2: p[3][1] = p[2][0] + p[2][1] = 1 + 2 = 3 and p[3][2] = p[2][1] + p[2][2] = 2 + 1 = 3.

The triangle uses 1 + 2 + 3 + 4 = 10 cells, a 4 × 4 matrix 16. For n rows it is n(n + 1)/2 against n², saving nearly half the memory.

3.4.4Shallow and deep copies of a 2D array

Being an array of arrays, a matrix copies in a surprising way. Section 3.2.6 said clone() makes an independent copy, true for an array of nums. But the outer array’s elements are references, and clone() copies the references, not the rows.

The two kinds side by side:

int[][] m = { {1, 2}, {3, 4} };
int[][] s = m.clone();          // shallow copy
s[0][0] = 9;                    // m[0][0] is 9 too!
s[1] = new int[] {7, 8};        // only s changes
int[][] d = new int[2][];       // deep copy:
for (int i = 0; i < 2; i++)
    d[i] = m[i].clone();        // rows too
d[0][1] = 5;                    // m unaffected

Steps 3 and 4 are the key. s[0][0] = … changes the inside of a shared row, visible through m; s[1] = … changes a reference in s’s separate outer array, leaving m alone. In a shallow copy, the outer arrays are separate and the rows shared.

A deep copy copies every cell: O(r · c) time and extra memory for r rows and c columns. A shallow copy takes O(r); cheap, but safe only if the rows never change.

3.4.5Filling and printing a matrix

The standard way to visit every cell is two nested loops, rows outside, columns inside. This program fills a 3 × 3 matrix with 1 to 9 and prints it as a table:

public class MultiArrayExample {
  public static void main(String[] a) {
    int[][] matrix = new int[3][3];
    // initial values: 1…9
    for (int i = 0; i < 3; i++)      // row
      for (int j = 0; j < 3; j++)    // column
        matrix[i][j] = i * 3 + j + 1;

    System.out.println("Matrix contents:");
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++)
        System.out.print(matrix[i][j] + " ");
      System.out.println();   // new line
    }
  }
}

Output:

Matrix contents:
1 2 3
4 5 6
7 8 9

i * 3 + j + 1 numbers the cells row by row: row i is preceded by i full rows, i × 3 cells, then j more within the row, plus 1 because numbering starts at 1. Table 3.17 lists the nine assignments.

j runs through 0, 1, 2 while i holds still; then i advances and j starts over. Every outer iteration contains all the inner ones, so the body runs 3 × 3 = 9 times — r · c times for an r × c matrix, a cost of O(r · c).

Printing follows the same pattern: the inner loop prints a row on one line with print, and the println() after it ends the line. Inside the inner loop it would put each number on its own line; without it, all nine would share one.

The bounds here are the constant 3. With i < matrix.length and j < matrix[i].length the code works for any matrix, even a jagged one, since matrix[i].length, unlike matrix[0].length, uses each row’s own length.

3.4.6Three-dimensional arrays

Java allows three or more dimensions too. A three-dimensional array is an array of matrices — say, a table changing over time (time × row × column), or the red, green, and blue layers of a color image.

int[][][] array3D =
        new int[3][3][3];
for (int x = 0; x < 3; x++)
  for (int y = 0; y < 3; y++)
    for (int z = 0; z < 3; z++)
      array3D[x][y][z] =
          x * 9 + y * 3 + z + 1;

// printing: the same three loops;
// println after the z loop (y),
// println after the y loop (x)

Each dimension adds a nested loop; here the innermost assignment runs 27 times. x * 9 + y * 3 + z + 1 extends the matrix formula by one dimension — 9 cells per layer, 3 per row — so array3D[1][2][0] = 1 · 9 + 2 · 3 + 0 + 1 = 16.

Printing uses the same three loops: when the z loop ends a row is complete and println starts a new line; when the y loop ends a layer is complete and one more blank line follows.

Element counts grow fast with dimensions: a three-dimensional int array of 100 per dimension holds a million elements, about 4 MB; four dimensions make it 400 MB. Work out the memory before creating one.

Java allows non-ASCII letters in identifiers, such as the Turkish üçBoyutluDizi (“three-dimensional array”), but files may be opened with other encodings and some tools mangle such characters, so ASCII names like array3D are safer.

3.4.7Transposing a matrix

Rows become columns and columns rows: a 2 × 3 matrix becomes 3 × 2, and row 0 becomes column 0.

static int[][] transpose(int[][] m) {
    int rows = m.length;
    int cols = m[0].length;
    int[][] t = new int[cols][rows];
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            t[j][i] = m[i][j];
    return t;
}
static void printMatrix(int[][] m) {
    for (int[] row : m) {
        for (int x : row)
            System.out.print(x + " ");
        System.out.println();
    }
}

transpose takes the row count from m.length and the column count from the first row, m[0].length, creates new int[cols][rows] with the dimensions swapped, and visits each cell of m once, writing it to its mirror position: t[j][i] = m[i][j].

printMatrix uses two for-each loops, row over the rows and x over each row’s elements; without indices, it handles jagged arrays too.

Both methods are static because main, which calls them, is static, and a static method can call its class’s other static methods directly, with no object. Without static, the call would not compile.

Let’s trace transpose(m) for m = {{1, 2, 3}, {4, 5, 6}}: rows = 2, cols = 3, and t starts as a 3 × 2 matrix of zeros.

After three assignments, column 0 of t is 1, 2, 3, row 0 of m; the last three write row 1 into column 1. printMatrix(t) prints “1 4,” “2 5,” and “3 6.”

Each element is copied once: m · n assignments, O(m · n) time, and, for the new matrix, O(m · n) extra memory. A square matrix can be transposed in place by swapping each cell above the diagonal with its mirror below; a non-square one cannot, since its shape changes.

3.4.8Application: Tic Tac Toe

Board games are a classic use of two-dimensional arrays, and Tic Tac Toe is the simplest:

• The board is 3 × 3, stored as a char[][].
• Players X and O take turns marking an empty cell.
• Three of your marks in a row, column, or diagonal win.
• A full board with no winner is a draw.

Every move is one assignment, board[row][col] = player; the rest of the program is checks around it. The main loop:

public class TicTacToe {   // import java.util.Scanner;
    static Scanner scanner = new Scanner(System.in); // single Scanner

    public static void main(String[] args) {
        char[][] board = new char[3][3];   // 3x3 game board
        char player = 'X';                   // X moves first
        boolean gameOn = true;
        initBoard(board);                  // every cell ' '
        while (gameOn) {
            showBoard(board);
            makeMove(board, player);
            gameOn = isGameOn(board, player);
            player = (player == 'X') ? 'O' : 'X';   // switch turns
        }
        showBoard(board);
    }

main creates the board, lets X start, and repeats until the game ends: show the board, take a move, check for the end, pass the turn. The conditional operator (player == 'X') ? 'O' : 'X' gives O if the player is X, otherwise X.

A board made with new char[3][3] starts as '\u0000' (3.2.1), invisible and not a space, so initBoard fills it with ' ' before play. The scanner field is static because static methods use it; the whole program shares one Scanner.

static void initBoard(char[][] t) {
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
      t[i][j] = ' ';
}
static void showBoard(char[][] t) {
  System.out.println("-------------");
  for (int i = 0; i < 3; i++) {
    System.out.print("| ");
    for (int j = 0; j < 3; j++)
      System.out.print(t[i][j]+" | ");
    System.out.println("\n-------------");
  }
}

initBoard writes a space into all nine cells; showBoard prints the board framed by lines. In "\n-------------", \n is the newline character, so each row ends before its separator line.

static void makeMove(char[][] t,
                     char player) {
  int row, col;
  do {
    System.out.print("Player " + player
      + ": row and column (1-3): ");
    row = scanner.nextInt() - 1;
    col = scanner.nextInt() - 1;
  } while (row < 0 || row > 2
        || col < 0 || col > 2
        || t[row][col] != ' ');
  t[row][col] = player;
}
// the user enters 1-3, the array uses 0-2;
// invalid/occupied cell → ask again

makeMove asks until it gets a valid move, using a do-while loop, whose body runs once before the test — natural, since there is nothing to check before the first question. The user types 1–3 and the array uses 0–2, hence the −1. The loop repeats if the row or column is invalid or the cell is taken. The order matters: || evaluates left to right and stops at the first true condition, so with the index checks first, t[row][col] is never accessed with a bad index.

3.4.9Checking for a win or a draw

A 3 × 3 board has 8 winning lines: 3 rows, 3 columns, 2 diagonals. A loop checks rows and columns, and a single return the diagonals:

static boolean hasWon(char[][] t, char o) {
    for (int i = 0; i < 3; i++)
        if ((t[i][0] == o && t[i][1] == o && t[i][2] == o)     // row i
         || (t[0][i] == o && t[1][i] == o && t[2][i] == o))    // column i
            return true;
    return (t[0][0] == o && t[1][1] == o && t[2][2] == o)      // main diagonal
        || (t[0][2] == o && t[1][1] == o && t[2][0] == o);     // anti-diagonal
}
static boolean isGameOn(char[][] t, char o) {
    if (hasWon(t, o)) {
        System.out.println("Congratulations, player " + o + " wins!");
        return false;
    }
    for (char[] row : t)
        for (char c : row)
            if (c == ' ') return true;          // an empty cell → continue
    System.out.println("The game is a draw.");
    return false;
}

For each i, hasWon tests row i (t[i][0], t[i][1], t[i][2]) and column i (t[0][i], t[1][i], t[2][i]) — the indices simply trade places, as in the transpose. Failing that, it checks the main diagonal [0][0], [1][1], [2][2] and the anti-diagonal [0][2], [1][1], [2][0].

isGameOn first asks whether the player who just moved has won; if so, it congratulates them and returns false. Otherwise one empty cell is enough to continue, so it returns true at the first; with none, the game is a draw. Only the last mover needs checking, since a move can win only for the player who made it.

We trace the win check on a board where X has just moved and the rows are X O _ / _ X O / _ _ X (_ is empty).

The table shows short-circuit evaluation. Once one of three conditions joined by && fails, the whole is false and the rest are skipped: in row 0, t[0][1] is 'O', so t[0][2] is never read; in row 1, t[1][0] is already empty. In the last row the left side of ||, the main diagonal, is true, which settles the result, so the anti-diagonal is never examined and the method returns true.

On a fixed 3 × 3 board, hasWon checks at most 8 lines or 24 cells, constant work. On an n × n board needing n in a line, 2n + 2 lines of n cells would cost O(n²); checking only the last move’s row, column, and diagonals (if any) takes O(n).

3.5The complexity of array operations

Each algorithm so far ended with a cost: O(1), O(n), O(n log n). This section explains the notation briefly and justifies the cost of each basic array operation, so that “is this fast?” can be answered from what the operation does to the array, not from memory.

3.5.1What array operations cost

The complexity of an algorithm describes how its running time and memory grow with the input size n. Seconds vary between machines, so we count basic steps — comparisons, assignments, additions — and ask how fast that count grows with n.

The common growth rates:

• O(1), constant: the step count does not depend on n.
• O(log n), logarithmic: doubling n adds one step.
• O(n), linear: doubling n doubles the steps.
• O(n log n): slightly faster than linear; the cost of good sorting algorithms.
• O(n²), quadratic: doubling n quadruples the steps.

For a million elements, log₂ n is about 20, n a million, n² a trillion. At a billion steps a second, a linear algorithm takes a thousandth of a second and a quadratic one about 17 minutes.

Time can also depend on the input itself: a linear search ends at once if the target comes first but scans everything if it is absent. Costs are therefore given for the best case, average case, and worst case; unless stated otherwise, a cost means the worst case, a guarantee that no input is slower. Table 3.20 summarizes array operations.

3.5.2Access: O(1)

int[] arr = {10, 20, 30, 40, 50};
int value = arr[2];      // 30 — in one step, O(1)

Reading arr[2] involves no counting from the start: the formula of Section 3.1.2 adds index × element size to the base address — one multiplication, one addition, one memory read, whatever the array’s size. Access is O(1), and so is writing, arr[2] = 35.

Not every structure has this. A linked list scatters its elements in memory, each knowing only where the next one is, so reaching element k takes k steps from the start: O(n) access. When a problem indexes often, the array is the natural choice.

3.5.3Linear search: O(n)

Access reads an element at a known index; search asks the reverse: is a value present, and where? An unsorted array gives no hint, so the only way is to check the elements one by one from the start. This is linear search.

static boolean linearSearch(int[] arr,
                           int target) {
    for (int x : arr)
        if (x == target)
            return true; // found
    return false;
}

The method returns true the moment an element matches, ignoring the rest. Only if the loop runs through the whole array is the target absent, which is why return false sits outside the loop.

We search {7, 2, 9, 5, 1, 8} for 5, then for 3.

5 is found at index 3 after 4 comparisons; 1 and 8 are never examined. 3 is absent, and being sure of that takes all n = 6 comparisons.

• Best case: the target is first: 1 comparison, O(1).
• Worst case: the target is last or absent: n comparisons, O(n).
• Average case: a present target, equally likely anywhere, takes (n + 1)/2 comparisons on average — still O(n).

A sorted array allows binary search (Section 3.2.7), which halves the range each step and finishes in O(log n). But sorting costs O(n log n), more than one linear search, so it pays only when many searches will follow.

3.5.4Nested loops: common elements of two arrays

The most direct way to find the elements two arrays share is to compare every element of one with every element of the other:

static void printMatches(int[] arr1, int[] arr2) {
    for (int x : arr1)          // n times
        for (int y : arr2)      // m times
            if (x == y)
                System.out.println(
                    "Match: " + x);
}

The outer loop runs n times, once per element of arr1, and each time the inner loop visits all m elements of arr2: n · m comparisons regardless of the input, since the code never exits early.

Tracing printMatches({3, 7, 5}, {5, 1, 3, 8}):

It prints “Match: 3” and “Match: 5” after 3 × 4 = 12 comparisons. Figure 3.28 shows them as a grid: rows are elements of arr1, columns elements of arr2, each cell one comparison.

For two arrays of n elements that is n² comparisons, O(n²): fine for small arrays, but 10 billion for two of 100,000. Two better ways:

• Sort the second array and binary-search it for each element of the first: O(n log n) plus O(n log n), so O(n log n).
• Put the second array in a hash set and look up each element of the first; at O(1) per lookup on average, the total is O(n) on average.

3.5.5Insertion: shifting right

With a fixed size, “insertion” needs unused room. In practice an array often holds fewer elements than its capacity, the used cells packed at the front and their count kept in a separate variable (size), as in the dynamic array of Section 3.2.11.

To insert in the middle, every element after the insertion point shifts one cell right, and the new value goes into the freed cell:

static int insert(int[] a, int size,
             int index, int value) {
  // precondition: size < a.length
  for (int k = size; k > index; k--)
    a[k] = a[k - 1];   // shift right
  a[index] = value;
  return size + 1;   // new size
}

The parameters are the array a, its used-cell count size, the insertion point index, and the value. The precondition says the array must have free room. The loop runs k down from size to index, copying a[k − 1] into a[k]; then the value goes into a[index] and the new size is returned.

We insert 4 at index 1 of a = {7, 2, 9, 5, 1, _} (capacity 6, five used): insert(a, 5, 1, 4).

The method returns 6 after four shifts of 1, 5, 9, and 2. When the loop ends, a[1] and a[2] briefly both hold 2, until a[1] = 4.

The shifting must start from the right. From the left, the first step, a[2] = a[1], would overwrite 9 with 2 and lose it, and the 2 would then spread rightward. From the right, each element moves before it can be overwritten: the first copy fills the empty cell, each later one the spot just vacated.

There are size − index shifts, so the cost depends on position:

• At the front (index = 0): n shifts, O(n), the worst case.
• In the middle: about n/2 shifts, still O(n).
• At the end (index = size): no shifts, one assignment, O(1).

A full array (size == a.length) must first be copied into a larger one, in O(n). Doubling the capacity each time makes such copies rare enough that appending stays constant-time on average.

3.5.6Deletion: shifting left

Deletion reverses insertion: to leave no gap, every element after the deleted position shifts one cell left.

static int remove(int[] a, int size, int index) {
  for (int k = index; k < size - 1; k++)
    a[k] = a[k + 1];   // shift left
  a[size - 1] = 0;    // clear the old last cell
  return size - 1;    // new size
}

This time the shifting starts from the left: the first copy overwrites the deleted value, exactly as intended, and each later copy overwrites the spot just vacated. Starting from the right would lose elements.

After the insertion above, a = {7, 4, 2, 9, 5, 1}. We delete the 4 at index 1: remove(a, 6, 1).

After four shifts the method returns 5 and the array is back to its state before the insertion. The last cell is left with a stale copy of 1 in what is now unused space, so a[5] = 0 clears it. For ints this is optional, since size is 5 and the cell is never read. In an object array, though, the cell must be set to null; otherwise it keeps a reference to a deleted object, which the garbage collector then cannot reclaim. Objects the program no longer uses but that linger in memory this way are a memory leak.

Deletion makes size − index − 1 shifts: n − 1 at the front, O(n); none at the end, O(1). Both insertion and deletion are dearest at the front, so arrays suit poorly a problem with frequent front insertions or deletions.

3.5.7The cost of sorting

Sorted arrays make binary search, the median, the mode, and finding duplicates easy, but sorting has its own cost, which depends on the algorithm. Table 3.25 compares five common ones.

* For the version that stops after a pass with no swaps; on an already sorted array it stops after one pass.

** Quicksort’s extra memory is its recursion depth: O(log n) on average, O(n) in the worst case. Sorting the smaller part first keeps it within O(log n) even then.

Three observations. The three simple algorithms need no extra memory but are O(n²) on average, fit only for small arrays. Quicksort is very fast on average, but bad pivot choices — the pivot is the element used to split the array — can make it quadratic; always taking the first element of an already sorted array, for instance, makes every split lopsided. Merge sort is O(n log n) in every case but needs O(n) extra memory.

Java’s Arrays.sort picks by type: dual-pivot quicksort for primitive arrays (int[], double[] …), and TimSort, a stable algorithm, for object arrays. A stable sort keeps equal keys in their original order: sort students by name, then by grade, and those with equal grades stay in name order. Equal primitives are indistinguishable, so they need no stability.

3.5.8Selection sort

Selection sort splits the array into a sorted left part, initially empty, and an unsorted right part. Each pass swaps the smallest unsorted element with the first unsorted one, growing the sorted part by one. After n − 1 passes the last element is in place by itself.

int[] arr = {64, 25, 12, 22, 11};
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < n; j++)
        if (arr[j] < arr[minIndex])
            minIndex = j;
    // swap: by index, in place
    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}

i marks the start of the unsorted part. minIndex starts at i, and the inner loop, from i + 1 to the end, updates it at each smaller element. The minimum is then swapped with arr[i], by index and through a temporary, as in Section 3.3.8.

Sorting {64, 25, 12, 22, 11}:

Pass 1 swaps the minimum, 11, from the end with 64, settling index 0 for good. Pass 2 starts at index 1 and finds 12. In pass 4 the minimum is already in front (minIndex = i = 3) and is swapped with itself. The last element, 64, is in place by itself.

With n = 5 the example made 4 + 3 + 2 + 1 = 10 = 5 · 4 / 2 comparisons, and an already sorted array would cost the same 10: selection sort never notices sorted input. But it makes at most n − 1 swaps, an advantage when swaps are expensive, as with large records.

3.5.9Insertion sort

Insertion sort works the way a card player orders a hand, sliding each new card into place among those already sorted. The array’s left part is always sorted, starting as just a[0] (one element is always sorted); each pass inserts the next element into its proper place there.

static void insertionSort(int[] a) {
    for (int k = 1; k < a.length; k++) {
        int key = a[k];
        int j = k;
        while (j > 0 && a[j - 1] > key) {
            a[j] = a[j - 1];   // shift right
            j--;
        }
        a[j] = key;        // insert
    }
}

Each pass copies the next element into key, turning its cell into a “hole.” While the element left of the hole is larger than the key, it shifts right into the hole and the hole moves left. When the left element is not larger, or the hole reaches the front (j == 0), the key drops in. This is the shifting of Section 3.5.5, with the insertion point found along the way.

Sorting {5, 2, 4, 1, 3}:

In pass 3 the key is 1 and the sorted part {2, 4, 5}. 5 > 1 shifts right, moving the hole to index 2; 4 > 1 moves it to 1; 2 > 1 moves it to 0. With j = 0 the loop stops and a[0] = 1 is written: a key smaller than the whole sorted part shifts all of it.

There were 1 + 1 + 3 + 2 = 7 shifts in all. The number is not arbitrary: it equals a measure of how “unsorted” the array is.

The inversions of {5, 2, 4, 1, 3}, by value, are (5, 2), (5, 4), (5, 1), (5, 3), (2, 1), (4, 1), (4, 3): seven pairs, matching the seven shifts.

Hence insertion sort is very fast on nearly sorted arrays: few misplaced elements mean few inversions and nearly linear time, whereas selection sort makes n(n − 1)/2 comparisons even on sorted input. That is why library algorithms such as TimSort sort small pieces by insertion. It is also stable: a[j − 1] > key stops at an equal element, so equal elements keep their order.

3.5.10Space complexity and memory use

Space complexity describes how the memory an algorithm or data structure needs grows with n, using the same notation as time complexity. An array of n elements takes O(n) space; how many bytes depends on the element type.

Two details need explaining. A Java char is a UTF-16 code unit and takes 2 bytes, even for ASCII characters. Whether a reference takes 4 or 8 bytes depends on the JVM and its settings; 64-bit JVMs usually compress references to 4 bytes.

On top of the data come two more costs:

• Overhead. Every array object also has a header of about 16 bytes recording such things as the object’s type and the array’s length. Negligible for a large array, it adds up over many small ones.
• Arrays of references. In an object array such as String[], only the references are contiguous. The objects they point to take separate space on the heap, each with its own header. The 400 bytes of a 100-element String[] are just the references; the strings themselves come on top.

An algorithm’s space cost counts only the memory it allocates beyond its input. Here, linear search, the mean, in-place reversal, insertion, deletion, selection sort, and insertion sort use O(1) extra memory; the median and mode use O(n) for their copy, and transposition O(m · n) for the new matrix. Time and memory often trade off: more memory can buy speed, and less can cost it.

3.6Common mistakes

Most array mistakes have a few sources: indices start at 0, an array is an object, and = and == work on references. Table 3.29 collects the mistakes discussed throughout these notes.

The shared lesson: an array variable is not the array but an arrow to it. = copies the arrow, == compares arrows, println prints the arrow. To work on the contents, go through the cells by index or use an Arrays method that does.

3.7Summary

• An array holds a fixed number of elements of one type in contiguous memory slots, indexed from 0 to length − 1. Element i is at base + i × element size, computed in one step, so access by index is O(1).
• Arrays offer fast access, no reference overhead, and cache-friendliness; their weaknesses are fixed size, shifting on insertion and deletion (O(n)), and wasted capacity. Java arrays are covariant, so a store of the wrong type is caught only at run time, with an ArrayStoreException.
• A Java array is an object on the heap; the variable on the stack holds only its reference. Elements of an array created with new get default values (0, 0.0, false, '\u0000', null). length is a field.
• = copies the reference; a real copy takes clone(), Arrays.copyOf, or System.arraycopy (O(n)). == compares references; compare contents with Arrays.equals and print with Arrays.toString.
• The garbage collector collects unreachable arrays. An out-of-bounds access throws ArrayIndexOutOfBoundsException; Java checks every access, C does not.
• The mean takes one pass, O(n) time and O(1) extra memory. The median and mode are found on a sorted copy and cost the O(n log n) of sorting; the copy protects the caller’s array.
• In-place reversal moves two pointers inward from the ends and makes ⌊n/2⌋ swaps: O(n) time, O(1) extra memory. The Caesar cipher relies on char values being integers and on % 26 for wraparound.
• A Java matrix is an array of arrays: m.length is the number of rows and m[i].length the number of columns in row i. Rows may differ in length (a jagged array). m.clone() gives a shallow copy; a deep copy copies every row as well.
• Traversing, filling, or transposing an m × n matrix is O(m · n). The body of nested loops runs as many times as the product of their iteration counts.
• Linear search is O(n) in the worst case; binary search on a sorted array is O(log n). Finding the common elements of two arrays with nested loops is O(n · m).
• Insertion shifts right to left, deletion left to right; both are O(n) in the worst case and O(1) at the end.
• Selection sort makes n(n − 1)/2 comparisons on every input. Insertion sort makes as many shifts as there are inversions: O(n) on a sorted array, O(n²) in the worst case. Both use O(1) extra memory.

3.8Key terms

Each term links to the course glossary, which gives its Turkish equivalent and its use in other chapters.

• array
• element
• index
• initializer
• capacity
• static array
• dynamic array
• reference
• covariance
• heap memory
• stack frame
• two-dimensional array
• multidimensional array
• matrix
• jagged array
• shallow copy
• deep copy
• transpose
• median
• mode
• in-place
• swap
• linear search
• binary search
• bubble sort
• selection sort
• insertion sort
• quicksort
• merge sort
• stable (sort)
• time complexity
• space complexity

3.9Test Yourself

1. After int[] a = {4, 7, 1}; int[] b = a; a = new int[] {0}; b[1] = 9;, which arrays do a and b point to?

   Answer

   a = [0], b = [4, 9, 1]. After b = a both point to the first array. Assigning a new array to a changes only a’s reference, so b still points to the first array, which b[1] = 9 then changes. The new array is unaffected.

2. What do Arrays.toString(new double[3]), Arrays.toString(new boolean[2]), and Arrays.toString(new String[2]) print?

   Answer

   [0.0, 0.0, 0.0], [false, false], and [null, null]. Elements of an array created with new get their type’s default value, and the default for String is null, not the empty string.

3. What are the mean and median of {10, 2, 7, 3, 100, 1}? Which better describes the “middle” of the data?

   Answer

   The sum is 123, so the mean is 123 / 6 = 20.5. Sorted, the array is {1, 2, 3, 7, 10, 100}; the size is even, so the median is the mean of 3 and 7 at indices 2 and 3: 5.0. Five of the six values are 10 or less; the 100 has pulled the mean up. The median ignores the extreme value and describes the middle better.

4. What does mode({8, 3, 8, 5, 3, 8}) return? How many times is the record updated during the loop?

   Answer

   The sorted copy is {3, 3, 5, 8, 8, 8}. At i = 1, 3 is seen a second time and the record becomes 3 (twice). At i = 2 and i = 3 new values begin and the counter is 1. At i = 4, 8 has been seen twice, but 2 > 2 is false. At i = 5, 8 is seen a third time and the record becomes 8 (three times). The method returns 8; the record changes twice in the loop.

5. What does encrypt("JAVA", 5) return? With what k must the same method be called to decrypt?

   Answer

   J: 9 + 5 = 14 → O. A: 0 + 5 = 5 → F. V: 21 + 5 = 26, 26 % 26 = 0 → A. A → F. The result is "OFAF". To decrypt, use k = 26 − 5 = 21: encrypt("OFAF", 21) → "JAVA".

6. If the Pascal’s triangle code runs with n = 6, what is row p[5]? How many cells does the triangle use?

   Answer

   The rows are 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1; 1 5 10 10 5 1, so p[5] = [1, 5, 10, 10, 5, 1]; for example, p[5][2] = p[4][1] + p[4][2] = 4 + 6 = 10. It uses 1 + 2 + … + 6 = 21 cells, where a 6 × 6 square matrix would use 36.

7. A 3 × 3 × 3 array holds x * 9 + y * 3 + z + 1. Which cell holds 20?

   Answer

   Since 20 − 1 = 19 = 2 · 9 + 0 · 3 + 1, x = 2, y = 0, z = 1: array3D[2][0][1], the second cell of the first row of the third layer.

8. With a = {5, 6, 8, 9, 0} and size = 4, insert(a, 4, 0, 7) is called. How many shifts are made, and what is the array? What happens if remove(a, 5, 4) is called next?

   Answer

   Inserting at the front shifts all four elements: 4 shifts, for k = 4, 3, 2, 1. The array becomes {7, 5, 6, 8, 9} and the method returns 5. remove(a, 5, 4) deletes the last element: the loop condition 4 < 4 is false from the start, so nothing shifts. a[4] = 0 is written, the array becomes {7, 5, 6, 8, 0}, and the method returns 4. Inserting at the front is O(n); deleting at the end is O(1).

9. {4, 3, 2, 1} is sorted first with selection sort, then (starting from the same array) with insertion sort. How many comparisons does selection sort make, and how many shifts does insertion sort make? What are the answers for {1, 2, 3, 4}?

   Answer

   Selection sort makes n(n − 1)/2 = 6 comparisons on every input, 6 for both arrays. Insertion sort makes as many shifts as there are inversions. In {4, 3, 2, 1} every pair is an inversion: 6 shifts (1 + 2 + 3). {1, 2, 3, 4} has no inversions: 0 shifts. Then each pass ends after one comparison, for 3 comparisons in total.

10. How many bytes is the data of a matrix created with new int[1000][1000]? In the worst case, how many comparisons does searching it for a value cell by cell take?

    Answer

    The data is 1,000,000 × 4 = 4,000,000 bytes (about 4 MB), plus the headers of the 1000 row arrays and the outer array and the 1000 references in the outer array. A search that visits every cell makes 1,000,000 comparisons when the value is absent: O(r · c) for an r × c matrix.

3.10Further reading

• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Section 3.1: covers topics from these notes — sorting arrays, java.util.Arrays, simple encryption with character arrays, and board games on two-dimensional arrays — in Java code.
• R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Sections 1.1 and 2.1: using arrays in Java, the distinction between reference and copy, and a comparative analysis of selection and insertion sort, with clear examples.
• J. Gosling et al., The Java Language Specification, Java SE 17 Edition, Chapter 10: the official definition of array declaration, initialization, default values, the shallow-copy behavior of clone, and ArrayStoreException.

3.11References

1. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
2. J. Gosling, B. Joy, G. Steele, G. Bracha, A. Buckley, D. Smith, G. Bierman, The Java Language Specification, Java SE 17 Edition, Oracle, 2021.
3. R. Lafore, Data Structures and Algorithms in Java, 2nd ed., Sams, 2002.
4. Oracle, Java SE 17 API Specification: documentation for java.util.Arrays and java.lang.System.
5. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.

Related pages: Chapter 3 slides · Study questions · Array simulator · Glossary · © Sercan Külcü. All rights reserved.