← Back to Subjects ororo.world

Chapter 8: Arrays (Single and Double Dimensional)

In the middle of the 1950s, a team at IBM led by John Backus built the first compiler for FORTRAN, a language meant for people doing heavy numerical work. Those users had a problem that had nothing to do with mathematics. A scientist working with two hundred readings could not sensibly invent two hundred variable names, and even if she did, no loop could visit them, because a loop can change a number but it cannot change a name.

FORTRAN’s answer was the DIMENSION statement. You declared one name and said how many cells it stood for, and from then on you reached a cell by writing the name with a number beside it. The number could be held in a variable. That single change is what made loops and data fit together, and almost every language since has kept the idea.

One detail took longer to settle. Should the first cell be number one, as counting normally begins, or number zero? In 1982 the computer scientist Edsger W. Dijkstra circulated a short note arguing that numbering ought to start at zero, because it makes the arithmetic of ranges come out cleanly. Java agrees with him, which is why your first element lives at index 0 — and why so many first programs run one step too far.

Diagram

Fig. 8.0-1 – a long horizontal strip of ten equal memory cells under one common name, labelled with indices 0 to 9 below the cells and sample marks inside them; a single variable named i drawn as a small box with an arrow pointing at the cell it currently selects; caption area showing the same cells reachable by changing i rather than by changing the name

NoteCuriosity Corner

Q1. Why does the first element of an array in Java sit at index 0 rather than at index 1? Q2. A program can reach the 500th element of an array just as quickly as the 2nd. How is that possible when the 500th is so much further away? Q3. To find one name in a sorted list of a thousand, is it better to check each name in turn or to keep halving the list? And why does halving refuse to work unless the list is already sorted? Q4. Bubble sort, selection sort and insertion sort all leave the same numbers in the same final order. So what actually makes them three different methods? Q5. Memory is one long line of cells, yet a marks table has rows and columns. How does a two-dimensional table get laid out in a one-dimensional memory?

This chapter will answer each of these questions as it goes.

8.1 Why a Single Variable Is Not Enough

A class teacher enters the marks of forty students, adds them, finds the average, and then wants to know how many students scored above that average. The first two tasks are easy. The third one quietly changes everything, because it cannot be done until every mark has already been seen — and to compare a mark with the average, the mark must still be there when the average is known.

That is the real problem this chapter solves. It is not about handling many values. It is about handling many values that all have to stay.

One variable holds one value

A variable of a primitive type names exactly one location in memory. Assigning to it replaces whatever was there. Consider this fragment, which reads ten numbers using a Scanner object named in:

int m = 0;
for (int i = 1; i <= 10; i++)
{
    m = in.nextInt();
}

Ten numbers are typed, ten assignments happen, and at the end m holds the tenth. The other nine are gone. They were never lost by mistake; they were overwritten, one by one, exactly as the program instructed. Any question that needs to look back — the average, the highest, the count above average — is now unanswerable.

Ten variables are worse, not better

The obvious repair is to use ten variables: m1, m2, m3, and so on. For ten values this is merely tedious. For forty it is unworkable, and for a number decided while the program runs it is impossible.

The deeper objection is not length. It is that a name is fixed when the program is compiled, while a value can change while the program runs. A loop can count i from 1 to 10, but no loop can turn the name m1 into the name m2. So a set of separate variables cannot be visited by a loop at all, and every operation on them — reading, adding, comparing, printing — must be written out by hand, once per variable.

What is needed is a way to keep the name fixed and let a number select which value we mean, because a number can be held in a variable, and a variable can be changed by a loop.

One name, many cells

That is exactly what an array provides. An array is a block of memory holding a fixed number of values of the same type, all reachable through one common name, with a number attached to that name deciding which one is meant. Each individual value in the block is called an element.

If the array is named m, then m[0], m[1], m[2] … are its elements, and the number in the brackets may be written as a literal or supplied by a variable. Because it may be supplied by a variable, a loop can now do the walking:

  • to read forty marks, run the loop and let the loop counter choose the cell;
  • to add them, run the loop again over the same cells;
  • to count those above the average, run it a third time — and the marks are all still there.

An array is Java’s simplest structured data type: a single type built out of many values of one other type, held together as one object.

NoteDefinition

An array is a collection of a fixed number of elements of the same data type, stored together under one name, where each element is selected by an integer position within the collection.

Every part of that sentence does work. Fixed number — the size is decided when the array is created and cannot grow afterwards. Same data type — an array of int holds only int values. One name — there is a single identifier for the whole collection. An integer position — and it is that integer, not a name, that makes loops possible.

Diagram

Fig. 8.1-1 – two panels side by side. Left panel: five separate boxes labelled m1, m2, m3, m4, m5, each holding one mark, with a crossed-out arrow from a loop counter i showing that i cannot select among them. Right panel: one contiguous strip of five cells under the single name m, holding the same marks, positions 0 to 4 written below the cells, and an arrow from the loop counter i pointing to the cell at position i, showing that changing i moves the arrow

Table 8.1 – Separate variables vs an array

Feature Separate variables Array
Naming one name for each value one name for the whole collection
Selecting a value by writing the name by an integer position that a variable can supply
Use with a loop not possible natural; the loop counter selects the element
Number of values must be decided and written out in the source code size fixed when the array is created, but the code does not change with it
Types held each variable may be of a different type every element is of the same type
Code length grows with the number of values stays the same however many values there are
What arrays are good at, and what they are not

Two properties matter throughout this chapter. The first is a strength: reaching an element by its position takes the same small amount of work whatever the position is, so m[499] is found as fast as m[1]. Nothing is counted or skipped over; the position is turned into an address by arithmetic. Section 8.9 shows exactly how that arithmetic works.

The second is an honest limitation, and it is really three. An array cannot change its size after it is created. It cannot hold a mixture of types. And because the elements sit in consecutive positions, putting a new value into the middle or taking one out of the middle forces the rest to shift, one cell at a time — you will write that shifting yourself in section 8.7.

None of this makes arrays a poor choice. It makes them a specific choice: right for a known quantity of same-typed data that must be visited repeatedly, wrong for a collection that keeps growing and shrinking unpredictably.

Q. An array is created to hold 10 marks and an eleventh student joins. What has to happen?

A. A larger array must be created and the ten existing values copied into it. The original array cannot be stretched, because its size was fixed at the moment it was created.

On paper, write down three tasks a school office performs on a list of marks — for example, printing all marks above a cut-off. For each one, state whether it can be done while reading the marks, or only after every mark has been stored. The second kind is what arrays exist for.

8.2 The Single Dimensional Array

When every element of an array is selected by a single position number, the array is called a single dimensional array. It is the array in its plainest form: one row of cells, one number to pick a cell. Everything else in this chapter is built on it, including the two-dimensional table you will meet in section 8.8.

8.2.1 Declaring and Creating an Array

Bringing an array into existence takes two distinct steps, and Java lets you write them together or apart.

The first step declares a variable that is allowed to refer to an array of a stated type. The second step actually creates the block of cells and fixes how many there are. The new operator does the creating.

int marks[] = new int[10];

Read it in pieces. int is the type of every element. marks is the name of the whole collection. The empty pair of brackets after the name says that marks is an array variable rather than a single int. new int[10] sets aside ten int cells in memory and hands back a way of reaching them, which is stored in marks.

The brackets may sit on either side of the name, and both forms mean exactly the same thing:

int marks[] = new int[10];
int[] marks2 = new int[10];

Placing the brackets next to the type — int[] marks2 — reads more naturally as “an array of int called marks2”, and is the form you will see most often in modern code. This book uses whichever form makes a particular line clearest; neither is more correct than the other.

Diagram

Fig. 8.2-1 – anatomy of the statement int marks[] = new int[10]; with labelled callouts pointing to each part: ‘int’ labelled element type, ‘marks’ labelled name of the array, ‘[ ]’ labelled marks the variable as an array, ‘new’ labelled creates the block in memory, ‘[10]’ labelled number of cells; below the statement, a strip of ten empty cells with positions 0 to 9 written underneath

Declaring now, creating later

The two steps can also be separated, which is useful when the size is not known until the program runs:

int marks[];
int n = in.nextInt();
marks = new int[n];

Here the size comes from a value typed by the user. Java evaluates the expression inside the brackets at the moment new runs, so any int expression is allowed — a literal, a variable, or a calculation. The size is fixed at that moment and cannot change afterwards.

The variable holds a reference, not the cells

An array in Java is an object. The variable marks does not contain the ten values; it contains a reference — a way of reaching the block where the ten values live. This is why the declaration and the creation are separate steps at all: until new runs, the variable refers to nothing, and its value is the special literal null.

Diagram

Fig. 8.2-2 – a small box labelled marks on the left containing an arrow-like reference value, an arrow from it leading to a separate contiguous block of ten cells on the right labelled positions 0 to 9; a caption line indicating that the variable holds the reference while the block holds the elements

That distinction has one practical consequence worth noticing early. Writing b = a between two array variables does not copy any elements; it makes b refer to the same block as a, so a change made through b is visible through a. Copying elements has to be done element by element, with a loop.

NoteDefinition

Creating an array means allocating a fixed block of memory for its elements with the new operator; declaring an array variable only creates a name capable of referring to such a block.

8.2.2 Subscripts and the Range 0 to n–1

The number written in brackets after the array name is called the subscript, or equivalently the index, of the element. The name together with its subscript — marks[3] — is called a subscripted variable, and it behaves in every way like an ordinary variable of the element type. It can be read, assigned to, passed to a method, or used in an expression.

marks[0] = 78;
marks[1] = marks[0] + 5;
System.out.println(marks[1]);

In Java the subscripts of an array of size n run from 0 to n – 1. An array created as new int[10] therefore has valid subscripts 0 to 9. There is no marks[10].

The reason is that a subscript is not a count of elements; it is a distance from the beginning of the block. The first element is at the beginning, so its distance is zero. The second is one cell further along, so its distance is one. Counting distances rather than positions is what makes the arithmetic behave: the number of elements between subscripts i and j is simply j – i, with no adjustment, and a loop written as

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

visits every element exactly once, with the bound stated plainly and no + 1 or – 1 anywhere.

Q1. Why does the first element of an array in Java sit at index 0 rather than at index 1?

A. Because a subscript records how far an element lies from the start of the block, not which number it is in a count. The first element lies at the start itself, a distance of zero. Numbering this way keeps every range calculation clean — the elements of an array of size n occupy subscripts 0 to n – 1, the gap between two subscripts is their difference, and a loop needs only the condition i < n to cover the whole array.

using the size as if it were a valid subscript What students write:

int marks[] = new int[5];
for (int i = 1; i <= 5; i++)
{
    marks[i] = 0;
}

What happens: the loop runs with i equal to 5 on its last pass. There is no cell at subscript 5, so the program stops at run time with an ArrayIndexOutOfBoundsException. The value at subscript 0 is never touched either — the loop skipped the first cell and then ran off the end. The fix:

for (int i = 0; i < 5; i++)
{
    marks[i] = 0;
}

Start at 0 and stop before the size. The condition i < size is the safe habit; i <= size almost never is.

8.2.3 Default Values of Array Elements

An ordinary local variable must be given a value before it is used; the compiler refuses to read one that has not been assigned. Array elements are different. Because an array is an object created by new, Java fills every cell with a default value at the moment of creation, and those values may be read straight away.

The defaults are fixed by the element type.

Table 8.2 – Default value stored in an array element at the time of creation, for each element type

Element type Default value Printed as
byte, short, int zero 0
long zero 0
float zero 0.0
double zero 0.0
char the character with code 0 nothing visible
boolean false false
String and any other object type no object at all null

The last row is worth pausing on. String is not a primitive type, so an array of String does not contain strings; it contains references, and until you put something in each cell, every reference is null. Creating new String[5] therefore creates no strings whatever — only five empty places where strings may later be referred to.

The program below shows the defaults for four common types.

displaying the default values stored in newly created arrays Problem: Create four arrays of size 4 — of types int, double, boolean and String — without assigning anything to their elements, and display the contents of each array on one line, so that the value Java placed in every cell can be seen. There is no input.

// Displays the values Java places in array elements when an array is created.
class ArrayDefaults
{
    public static void main(String args[])
    {
        int marks[] = new int[4];
        double price[] = new double[4];
        boolean present[] = new boolean[4];
        String city[] = new String[4];
        int i;

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

        System.out.print("double :");
        for (i = 0; i < 4; i++)
        {
            System.out.print(" " + price[i]);
        }
        System.out.println();

        System.out.print("boolean:");
        for (i = 0; i < 4; i++)
        {
            System.out.print(" " + present[i]);
        }
        System.out.println();

        System.out.print("String :");
        for (i = 0; i < 4; i++)
        {
            System.out.print(" " + city[i]);
        }
        System.out.println();
    }
}

Sample output:

int    : 0 0 0 0
double : 0.0 0.0 0.0 0.0
boolean: false false false false
String : null null null null

Variable description:

[Table:] Table 8.3 – Variable description for the program ArrayDefaults [/Table] | Variable | Type | Purpose | |—|—|—| | marks | int[] | array of four integers, left at its default values | | price | double[] | array of four real numbers, left at its default values | | present | boolean[] | array of four truth values, left at its default values | | city | String[] | array of four String references, left at their default value | | i | int | loop counter used as the subscript in each traversal |

Notes: The four loops are identical apart from the array they read, which is the point — the defaults are decided by the element type, not by anything the program does. print is used inside each loop and println after it, so that one array occupies one line. The double cells print as 0.0 rather than 0, because their type, not their value, decides how they are displayed.

8.2.4 Initialising an Array at the Point of Declaration

When the values are known while the program is being written, they can be listed inside braces, separated by commas. This is called an initialiser list.

int fare[] = {12, 15, 15, 20, 26, 30};

Two things happen automatically. The array is created — no new is needed — and its size is taken from the number of values in the list, here six. The values are stored in the order written, so fare[0] is 12 and fare[5] is 30.

The same form works for any element type. Characters go in single quotes and strings in double quotes:

char grade[] = {'A', 'B', 'C', 'D', 'E'};
String subject[] = {"English", "Physics", "Chemistry", "Computer Science"};

An initialiser list is only allowed in a declaration. Once the variable exists, values must be placed one at a time, or a fresh array must be created and assigned.

giving both a size and a list of values What students write:

int fare[] = new int[6]{12, 15, 15, 20, 26, 30};

What happens: the program does not compile. Java refuses to be told the size twice, and the size is already implied by the list. The fix:

int fare[] = {12, 15, 15, 20, 26, 30};

Write the list alone. If the new form is wanted for some reason, the brackets must be left empty: int fare[] = new int[]{12, 15, 15, 20, 26, 30}; is also correct, and again takes its size from the list.

8.2.5 Arrays of Other Data Types

Nothing about the syntax changes when the element type changes. The type appears twice — once in the declaration and once after new — and the two must agree.

Table 8.4 – Creating an array of ten elements, for each of several element types

To hold Written as
integers int m[] = new int[10];
real numbers of single precision float m[] = new float[10];
real numbers of double precision double m[] = new double[10];
single characters char ch[] = new char[10];
truth values boolean flag[] = new boolean[10];
strings String name[] = new String[10];

An array is strictly of one type. marks[2] = 'A'; is not an error in an int array — the character is converted to its code — but marks[2] = "A"; is, because a String cannot be turned into an int by the compiler. Mixed data needs either separate arrays that run in step, or a class of your own with one field per item of information.

8.2.6 The length Attribute

Every array carries its own size with it. Writing marks.length gives the number of elements in marks, and it is available wherever the array is available — including inside a method that received the array as an argument and knows nothing else about it.

int fare[] = {12, 15, 15, 20, 26, 30};
System.out.println("Number of fares : " + fare.length);
System.out.println("Last subscript  : " + (fare.length - 1));

This prints Number of fares : 6 and Last subscript : 5. The distinction is the one from section 8.2.2 again: length counts the elements, while the highest legal subscript is one less than that count.

Using length rather than a number typed into the loop is a small habit with a large payoff. A loop written as for (i = 0; i < fare.length; i++) stays correct when the initialiser list grows or shrinks; a loop written as i < 6 silently becomes wrong.

writing length with brackets on an array What students write:

int fare[] = {12, 15, 15, 20, 26, 30};
System.out.println(fare.length());

What happens: the program does not compile. Java reports that it cannot find a method named length() for an array. The fix:

System.out.println(fare.length);

For an array, length is a property of the object and is written with no brackets. The confusion comes from String, where the size is obtained by a method call — s.length(). Array without brackets, String with brackets.

Q. An array is created with new int[0]. Is that an error?

A. No. It creates a perfectly valid array with no elements at all. Its length is 0, so any loop over it simply runs zero times — which is usually exactly the right behaviour for an empty list. Only a negative size is rejected.

Key in the ArrayDefaults program and run it. Now add a fifth array of type char and a loop that prints its four cells the same way. Predict what the line will look like before you run it, then run it and explain what you see using Table 8.2.

8.3 Putting Values into an Array

An array created by new is real but empty of anything useful — every cell holds the default value for its type. Something has to put the actual data in. There are three routes, and they differ in when the values become known.

The initialiser list of section 8.2.4 is the earliest: the values are known while the program is being written. The three routes in this section cover everything later than that — values the program works out for itself, values handed to it when it is started, and values typed while it is running.

8.3.1 By Assignment

The plainest method is to assign to one subscripted variable at a time.

int stock[] = new int[4];
stock[0] = 25;
stock[1] = 12;
stock[2] = 40;
stock[3] = 7;

This is honest but pointless for anything larger than a handful of cells, and it repeats the weakness of separate variables that section 8.1 set out to remove. Assignment becomes powerful only when the subscript is a variable and the value is calculated:

for (int i = 0; i < stock.length; i++)
{
    stock[i] = 0;
}

One statement now fills every cell, whatever the size of the array. And since the loop counter is available inside the loop, the value stored may depend on the position it is stored at — which is how tables, sequences and patterns get built.

building a multiplication table in an array Problem: Store the first ten multiples of 7 in an array, then display them on one line. The multiplier for the element at subscript i is i + 1. Input: none; the number is fixed in the program. Output: a single line listing the ten multiples.

// Fills an array with the first ten multiples of a number, then displays them.
class MultipleTable
{
    public static void main(String args[])
    {
        int number = 7;
        int table[] = new int[10];
        int i;

        for (i = 0; i < table.length; i++)
        {
            table[i] = number * (i + 1);
        }

        System.out.print("Multiples of " + number + " :");
        for (i = 0; i < table.length; i++)
        {
            System.out.print(" " + table[i]);
        }
        System.out.println();
    }
}

Sample output:

Multiples of 7 : 7 14 21 28 35 42 49 56 63 70

Variable description:

[Table:] Table 8.5 – Variable description for the program MultipleTable [/Table] | Variable | Type | Purpose | |—|—|—| | number | int | the number whose multiples are wanted | | table | int[] | holds the ten multiples, one to a cell | | i | int | loop counter, used as the subscript in both loops |

Notes: the multiplier is i + 1 and not i, because the subscript starts at 0 while the first multiple wanted is the first, not the zeroth. This small adjustment between where a value sits and what the value means appears constantly in array work, and it is worth writing out deliberately rather than guessing. Two separate loops are used — one to fill, one to display — because they are two separate jobs; combining them would work here only because nothing is needed before printing begins.

filling the array in MultipleTable, with number = 7

Pass i i + 1 number * (i + 1) cell filled
1 0 1 7 table[0] = 7
2 1 2 14 table[1] = 14
3 2 3 21 table[2] = 21
4 3 4 28 table[3] = 28
5 4 5 35 table[4] = 35
6 5 6 42 table[5] = 42
7 6 7 49 table[6] = 49
8 7 8 56 table[7] = 56
9 8 9 63 table[8] = 63
10 9 10 70 table[9] = 70

Result: the loop ends when i reaches 10, because 10 < table.length is false. Nothing is printed by this loop; the trace shows that ten passes fill ten cells, subscripts 0 to 9, and that the value in a cell is not the same thing as the subscript of that cell.

8.3.2 Through the Argument of main

Every Java program starts at main, and main receives an array. Look again at the header you have written many times:

public static void main(String args[])

args is an array of String. It holds the command-line arguments — the extra words typed after the class name when the program is launched. Running a program as

java ArgSum 12 8 25 5

gives args a length of 4, with args[0] holding the text "12", args[1] holding "8", and so on. Nothing is read from the keyboard while the program runs; the data arrives with the program itself.

Two points decide how such data is used. First, the elements are text even when they look like numbers, so "12" must be converted before it can be added to anything. Integer.parseInt does that conversion, and returns the int the text represents. Second, the program is told how many arguments it received by args.length, so it need not be written for a fixed count.

totalling numbers supplied on the command line Problem: Accept any quantity of whole numbers as command-line arguments, store them in an int array, and display how many were received together with their total. Input: the numbers are typed after the class name when the program is launched, for example java ArgSum 12 8 25 5. Output: two labelled lines.

// Reads whole numbers supplied as command-line arguments and totals them.
class ArgSum
{
    public static void main(String args[])
    {
        int n[] = new int[args.length];
        int total = 0;
        int i;

        for (i = 0; i < args.length; i++)
        {
            n[i] = Integer.parseInt(args[i]);
            total = total + n[i];
        }

        System.out.println("Values received : " + n.length);
        System.out.println("Total           : " + total);
    }
}

Sample output, for the launch java ArgSum 12 8 25 5:

Values received : 4
Total           : 50

Variable description:

[Table:] Table 8.6 – Variable description for the program ArgSum [/Table] | Variable | Type | Purpose | |—|—|—| | args | String[] | the command-line arguments, as text | | n | int[] | the same values converted to whole numbers | | total | int | running sum of the values | | i | int | loop counter and subscript |

Notes: the array n is created with size args.length, so the program adapts to however many numbers are supplied — including none, in which case the loop runs zero times and the total is 0. If any argument is not a whole number, Integer.parseInt cannot do its work and the program stops with an error; a program meant for real users would check the text first.

Passing an array to a method directly

In a development environment such as BlueJ, a static method can also be invoked on its own from a menu, with its argument typed into a dialogue box. Because of this you may see a class written with a header such as public static void main(int m[]), the values being supplied in braces as {1, 2, 3, 4} when the method is called.

This is worth understanding for what it is: a convenience of the environment for calling a method, not the way a Java program is normally started. When the Java runtime launches a class by itself, it looks for main with a String array parameter and nothing else. A class whose only main takes an int array will compile, but it cannot be started in the usual way.

8.3.3 Reading Values with the Scanner Class

Most programs need values that are not known until they are running. The Scanner class of the java.util package reads them from the keyboard.

import java.util.Scanner;

A Scanner object is created once, attached to the standard input stream, and then asked repeatedly for the next value:

Scanner in = new Scanner(System.in);
int n = in.nextInt();

Each call reads one item and moves past it, so a loop calling nextInt() fills an array one cell per pass. Which method to call depends on the type wanted.

Table 8.7 – Commonly used Scanner methods and what each returns

Method Reads and returns
nextInt() the next whole number, as an int
nextLong() the next whole number, as a long
nextDouble() the next real number, as a double
next() the next word, up to the next space, as a String
nextLine() the rest of the current line, as a String
nextBoolean() the next true or false, as a boolean

Diagram

Fig. 8.3-1 – flow: value typed at the keyboard → standard input stream (System.in) → Scanner object named in → in.nextInt() returns one whole number → assignment to marks[i] → the cell at subscript i inside the array block

There is no method for reading a single character. A character is obtained by reading a word and taking its first letter, which is the source of a common mistake.

expecting a nextChar method What students write:

char grade[] = new char[5];
grade[0] = in.nextChar();

What happens: the program does not compile. The compiler reports that Scanner has no method named nextChar(), because no such method exists. The fix:

grade[0] = in.next().charAt(0);

next() reads a word as a String, and charAt(0) takes its first character. If the user types A, the array cell receives 'A'.

One further caution about mixing methods. nextInt() stops as soon as the number ends and leaves the rest of the line, including the end-of-line mark, still waiting. A nextLine() called immediately afterwards therefore returns that leftover remainder rather than the next line typed. Reading a whole line after a number needs an extra nextLine() to clear what is left behind.

storing marks entered at the keyboard Problem: Read the number of students, create an array of exactly that size, read one mark for each student, and then display the stored marks with their subscripts. Input: a count, followed by that many whole numbers, typed at the keyboard. Output: one line per stored mark.

// Reads a set of marks into an array and displays them with their subscripts.
import java.util.Scanner;

class MarksEntry
{
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        int i;

        System.out.print("How many students? ");
        int n = in.nextInt();
        int marks[] = new int[n];

        System.out.println("Enter " + n + " marks:");
        for (i = 0; i < n; i++)
        {
            marks[i] = in.nextInt();
        }

        System.out.println("Marks as stored:");
        for (i = 0; i < n; i++)
        {
            System.out.println("marks[" + i + "] = " + marks[i]);
        }
    }
}

Sample output, for the count 5 followed by the marks 62, 48, 35, 71 and 40 (the typed values appear in the transcript as they are echoed by the terminal):

How many students? 5
Enter 5 marks:
62 48 35 71 40
Marks as stored:
marks[0] = 62
marks[1] = 48
marks[2] = 35
marks[3] = 71
marks[4] = 40

Variable description:

[Table:] Table 8.8 – Variable description for the program MarksEntry [/Table] | Variable | Type | Purpose | |—|—|—| | in | Scanner | reads values typed at the keyboard | | n | int | number of students, and hence the size of the array | | marks | int[] | the marks, one to a cell | | i | int | loop counter and subscript |

Notes: the array cannot be created until n is known, so new int[n] comes after the first read — this is exactly the pattern of section 8.2.1, where the size is decided while the program runs. The five marks may be typed on one line separated by spaces or on five separate lines; nextInt() treats any run of spaces or line breaks as a separator, so both work identically.

Q. The user answers 5 but then types only four marks and stops. What does the program do?

A. It waits. The fifth call to nextInt() cannot return until a fifth number is available, so the program simply sits there until one is typed. It is not stuck in a loop; it is stuck on input.

Choosing a way to supply values

Table 8.9 – Three ways of supplying values to an array

Feature Assignment in the program Command-line argument Scanner input
When the values are known while the program is written, or computed as it runs when the program is launched while the program is running
Where they come from the source code, or a calculation the words typed after the class name the keyboard
Type of the incoming data already the correct type always text; must be converted the type asked for by the method called
Who decides how many the programmer, or the loop whoever launches the program; read from args.length usually read as the first input
Suits tables, patterns, fixed data, clearing an array short fixed inputs supplied once data supplied by a person as the program runs

Modify MultipleTable so that the number whose multiples are wanted is read with a Scanner instead of being fixed at 7. Run it for 7 and confirm the output is unchanged, then run it for 13. State which lines of the original program had to change and which did not.

8.4 Traversing an Array

Visiting every element of an array exactly once, in order, is called a traversal. Almost everything an array is used for is a traversal, or several: totalling, averaging, counting, searching, printing, comparing, copying, sorting. Learning to write one correctly is worth more than learning any single algorithm in this chapter.

A traversal has the same shape every time:

for (int i = 0; i < a.length; i++)
{
    // do something with a[i]
}

The counter starts at the first subscript, the condition stops it just past the last, and the body works on one element. What changes from one problem to the next is only the body — and whether one pass is enough.

8.4.1 Summing and Averaging the Elements

To total an array, keep a variable outside the loop that carries the running sum, and add one element to it on each pass:

int total = 0;
for (int i = 0; i < a.length; i++)
{
    total = total + a[i];
}

The variable total must be created before the loop and must start at 0, because it has to survive from one pass to the next and must begin from a known value. A variable used this way — accumulating a result across the passes of a loop — is doing the same work in every array algorithm you will meet.

The average follows from the total, but the division needs care. Both total and a.length are of type int, and dividing one int by another in Java produces an int, with the fractional part discarded.

losing the fractional part of an average What students write:

int average = total / n;

What happens: the program compiles and runs, and quietly gives a wrong answer. With a total of 494 over 8 marks, the true average is 61.75, but integer division throws away the .75 and stores 61. Nothing warns you; the answer is simply short. The fix:

double average = (double) total / n;

Casting one operand to double makes the division a real division. The cast must be applied before the division — writing (double) (total / n) divides first and then converts 61 to 61.0, which is too late.

Why some questions need two passes

Now return to the problem that opened this chapter: how many marks lie above the average? The average is not known until every mark has been added, and each mark has to be compared with it afterwards. So the array must be walked twice — once to total, once to compare. This is exactly the work that cannot be done while the values are being read, and it is the reason the marks had to be stored in the first place.

Diagram

Fig. 8.4-1 – one strip of eight cells holding marks, with two labelled sweeps drawn beneath it. Sweep 1, an arrow left to right, labelled ‘accumulate total’; a box below it showing total growing. Sweep 2, a second arrow left to right, labelled ‘compare each mark with the average’; a box below it showing count growing. A note between the sweeps stating that the average becomes known only when sweep 1 ends

total, average and the count of marks above the average Problem: The marks of eight students are fixed in the program. Display how many marks there are, their total, their average correct to the precision double gives, and how many of the marks are strictly above that average. Input: none. Output: four labelled lines.

// Totals a set of marks, finds their average, and counts the marks above it.
class MarksReport
{
    public static void main(String args[])
    {
        int marks[] = {55, 78, 41, 90, 63, 38, 72, 57};
        int total = 0;
        int count = 0;
        int i;

        for (i = 0; i < marks.length; i++)
        {
            total = total + marks[i];
        }

        double average = (double) total / marks.length;

        for (i = 0; i < marks.length; i++)
        {
            if (marks[i] > average)
            {
                count++;
            }
        }

        System.out.println("Number of marks     : " + marks.length);
        System.out.println("Total               : " + total);
        System.out.println("Average             : " + average);
        System.out.println("Marks above average : " + count);
    }
}

Sample output:

Number of marks     : 8
Total               : 494
Average             : 61.75
Marks above average : 4

Variable description:

[Table:] Table 8.10 – Variable description for the program MarksReport [/Table] | Variable | Type | Purpose | |—|—|—| | marks | int[] | the eight marks | | total | int | running sum of the marks | | average | double | the mean mark, computed after the first traversal | | count | int | how many marks exceed the average | | i | int | loop counter and subscript |

Notes: total and count are both created before their loops and both start at 0, but they accumulate different things — one adds a value, the other adds 1 when a condition holds. The comparison is marks[i] > average, so a mark exactly equal to the average is not counted; a specification should always say which of the two is meant.

the cost of a traversal Let \(n\) be the number of elements in the array. A single traversal performs one visit per element, so the work grows in step with \(n\) and the cost is \(O(n)\). The program above traverses twice, doing about \(2n\) visits, but doubling a quantity does not change how it grows with \(n\) — the dominant term is still \(n\), and the cost remains \(O(n)\).

8.4.2 Finding the Maximum and the Minimum

You cannot know the largest value in an array until you have seen them all, so this too is a traversal. The method is to hold a “best so far” and improve it whenever a better candidate appears.

finding the largest element of an array Input: an array a of n numbers, with n at least 1. Output: the largest value in the array, and the subscript where it occurs. Method:

1. Set max to a[0].
2. Set position to 0.
3. Repeat steps 4 to 6 for i = 1, 2, ..., n-1.
4.    If a[i] > max then do steps 5 and 6, otherwise skip them.
5.        Set max to a[i].
6.        Set position to i.
7. max is the largest value and position is its subscript.

Why it works: after the pass for a given i, max holds the largest of the elements examined so far — this is true at the start, when only a[0] has been examined, and each pass preserves it by replacing max whenever a larger element appears. When the last element has been examined, “so far” means the whole array. Cost: exactly \(n - 1\) comparisons, where \(n\) is the number of elements, in every case. Best, average and worst case are the same, and the cost is \(O(n)\).

The smallest element is found by the same method with the comparison reversed, and both can be tracked in one traversal. Notice that the loop starts at 1, not 0: element 0 has already been used to set the starting values, and comparing it with itself would achieve nothing.

starting the maximum at zero What students write:

int max = 0;
for (int i = 0; i < temp.length; i++)
{
    if (temp[i] > max)
    {
        max = temp[i];
    }
}

What happens: the answer is right for data that happens to contain a positive value, and wrong otherwise. For the temperatures -2, -6, -1 the true maximum is -1, but no element is greater than 0, so the program reports 0 — a value that is not even in the array. The fix:

int max = temp[0];
for (int i = 1; i < temp.length; i++)

Start from an element that is actually present. The same objection applies to starting a minimum at 0, or at 100, or at any other guessed value.

Diagram

Fig. 8.4-2 – a strip of seven cells holding the values -2, 3, 5, -6, 1, 4, 0 with subscripts 0 to 6 beneath. Above the strip, a marker labelled ‘max so far’ drawn at subscript 0, then moved to subscript 1, then to subscript 2, with the value beside it changing from -2 to 3 to 5; the marker then stays over subscript 2 for the remaining cells, showing that no later element is larger

highest and lowest temperature of a week Problem: The daily temperatures of a week, in degrees Celsius, are fixed in the program and may be negative. Display the highest and the lowest, the day number on which each occurred, and the difference between them. Days are numbered from 1. Input: none. Output: three labelled lines.

// Finds the highest and lowest of a week's temperatures, and the day of each.
class TemperatureRange
{
    public static void main(String args[])
    {
        int temp[] = {-2, 3, 5, -6, 1, 4, 0};
        int max = temp[0];
        int min = temp[0];
        int maxDay = 0;
        int minDay = 0;
        int i;

        for (i = 1; i < temp.length; i++)
        {
            if (temp[i] > max)
            {
                max = temp[i];
                maxDay = i;
            }
            if (temp[i] < min)
            {
                min = temp[i];
                minDay = i;
            }
        }

        System.out.println("Highest : " + max + " on day " + (maxDay + 1));
        System.out.println("Lowest  : " + min + " on day " + (minDay + 1));
        System.out.println("Range   : " + (max - min));
    }
}

Sample output:

Highest : 5 on day 3
Lowest  : -6 on day 4
Range   : 11

Variable description:

[Table:] Table 8.11 – Variable description for the program TemperatureRange [/Table] | Variable | Type | Purpose | |—|—|—| | temp | int[] | the seven daily temperatures | | max | int | highest temperature found so far | | min | int | lowest temperature found so far | | maxDay | int | subscript at which max was found | | minDay | int | subscript at which min was found | | i | int | loop counter and subscript |

Notes: maxDay is updated inside the same if that updates max, so the two can never disagree; recording the value in one place and the position in another is a frequent source of bugs. The day number printed is maxDay + 1, because the array is subscripted from 0 while the week is counted from 1 — the same shift met in section 8.3.1. If two days share the highest temperature, this version reports the earlier one, since a later equal value does not satisfy >.

TemperatureRange on the values -2, 3, 5, -6, 1, 4, 0

Pass i temp[i] temp[i] > max? max, maxDay after temp[i] < min? min, minDay after
start – – – -2, 0 – -2, 0
1 1 3 yes 3, 1 no -2, 0
2 2 5 yes 5, 2 no -2, 0
3 3 -6 no 5, 2 yes -6, 3
4 4 1 no 5, 2 no -6, 3
5 5 4 no 5, 2 no -6, 3
6 6 0 no 5, 2 no -6, 3

Result: the output is Highest : 5 on day 3, Lowest : -6 on day 4, Range : 11. The trace shows the point of the method — max and min are each replaced only twice in seven passes, yet every element is still examined, because a value cannot be dismissed without being compared.

8.4.3 Staying Inside the Bounds

Every array access in Java is checked as the program runs. If a subscript falls outside the range 0 to length - 1, the program stops immediately with an ArrayIndexOutOfBoundsException, naming the offending value. Section 8.2.2 showed the classic way of producing one; the concern here is the choice of loop bounds while traversing.

Not every traversal covers the whole array, and the header must say which elements are wanted.

Table 8.12 – Loop headers for traversing an array a of n elements, and what each visits

Loop header Elements visited Typical use
for (i = 0; i < n; i++) all, first to last totalling, counting, printing
for (i = n - 1; i >= 0; i--) all, last to first printing in reverse, shifting values to the right
for (i = 1; i < n; i++) all except the first the body compares with a value already taken from a[0]
for (i = 0; i < n - 1; i++) all except the last the body touches a[i + 1] as well as a[i]

The last row is the one that catches people. Whenever the body of a loop mentions a[i + 1], the largest i allowed is n - 2, so the condition must be i < n - 1. Written as i < n, the final pass reaches a[n], which does not exist. You will meet this exact situation in bubble sort, where neighbouring elements are compared.

Reverse traversal deserves the same attention. The counter starts at n - 1, because that is the last valid subscript, and the condition is i >= 0 rather than i > 0, or element 0 is never reached.

Q. Checking every subscript costs time. Why does Java do it at all?

A. Because an unchecked wrong subscript would read or overwrite memory belonging to something else, and the damage would surface far away from the line that caused it. The check converts a silent corruption into an immediate, precisely located error — cheap insurance for a fault that is otherwise very hard to trace.

Take the TemperatureRange program and change the loop header to for (i = 1; i <= temp.length; i++). Before running it, write down what you expect to happen and at which value of i. Run it, read the message the program prints when it stops, and check whether the value named matches your prediction. Restore the correct header afterwards.

8.5 Searching an Array

Searching means finding out whether a particular value is present in an array and, if it is, where. The value being looked for is called the search key, and a search should report the position rather than a bare yes or no, because the position is what lets the program do anything useful afterwards — print the matching record, change it, remove it.

There are two standard methods, and the difference between them is not merely speed. One works on any array at all. The other buys its speed by demanding something in return.

8.5.3 Choosing Between the Two Searches

The two methods answer the same question and are not interchangeable.

Table 8.15 – Linear search compared with binary search

Feature Linear search Binary search
Requirement on the data none; sorted or unsorted the array must be in order
Elements examined one after another from the start only the middle of a shrinking interval
Effect of one comparison rules out one element rules out about half the remaining elements
Best case 1 comparison, \(O(1)\) 1 comparison, \(O(1)\)
Worst case \(n\) comparisons, \(O(n)\) about \(\log_2 n\) comparisons, \(O(\log n)\)
Suits small arrays, or data that arrives unordered large arrays that are already kept in order
Cost of preparation none the array must be sorted, which itself takes work

The last two rows decide most real choices. Binary search is faster per search but is not free, because keeping the data in order costs something. For a single search of an unsorted array, sorting it first and then searching is slower than simply looking through it. For an array that will be searched again and again — a price list, an index, a directory — the sorting is paid for once and every later search is cheap.

what halving actually buys Let \(n\) be the number of elements. Linear search may need \(n\) comparisons; binary search needs about \(\log_2 n\). For \(n = 1000\) that is 1000 against about 10. Doubling the data adds 1000 more comparisons to the linear worst case, but only one more comparison to the binary one — the whole point of an \(O(\log n)\) method.

Q3. To find one name in a sorted list of a thousand, is it better to check each name in turn or to keep halving the list? And why does halving refuse to work unless the list is already sorted?

A. Halving is far better — about ten comparisons instead of up to a thousand, because each comparison discards half of what remains rather than a single entry. It works only on sorted data because of what the program concludes when the middle element does not match. It does not merely learn that this one element is wrong; it concludes that the whole half on one side can be thrown away without being looked at. That conclusion rests entirely on the order: in an unordered list, a value smaller than the middle element could be lying anywhere, so nothing may be discarded, and the method loses the very thing that made it fast.

Q. Binary search reports the subscript of an element equal to the key. If the key occurs three times, which one is reported?

A. Whichever the halving happens to land on — not necessarily the first. Linear search, by contrast, always reports the first occurrence, because it stops the moment it meets one. Where the first occurrence specifically is wanted, that difference has to be handled deliberately.

Both methods have been written here for numbers, compared with < and >. The same two algorithms apply unchanged to an array of text; only the comparison changes, since two String values are ordered by the compareTo() method rather than by the relational operators.

Add a counter to BinarySearch that increases by 1 on every pass of the while loop, and print it at the end. Run the program for each of the nine prices in the list and note the count each time. Which key is found in one pass, and what is the largest count any key needs? Compare that largest count with the number of elements.

8.6 Sorting an Array

Sorting means rearranging the elements of an array so that they run in order — ascending or descending, numerically for numbers and alphabetically for text. It is worth doing for its own sake, because ordered data is easier to read, and worth doing for what it enables: binary search, merging, finding duplicates, ranking.

The syllabus covers three techniques — bubble sort, selection sort and insertion sort. All three produce exactly the same final array. What differs is the strategy: what each one has achieved when it is halfway through, how many comparisons it makes, and how much it moves the data about. That is the real subject of this section.

Every technique here works through a series of passes, one sweep of the data each, and every one of them relies on the swap — exchanging the values in two cells. A swap needs a third variable, because a direct assignment would destroy one of the values before it could be saved:

t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;

All three techniques below are shown ascending, on the same six values — 29, 13, 48, 7, 35, 21 — so that their behaviour can be compared honestly at the end.

8.6.1 Bubble Sort

Bubble sort compares neighbours. It walks along the array comparing each element with the one after it, exchanging the pair whenever they are in the wrong order. One such sweep does not sort the array, but it does one thing reliably: the largest value meets every element it passes, wins every comparison, and is carried all the way to the last cell.

That is the whole idea. After the first pass the largest value is in its final place; after the second pass the second largest is in place; and so on. Each pass may therefore stop one cell earlier than the last, since the tail of the array is already settled.

bubble sort, ascending Input: an array a of n elements. Output: the same array with its elements in ascending order. Method:

1. Repeat steps 2 and 3 for i = 0, 1, 2, ..., n-2.
2.    Repeat step 3 for j = 0, 1, 2, ..., n-2-i.
3.        If a[j] > a[j+1] then exchange a[j] and a[j+1].
4. Stop. The array is in ascending order.

Why it works: during pass i, the largest value among the first n-i elements is exchanged rightwards past every smaller neighbour it meets, so it ends the pass at subscript n-1-i. After n-1 passes the last n-1 positions all hold their correct values, and the single remaining element must be the smallest. Cost: with \(n\) the number of elements, this version always makes \(n(n-1)/2\) comparisons — 15 comparisons for 6 elements — however the data is arranged. The number of exchanges ranges from 0, for data already sorted, to \(n(n-1)/2\) for data in exact reverse order. The cost is \(O(n^2)\).

Note the inner bound carefully: j runs only to n-2-i, because the body compares a[j] with a[j+1] and the largest subscript touched must still be n-1. This is the situation section 8.4.3 warned about.

Diagram

Fig. 8.6-1 – six cells holding 29, 13, 48, 7, 35, 21 with subscripts 0 to 5. Five curved brackets drawn above successive neighbouring pairs (0-1, 1-2, 2-3, 3-4, 4-5), each labelled with the comparison made and marked ‘swap’ or ‘no swap’ for the first pass; below the strip, the result of the pass 13, 29, 7, 35, 21, 48 with the final cell shaded and labelled ‘largest value now settled’

sorting an array by bubble sort Problem: Six whole numbers are fixed in the program in no particular order. Display them as given, sort them into ascending order using bubble sort, and display them again. Input: none. Output: two labelled lines.

// Sorts an array into ascending order by exchanging neighbouring elements.
class BubbleSort
{
    public static void main(String args[])
    {
        int a[] = {29, 13, 48, 7, 35, 21};
        int i, j, t;

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

        for (i = 0; i < a.length - 1; i++)
        {
            for (j = 0; j < a.length - 1 - i; j++)
            {
                if (a[j] > a[j + 1])
                {
                    t = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = t;
                }
            }
        }

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

Sample output:

Before : 29 13 48 7 35 21
After  : 7 13 21 29 35 48

Variable description:

[Table:] Table 8.16 – Variable description for the program BubbleSort [/Table] | Variable | Type | Purpose | |—|—|—| | a | int[] | the numbers to be sorted, rearranged in place | | i | int | counts the passes; also the subscript in the display loops | | j | int | subscript of the left member of the pair being compared | | t | int | temporary store used while exchanging two elements |

Notes: the array is sorted in place — no second array is created, and the original order is lost. The outer loop runs n-1 times rather than n, because once n-1 values have been settled the last one has nowhere else to be. Changing the test from a[j] > a[j + 1] to a[j] < a[j + 1] sorts the array into descending order and changes nothing else.

BubbleSort on 29, 13, 48, 7, 35, 21, shown one pass at a time

Pass (i) Comparisons made Exchanges Array at end of pass
1 (i = 0) 5 4 13 29 7 35 21 48
2 (i = 1) 4 2 13 7 29 21 35 48
3 (i = 2) 3 2 7 13 21 29 35 48
4 (i = 3) 2 0 7 13 21 29 35 48
5 (i = 4) 1 0 7 13 21 29 35 48

Result: the array is in ascending order, and 15 comparisons were made in all. The trace exposes a real weakness — the data was already sorted at the end of pass 3, yet passes 4 and 5 ran anyway, comparing values that could not possibly be out of order. Bubble sort as written has no way of noticing that it has finished early.

Add a boolean variable that is set to false before each pass and to true inside the if whenever an exchange happens. After each pass, print the pass number and whether any exchange occurred. Run the program and confirm from the output that passes 4 and 5 exchange nothing. Then say, in one sentence, how the program could use that information to stop early.

8.6.2 Selection Sort

Selection sort takes the opposite approach. Instead of nudging values along by repeated exchanges, it looks for the value that belongs in a given position and puts it there in one move.

Think of the array as two regions: a sorted region growing from the left, and an unsorted region occupying the rest. To extend the sorted region by one cell, find the smallest value in the unsorted region and exchange it with the first unsorted cell. Repeat until the unsorted region holds one element, which must already be the largest.

Finding the smallest is the method of section 8.4.2, applied to part of the array rather than all of it.

selection sort, ascending Input: an array a of n elements. Output: the same array with its elements in ascending order. Method:

1. Repeat steps 2 to 4 for i = 0, 1, 2, ..., n-2.
2.    Set min to i.
3.    Repeat for j = i+1, i+2, ..., n-1:
          if a[j] < a[min] then set min to j.
4.    Exchange a[i] and a[min].
5. Stop. The array is in ascending order.

Why it works: step 3 leaves min holding the subscript of the smallest element in the unsorted region, by the running-minimum argument of section 8.4.2. Step 4 moves that element to the front of the unsorted region, which is exactly where it belongs, since everything to its left is already smaller and settled. Each pass therefore enlarges the sorted region by one, correctly. Cost: exactly \(n(n-1)/2\) comparisons for \(n\) elements, whatever the arrangement — the search for the minimum cannot be shortened. But there is at most one exchange per pass, so at most \(n-1\) exchanges in all. The cost is \(O(n^2)\).

Diagram

Fig. 8.6-2 – three stacked strips of six cells. Strip 1: 29 13 48 7 35 21, the whole strip labelled ‘unsorted’, an arrow marking 7 at subscript 3 as the minimum, and a double-headed arrow showing the exchange with subscript 0. Strip 2: 7 13 48 29 35 21, cell 0 shaded and labelled ‘sorted region’, the rest labelled ‘unsorted’, minimum 13 already in place at subscript 1. Strip 3: 7 13 21 29 35 48, whole strip shaded and labelled ‘sorted’

sorting an array by selection sort Problem: The same six numbers are to be sorted into ascending order using selection sort. Display the array before and after, and also report how many exchanges the method performed. Input: none. Output: two labelled lines and a count.

// Sorts an array into ascending order by repeatedly selecting the smallest element.
class SelectionSort
{
    public static void main(String args[])
    {
        int a[] = {29, 13, 48, 7, 35, 21};
        int i, j, min, t;
        int moves = 0;

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

        for (i = 0; i < a.length - 1; i++)
        {
            min = i;
            for (j = i + 1; j < a.length; j++)
            {
                if (a[j] < a[min])
                {
                    min = j;
                }
            }

            if (min != i)
            {
                t = a[i];
                a[i] = a[min];
                a[min] = t;
                moves++;
            }
        }

        System.out.print("After  :");
        for (i = 0; i < a.length; i++)
        {
            System.out.print(" " + a[i]);
        }
        System.out.println();
        System.out.println("Exchanges made : " + moves);
    }
}

Sample output:

Before : 29 13 48 7 35 21
After  : 7 13 21 29 35 48
Exchanges made : 2

Variable description:

[Table:] Table 8.17 – Variable description for the program SelectionSort [/Table] | Variable | Type | Purpose | |—|—|—| | a | int[] | the numbers to be sorted, rearranged in place | | i | int | first subscript of the unsorted region; counts the passes | | j | int | subscript scanned while looking for the smallest element | | min | int | subscript of the smallest element found so far in the unsorted region | | t | int | temporary store used while exchanging | | moves | int | counts the exchanges actually performed |

Notes: the test if (min != i) avoids exchanging an element with itself, which would be harmless but pointless — and would make the count meaningless. Only two real exchanges were needed for six values, against the eight that bubble sort performed on the same data. min holds a subscript, not a value; confusing the two is the commonest mistake in this algorithm, and writing if (a[j] < min) compares a mark with a position.

SelectionSort on 29, 13, 48, 7, 35, 21

Pass (i) Unsorted region scanned Smallest found min Exchange Array at end of pass
1 (i = 0) 13 48 7 35 21 7 3 a[0] with a[3] 7 13 48 29 35 21
2 (i = 1) 48 29 35 21 13 1 none needed 7 13 48 29 35 21
3 (i = 2) 29 35 21 21 5 a[2] with a[5] 7 13 21 29 35 48
4 (i = 3) 35 48 29 3 none needed 7 13 21 29 35 48
5 (i = 4) 48 35 4 none needed 7 13 21 29 35 48

Result: the output is 7 13 21 29 35 48 with Exchanges made : 2. Fifteen comparisons were still made, exactly as in bubble sort, but the data moved only twice — the trade selection sort offers is many comparisons in exchange for very little movement.

8.6.3 Insertion Sort

Insertion sort works the way most people arrange a hand of playing cards. The cards already held are kept in order; each new card is compared with them from the right, the larger ones are pushed along to make room, and the new card is dropped into the gap.

The array is again seen as a sorted region on the left and an unsorted region on the right, but the sorted region is built differently. Selection sort chooses which value goes into the next position; insertion sort takes whatever value comes next and works out where it goes.

The element being placed must be saved in a temporary variable first, because the shifting is about to overwrite its cell.

insertion sort, ascending Input: an array a of n elements. Output: the same array with its elements in ascending order. Method:

1. Repeat steps 2 to 5 for i = 1, 2, 3, ..., n-1.
2.    Set temp to a[i] and set j to i-1.
3.    Repeat step 4 while j >= 0 and a[j] > temp.
4.        Copy a[j] into a[j+1] and reduce j by 1.
5.    Copy temp into a[j+1].
6. Stop. The array is in ascending order.

Why it works: before pass i, the elements at subscripts 0 to i-1 are in order among themselves. Step 4 shifts rightwards every one of them that is greater than temp, which opens exactly one gap, at subscript j+1, with everything to its left no greater than temp and everything to its right greater. Placing temp there leaves subscripts 0 to i in order, so the sorted region has grown by one. Cost: with \(n\) the number of elements, the best case is data already in ascending order, needing only \(n-1\) comparisons and no shifting at all — \(O(n)\). The worst case is data in reverse order, needing \(n(n-1)/2\) comparisons and as many shifts — \(O(n^2)\). On the six values used here it makes 11 comparisons, against 15 for either of the other two methods.

Diagram

Fig. 8.6-3 – the array 7 13 29 48 35 21 with subscripts 0 to 5; cells 0 to 3 shaded as ‘already in order’; the value 35 at subscript 4 lifted out into a box labelled temp; a curved arrow showing 48 shifted from subscript 3 to subscript 4; a downward arrow dropping temp into the gap at subscript 3; the resulting strip 7 13 29 35 48 21 shown below

testing the element before testing the subscript What students write:

while (a[j] > temp && j >= 0)

What happens: the program stops with an ArrayIndexOutOfBoundsException whenever the value being placed is smaller than every element to its left. In that case j keeps decreasing until it reaches −1, and a[-1] is evaluated before the test j >= 0 gets its turn. The fix:

while (j >= 0 && a[j] > temp)

Test the subscript first. Java’s && operator does not evaluate its right-hand side once the left-hand side is false, so a[j] is never reached with j equal to −1. The order of the two conditions is not a matter of taste here; it is what keeps the second one safe.

sorting an array by insertion sort Problem: The same six numbers are to be sorted into ascending order using insertion sort. Display the array before and after. Input: none. Output: two labelled lines.

// Sorts an array into ascending order by inserting each element into the sorted part.
class InsertionSort
{
    public static void main(String args[])
    {
        int a[] = {29, 13, 48, 7, 35, 21};
        int i, j, temp;

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

        for (i = 1; i < a.length; i++)
        {
            temp = a[i];
            j = i - 1;
            while (j >= 0 && a[j] > temp)
            {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = temp;
        }

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

Sample output:

Before : 29 13 48 7 35 21
After  : 7 13 21 29 35 48

Variable description:

[Table:] Table 8.18 – Variable description for the program InsertionSort [/Table] | Variable | Type | Purpose | |—|—|—| | a | int[] | the numbers to be sorted, rearranged in place | | i | int | subscript of the element being placed; counts the passes | | j | int | subscript scanned leftwards through the sorted region | | temp | int | holds the element being placed while cells are shifted |

Notes: the outer loop starts at 1, not 0, because a sorted region of one element needs no work. After the while loop ends, j + 1 is the correct destination in both cases — whether the loop stopped because a smaller element was met or because j ran off the left end. Some textbooks avoid the j >= 0 test by storing a very large negative value in cell 0 as a stopper; that costs a cell and quietly fails on any data smaller than the value chosen, so the guarded test used here is the safer form.

InsertionSort on 29, 13, 48, 7, 35, 21

Pass (i) temp Elements shifted right Placed at subscript Array at end of pass
1 (i = 1) 13 29 0 13 29 48 7 35 21
2 (i = 2) 48 none 2 13 29 48 7 35 21
3 (i = 3) 7 48, 29, 13 0 7 13 29 48 35 21
4 (i = 4) 35 48 3 7 13 29 35 48 21
5 (i = 5) 21 48, 35, 29 2 7 13 21 29 35 48

Result: the array is sorted after 11 comparisons and 8 shifts. Pass 2 is the interesting one: 48 was already larger than everything to its left, so the while loop did not run at all and the element was simply written back where it came from. That is why nearly sorted data is cheap for this method — most passes end after one comparison.

8.6.4 Comparing the Three Sorting Techniques

All three techniques ran on the same six values and produced the same answer. The differences lie in the accounting.

One further property is worth naming. A sorting method is called stable if two equal values keep their original relative order. This matters when the data carries more than one field — sorting a list of students by marks, where two students have the same mark, a stable method leaves them in the order they were already in. Bubble sort and insertion sort only ever move a value past a strictly greater one, so both are stable. Selection sort exchanges distant elements and can jump one equal value over another, so it is not.

Table 8.19 – Bubble sort, selection sort and insertion sort

Feature Bubble sort Selection sort Insertion sort
Basic action exchange neighbours that are out of order find the smallest and put it in place shift the larger elements and insert
What is settled after pass k the k largest values, at the right-hand end the k smallest values, at the left-hand end the first k+1 elements, in order among themselves
Comparisons on the six values used here 15 15 11
Comparisons, worst case \(n(n-1)/2\) \(n(n-1)/2\) \(n(n-1)/2\)
Comparisons, best case \(n(n-1)/2\) \(n(n-1)/2\) \(n-1\)
Movement of data many exchanges; 8 on this data at most \(n-1\) exchanges; 2 on this data shifting, not exchanging; 8 shifts on this data
Effect of nearly sorted data none, unless the method is modified to stop early none large; the method becomes close to \(O(n)\)
Stable yes no yes
Cost \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) worst, \(O(n)\) best

Read the table as a set of trade-offs rather than a ranking. Selection sort is the one to choose when moving data is expensive and comparing it is cheap, since it moves each element at most once per pass. Insertion sort is the one to choose when the data is likely to be nearly in order already, because only then does its best case appear. Bubble sort is the simplest to write and the easiest to get right, and it is the natural place to start — but on this evidence it does the most work for the least reason.

The one thing all three share is the shape of their worst case. Each performs about \(n^2/2\) comparisons, so multiplying the data by 10 multiplies the work by roughly 100. That is what \(O(n^2)\) means in practice, and it is why sorting a genuinely large collection needs methods beyond this chapter.

Q4. Bubble sort, selection sort and insertion sort all leave the same numbers in the same final order. So what actually makes them three different methods?

A. What differs is the strategy, and therefore the work. Bubble sort compares neighbours and lets large values drift to the end, settling the largest values first. Selection sort searches the unsorted part for the smallest value and places it directly, settling the smallest values first and moving data very little. Insertion sort keeps the front of the array in order and slots each new element into it by shifting. On the same six values they needed 15, 15 and 11 comparisons and 8, 2 and 8 movements respectively — the same destination reached by three routes of different length.

Practical link: sorting a single dimensional array — file this under “Fundamental operations on arrays” in the work file. Write a program that reads n (with n between 2 and 20) and then n whole numbers into an array, sorts them into ascending order using selection sort, and displays the sorted array on one line together with the number of exchanges performed. Test it with the input 6 followed by 29, 13, 48, 7, 35, 21, and then with the unseen input 5 followed by 10, 20, 30, 40, 50 — state what the exchange count should be for data that is already sorted, and check that your program agrees.

8.7 Insertion, Deletion and Merging

Searching and sorting leave an array the same size. The three operations in this section change what the array holds — a value goes in, a value comes out, two lists become one — and each of them runs into the fact established in section 8.1: an array cannot grow.

The way round it is to separate two different numbers. The capacity of an array is how many cells it has, fixed by new. The number of elements actually in use is something the program keeps track of itself, in an ordinary int variable, usually called n. An array of capacity 10 holding 6 values has four spare cells at the end, and those spare cells are what make insertion possible at all.

From here on, n means the count of elements in use, and the elements occupy subscripts 0 to n - 1. Everything from n to capacity - 1 is spare.

8.7.1 Inserting an Element at a Given Position

To put a new value at subscript pos, the cell at pos must first be emptied — and emptying it means moving everything from pos onwards one place to the right.

The direction of that movement is the whole difficulty. Copying a[pos] into a[pos + 1] first would destroy the value already in a[pos + 1] before it had been saved, and the same value would then be copied all the way along. The shifting must therefore begin at the last element and work backwards, so that every cell is copied into a cell whose contents are no longer needed.

inserting an element into an array at a given position Input: an array a with capacity c, holding n elements at subscripts 0 to n-1; a value ele; a position pos in the range 0 to n. Output: the array holding n+1 elements, with ele at subscript pos and the previous order otherwise preserved. Method:

1. If n = c then stop: there is no spare cell and the insertion is not possible.
2. Repeat step 3 for j = n-1, n-2, ..., pos.
3.    Copy a[j] into a[j+1].
4. Copy ele into a[pos].
5. Increase n by 1.

Why it works: step 3 is performed on decreasing values of j, so each element is copied into the cell just vacated by the element on its right — the first copy goes into the spare cell at subscript n, which held nothing in use. When the loop ends, subscripts pos+1 to n hold what used to be at pos to n-1, and the cell at pos may be overwritten without loss. Cost: with n elements in use, inserting at the front shifts all \(n\) of them, inserting at the end shifts none, and the average is about \(n/2\). The cost is \(O(n)\).

Diagram

Fig. 8.7-1 – a strip of ten cells, the first six holding 14, 27, 33, 46, 58, 61 and the last four drawn empty and labelled ‘spare capacity’; subscripts 0 to 9 beneath. Three curved arrows above the strip showing 61 moving from subscript 5 to 6, 58 from 4 to 5 and 46 from 3 to 4, numbered 1, 2, 3 to show the order of the copies; a downward arrow dropping the value 40 into the vacated cell at subscript 3

inserting a value into a sorted list at a stated position Problem: An array of capacity 10 holds six numbers in ascending order at subscripts 0 to 5. Insert the value 40 at subscript 3, keeping the order of the other elements, and display the list before and after. Input: none; the list, the value and the position are fixed in the program. Output: two labelled lines.

// Inserts a value at a stated position by shifting the later elements right.
class ArrayInsert
{
    public static void main(String args[])
    {
        int a[] = new int[10];
        int given[] = {14, 27, 33, 46, 58, 61};
        int n = given.length;
        int pos = 3;
        int ele = 40;
        int i, j;

        for (i = 0; i < n; i++)
        {
            a[i] = given[i];
        }

        System.out.print("Before (" + n + " elements) :");
        for (i = 0; i < n; i++)
        {
            System.out.print(" " + a[i]);
        }
        System.out.println();

        if (n < a.length)
        {
            for (j = n - 1; j >= pos; j--)
            {
                a[j + 1] = a[j];
            }
            a[pos] = ele;
            n++;
        }
        else
        {
            System.out.println("No spare cell: insertion not possible.");
        }

        System.out.print("After  (" + n + " elements) :");
        for (i = 0; i < n; i++)
        {
            System.out.print(" " + a[i]);
        }
        System.out.println();
    }
}

Sample output:

Before (6 elements) : 14 27 33 46 58 61
After  (7 elements) : 14 27 33 40 46 58 61

Variable description:

[Table:] Table 8.20 – Variable description for the program ArrayInsert [/Table] | Variable | Type | Purpose | |—|—|—| | a | int[] | working array of capacity 10 | | given | int[] | the six values the list starts with | | n | int | number of elements in use | | pos | int | subscript at which the new value is to be placed | | ele | int | the value being inserted | | i | int | subscript used in the copying and display loops | | j | int | subscript used while shifting elements to the right |

Notes: the array is created with new int[10] and then filled from a shorter list, precisely so that spare cells exist; a program that used int a[] = {14, 27, 33, 46, 58, 61}; would have a capacity of exactly 6 and no room to insert anything. The display loops run to n, not to a.length, because the spare cells hold defaults that are not part of the list. The guard n < a.length is not decoration — without it the shifting loop would write to a[10] and stop the program.

shifting from the wrong end What students write:

for (j = pos; j < n; j++)
{
    a[j + 1] = a[j];
}

What happens: no error is reported, but the list is ruined. The first copy overwrites a[pos + 1] before its value has been moved anywhere, so that value is lost and the value from a[pos] is then copied into every following cell. For the list above, inserting at subscript 3 would give 14 27 33 40 46 46 46 46. The fix: shift backwards, from the last element down to pos:

for (j = n - 1; j >= pos; j--)
{
    a[j + 1] = a[j];
}

Each copy then lands in a cell whose old contents have already been moved to safety.

the shifting loop of ArrayInsert, with n = 6 and pos = 3

Pass j Copy performed Array (subscripts 0 to 6) after the copy
start – – 14 27 33 46 58 61 0
1 5 a[6] = a[5] 14 27 33 46 58 61 61
2 4 a[5] = a[4] 14 27 33 46 58 58 61
3 3 a[4] = a[3] 14 27 33 46 46 58 61
after loop 2 a[3] = 40 14 27 33 40 46 58 61

Result: seven elements in ascending order. Notice that a value appears twice at the end of each pass — that is the copy in transit, and it is overwritten on the next pass. The last such duplicate, at subscript 3, is removed by the assignment of the new value.

8.7.2 Deleting an Element from a Given Position

Deletion is the same movement in reverse. The element at pos is removed by copying every later element one place to the left, over the gap, and then reducing n by 1.

Here the copying must run forwards, from pos upwards, for the same reason insertion runs backwards: each cell is copied into one whose contents are no longer needed.

deleting the element at a given position Input: an array a holding n elements at subscripts 0 to n-1, and a position pos in the range 0 to n-1. Output: the array holding n-1 elements, the one at pos removed and the order of the rest preserved. Method:

1. Repeat step 2 for j = pos, pos+1, ..., n-2.
2.    Copy a[j+1] into a[j].
3. Reduce n by 1.

Why it works: after step 2 has run for every j from pos to n-2, the element that was at subscript j+1 sits at subscript j for each of those positions, so the value at pos has been covered over and everything after it has moved down by one. Reducing n puts the last cell out of use. Cost: deleting the first element shifts \(n-1\) elements, deleting the last shifts none. The cost is \(O(n)\).

Diagram

Fig. 8.7-2 – a strip of five cells holding 8, 19, 23, 31, 45 with subscripts 0 to 4; the cell at subscript 1 marked with a cross and labelled ‘to be deleted’; three curved arrows showing 23 moving from subscript 2 to 1, 31 from 3 to 2 and 45 from 4 to 3, numbered 1, 2, 3; the cell at subscript 4 shown shaded and labelled ‘no longer in use, though the value 45 is still there’

deleting an element at a stated position Problem: An array of capacity 10 holds five numbers at subscripts 0 to 4. Delete the element at subscript 1, display the list before and after, and also display what remains in the cell that has gone out of use. Input: none. Output: four lines.

// Deletes the element at a stated position by shifting the later elements left.
class ArrayDelete
{
    public static void main(String args[])
    {
        int a[] = new int[10];
        int given[] = {8, 19, 23, 31, 45};
        int n = given.length;
        int pos = 1;
        int i, j;

        for (i = 0; i < n; i++)
        {
            a[i] = given[i];
        }

        System.out.print("Before (" + n + " elements) :");
        for (i = 0; i < n; i++)
        {
            System.out.print(" " + a[i]);
        }
        System.out.println();
        System.out.println("Deleting subscript " + pos + ", which holds " + a[pos]);

        for (j = pos; j < n - 1; j++)
        {
            a[j] = a[j + 1];
        }
        n--;

        System.out.print("After  (" + n + " elements) :");
        for (i = 0; i < n; i++)
        {
            System.out.print(" " + a[i]);
        }
        System.out.println();
        System.out.println("Cell at subscript " + n + " still holds " + a[n]);
    }
}

Sample output:

Before (5 elements) : 8 19 23 31 45
Deleting subscript 1, which holds 19
After  (4 elements) : 8 23 31 45
Cell at subscript 4 still holds 45

Variable description:

[Table:] Table 8.21 – Variable description for the program ArrayDelete [/Table] | Variable | Type | Purpose | |—|—|—| | a | int[] | working array of capacity 10 | | given | int[] | the five values the list starts with | | n | int | number of elements in use | | pos | int | subscript of the element being deleted | | i | int | subscript used in the copying and display loops | | j | int | subscript used while shifting elements to the left |

Notes: the last line of output makes an important point. Nothing was erased. The value 45 is still sitting at subscript 4, and it became invisible only because n was reduced and every loop now stops before reaching it. Deletion from an array is a change of bookkeeping backed up by a shift, not an act of removal. The loop bound is j < n - 1 and not j < n, since the body reads a[j + 1].

To delete a value rather than a position, search for it first — linear search from section 8.5.1 returns exactly the subscript this algorithm needs, and returns −1 when there is nothing to delete.

why insertion and deletion cost what they do Let \(n\) be the number of elements in use. Reaching any single cell costs the same tiny amount whatever its position, but insertion and deletion are not single-cell operations: they move every element beyond the point of change, up to \(n\) of them, one cell each. Both are therefore \(O(n)\), and both are cheapest at the end of the list and dearest at the front.

8.7.3 Merging Two Sorted Arrays

Merging combines two arrays that are already sorted into a third array that is also sorted. If the first holds m elements and the second holds p, the result holds exactly m + p.

The method rests on one observation. If both lists are in ascending order, then the smallest value not yet used must be at the front of one list or the other — it cannot be hiding further along, because everything further along is larger. So it is enough to compare the two front elements, take the smaller, and move that list’s marker forward by one.

Eventually one list runs out. Whatever is left in the other is already in order and larger than everything taken so far, so it is simply copied across.

merging two sorted arrays Input: an array a of m elements and an array b of p elements, both in ascending order. Output: an array c of m+p elements containing all of them, in ascending order. Method:

1. Set i to 0, j to 0 and k to 0.
2. Repeat steps 3 to 5 while i < m and j < p.
3.    If a[i] <= b[j] then copy a[i] into c[k] and increase i by 1.
4.    Otherwise copy b[j] into c[k] and increase j by 1.
5.    Increase k by 1.
6. While i < m, copy a[i] into c[k], increasing i and k by 1 each time.
7. While j < p, copy b[j] into c[k], increasing j and k by 1 each time.

Why it works: at every stage the elements already placed in c are the smallest ones from both lists, in order, and the next element to place is the smaller of the two still at the front — that is exactly what steps 3 and 4 choose. Steps 6 and 7 handle the remainder of whichever list is not exhausted; only one of them can run. Cost: each element is examined and copied exactly once, so the work is proportional to \(m + p\) and the cost is \(O(m + p)\), where \(m\) and \(p\) are the numbers of elements in the two arrays.

Diagram

Fig. 8.7-3 – two source strips one above the other, the first holding 4, 11, 19, 26 and the second holding 7, 9, 22, 30, 41, each with a marker labelled i and j at its current position; a third, longer strip below labelled c with a marker labelled k. Arrows from the two markers meeting at a comparison symbol, and a single arrow from the comparison into the cell at k, showing that one value is copied per step and only one marker advances

merging two sorted arrays Problem: Two arrays hold numbers in ascending order — one with four elements and one with five. Produce a third array containing all nine in ascending order, without sorting it afterwards, and display all three arrays. Input: none. Output: three labelled lines.

// Merges two ascending arrays into a third, keeping the order.
class ArrayMerge
{
    public static void main(String args[])
    {
        int a[] = {4, 11, 19, 26};
        int b[] = {7, 9, 22, 30, 41};
        int c[] = new int[a.length + b.length];
        int i = 0;
        int j = 0;
        int k = 0;
        int p;

        System.out.print("First  :");
        for (p = 0; p < a.length; p++)
        {
            System.out.print(" " + a[p]);
        }
        System.out.println();

        System.out.print("Second :");
        for (p = 0; p < b.length; p++)
        {
            System.out.print(" " + b[p]);
        }
        System.out.println();

        while (i < a.length && j < b.length)
        {
            if (a[i] <= b[j])
            {
                c[k] = a[i];
                i++;
            }
            else
            {
                c[k] = b[j];
                j++;
            }
            k++;
        }

        while (i < a.length)
        {
            c[k] = a[i];
            i++;
            k++;
        }

        while (j < b.length)
        {
            c[k] = b[j];
            j++;
            k++;
        }

        System.out.print("Merged :");
        for (p = 0; p < c.length; p++)
        {
            System.out.print(" " + c[p]);
        }
        System.out.println();
    }
}

Sample output:

First  : 4 11 19 26
Second : 7 9 22 30 41
Merged : 4 7 9 11 19 22 26 30 41

Variable description:

[Table:] Table 8.22 – Variable description for the program ArrayMerge [/Table] | Variable | Type | Purpose | |—|—|—| | a | int[] | first sorted array | | b | int[] | second sorted array | | c | int[] | merged result, of size a.length + b.length | | i | int | subscript of the next unused element of a | | j | int | subscript of the next unused element of b | | k | int | subscript of the next free cell of c | | p | int | subscript used by the display loops only |

Notes: three separate markers are needed, and k advances on every copy while i and j advance one at a time — mixing them up is the usual source of trouble here. The comparison is <= rather than <, so that when the two lists hold equal values the one from a is taken first; this keeps the merge stable, in the sense of section 8.6.4. A separate variable p is used for the display loops so that i and j still hold 0 when the merging begins.

ArrayMerge on 4, 11, 19, 26 and 7, 9, 22, 30, 41

Step i j a[i] b[j] Value copied to c[k] k after
1 0 0 4 7 4, from a 1
2 1 0 11 7 7, from b 2
3 1 1 11 9 9, from b 3
4 1 2 11 22 11, from a 4
5 2 2 19 22 19, from a 5
6 3 2 26 22 22, from b 6
7 3 3 26 30 26, from a 7
tail 4 3 – 30, 41 30 then 41, from b 9

Result: c holds 4 7 9 11 19 22 26 30 41. After step 7 the marker i reached 4, which is a.length, so the first while loop ended and the second array’s remaining two elements were copied straight across without any further comparison.

forgetting the leftovers What students write:

while (i < a.length && j < b.length)
{
    // compare and copy
}
// nothing after the loop

What happens: the merged array is short of values, and the missing ones are silently replaced by zeros, since the unused cells of c still hold their default. For the data above the result would be 4 7 9 11 19 22 26 0 0. The fix: follow the main loop with the two copying loops of steps 6 and 7. Only one of them can actually run, but which one is not known in advance, so both must be written.

A last observation ties this section to the previous one. The nine merged values could also have been obtained by copying both arrays into one and sorting it — but that would cost \(O(n^2)\) with the methods of section 8.6, while merging costs \(O(m + p)\). When the order is already there, throwing it away and rebuilding it is the expensive way round.

Change the value 22 in the second array of ArrayMerge to 26, so that the same value now appears in both arrays, and run the program. Check that the merged list contains 26 twice, and work out from the <= in the comparison which of the two copies came from the first array.

8.8 The Double Dimensional Array

A single dimensional array is a list. A great deal of ordinary data is not a list but a table: the marks of forty students in five subjects, the fares between six stations, the rainfall of twelve months over ten years. Such data has two directions, and it needs two numbers to pick out one value — which row, and which column.

An array whose elements are selected by two subscripts is called a double dimensional array, and the table it represents is usually called a matrix. Almost everything already learnt carries over: the subscripts still start at 0, the elements are still all of one type, and the size is still fixed at creation.

NoteDefinition

A double dimensional array is a collection of elements of the same type arranged in rows and columns, in which each element is selected by two integer subscripts — the first giving its row and the second its column.

8.8.1 Creating a Double Dimensional Array

The declaration carries two pairs of brackets, and new is given two sizes:

int m[][] = new int[3][4];

This creates a table of 3 rows and 4 columns — twelve cells in all. Row subscripts run from 0 to 2 and column subscripts from 0 to 3, so the twelve elements are m[0][0] to m[2][3]. The first subscript is always the row and the second always the column, and the two are not interchangeable: m[2][3] exists in this array while m[3][2] does not.

Diagram

Fig. 8.8-1 – a grid of 3 rows and 4 columns; column subscripts 0, 1, 2, 3 written above the columns and row subscripts 0, 1, 2 written to the left of the rows; each cell labelled with its full name m[0][0], m[0][1] … m[2][3]; the cell m[2][3] outlined and labelled ‘row 2, column 3 — the last element’

Values may also be listed at the point of declaration, one inner pair of braces per row:

int m[][] = {{5, 8, 2, 9}, {7, 1, 6, 3}, {4, 0, 8, 2}};

The number of inner groups fixes the number of rows, and the number of values in each group fixes the number of columns. Written out over three lines, as it usually is, the code takes the shape of the table itself.

Any element type may be used, and the pattern of the declaration never changes.

Table 8.23 – Creating a double dimensional array of 3 rows and 4 columns, for several element types

To hold Written as
whole numbers int m[][] = new int[3][4];
real numbers double m[][] = new double[3][4];
single characters char ch[][] = new char[3][4];
truth values boolean flag[][] = new boolean[3][4];
pieces of text String name[][] = new String[3][4];

The default values are the ones listed in Table 8.2, so a new int matrix begins full of zeros and a new String matrix begins full of null.

How many rows, how many columns

Both counts are available from the array itself, but they are asked for differently:

int rows = m.length;
int cols = m[0].length;

m.length gives the number of rows. m[0].length gives the number of columns in row 0. The wording is deliberate.

In Java a double dimensional array is really an array of arrays: m is an array of 3 elements, and each of those elements is itself an array of 4 int values. That is why the number of columns is a property of a row rather than of the whole table, and why Java is able to build tables whose rows have different lengths. For the rectangular tables in this chapter every row has the same length, so m[0].length is the number of columns of the whole matrix.

asking the wrong array for the number of columns What students write:

for (j = 0; j < m.length; j++)

What happens: the loop uses the number of rows as the column bound. For a 3 by 4 matrix it visits only columns 0, 1 and 2, so the last column is silently missed; for a 4 by 3 matrix it runs to column 3, which does not exist, and the program stops with an ArrayIndexOutOfBoundsException. The fix:

for (j = 0; j < m[0].length; j++)

Use m.length for rows and m[0].length for columns. The mistake is invisible in a square matrix, where the two happen to be equal — which is exactly why it survives long enough to cause trouble later.

Q. In new int[5][3], which number is the count of rows?

A. The first, 5. The array has 5 rows of 3 columns each, so the subscripts run m[0][0] to m[4][2]. Reading the two sizes in the wrong order produces a table of the right total size but the wrong shape.

8.8.2 Storing and Displaying the Elements

One subscript needs one loop; two subscripts need two, one inside the other. The outer loop chooses a row and the inner loop runs across that row’s columns, so the elements are visited row by row.

for (i = 0; i < rows; i++)
{
    for (j = 0; j < cols; j++)
    {
        // work with m[i][j]
    }
}

Displaying a matrix uses the same pair of loops with one addition: a println() at the end of each row, after the inner loop has finished, so that the next row starts on a new line. Leaving it out prints the entire table as one long line — a mistake that is easy to see and easy to correct.

reading and displaying a matrix Problem: Read the number of rows and columns, then read that many whole numbers into a double dimensional array, and display them in the shape of a table. Input: two whole numbers giving the size, followed by the elements, typed at the keyboard. Output: the matrix, one row to a line.

// Reads a matrix from the keyboard and displays it in rows and columns.
import java.util.Scanner;

class MatrixInput
{
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        int i, j;

        System.out.print("Rows    : ");
        int rows = in.nextInt();
        System.out.print("Columns : ");
        int cols = in.nextInt();

        int m[][] = new int[rows][cols];

        System.out.println("Enter " + (rows * cols) + " elements:");
        for (i = 0; i < rows; i++)
        {
            for (j = 0; j < cols; j++)
            {
                m[i][j] = in.nextInt();
            }
        }

        System.out.println("The matrix is:");
        for (i = 0; i < rows; i++)
        {
            for (j = 0; j < cols; j++)
            {
                System.out.print(m[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

Sample output, for 3 rows and 4 columns and the twelve values shown (the typed values appear in the transcript as they are echoed by the terminal):

Rows    : 3
Columns : 4
Enter 12 elements:
5 8 2 9
7 1 6 3
4 0 8 2
The matrix is:
5   8   2   9
7   1   6   3
4   0   8   2

Variable description:

[Table:] Table 8.24 – Variable description for the program MatrixInput [/Table] | Variable | Type | Purpose | |—|—|—| | in | Scanner | reads the size and the elements | | rows | int | number of rows | | cols | int | number of columns | | m | int[][] | the matrix | | i | int | row subscript | | j | int | column subscript |

Notes: the array cannot be created until both sizes are known, so new int[rows][cols] comes after the two reads. The twelve values may be typed on three lines or on one, since nextInt() treats every run of spaces and line breaks alike; typing them in the shape of the table is a courtesy to the person entering them, not a requirement of the program. Each element is followed by a tab so that the columns line up, and System.out.println() after the inner loop ends the row.

8.8.3 Working Row-wise and Column-wise

The two loops can be nested either way round, and swapping them changes what the traversal means.

With i outside and j inside, the elements are visited across row 0, then across row 1, and so on. Reverse the nesting — j outside and i inside — and the elements are visited down column 0, then down column 1. The array is unchanged; only the order of visiting differs, and that order is what makes a row total or a column total possible.

Diagram

Fig. 8.8-2 – two copies of the same 3 by 4 grid. The left copy has a snaking arrow running left to right across row 0, then row 1, then row 2, labelled ‘row-wise: i outside, j inside’. The right copy has a snaking arrow running top to bottom down column 0, then column 1, then 2, then 3, labelled ‘column-wise: j outside, i inside’; the cells are numbered 1 to 12 in each copy to show the differing order of visits

To total a row, the accumulator must be reset at the start of each row and reported at its end — that is, inside the outer loop but outside the inner one. Placing it in the wrong loop is the standard mistake: created before both loops, it accumulates the whole table; created inside the inner loop, it never holds more than one element.

row totals and column totals of a matrix Problem: A matrix of 3 rows and 4 columns is fixed in the program. Display the matrix, then the total of each row, and then the total of each column. Input: none. Output: the matrix followed by the two sets of totals.

// Displays a matrix and the total of each of its rows and columns.
class RowColumnSum
{
    public static void main(String args[])
    {
        int m[][] = {{12, 5, 9, 3},
                     {7, 14, 2, 8},
                     {6, 1, 11, 4}};
        int rows = m.length;
        int cols = m[0].length;
        int i, j, sum;

        System.out.println("The matrix is:");
        for (i = 0; i < rows; i++)
        {
            for (j = 0; j < cols; j++)
            {
                System.out.print(m[i][j] + "\t");
            }
            System.out.println();
        }

        for (i = 0; i < rows; i++)
        {
            sum = 0;
            for (j = 0; j < cols; j++)
            {
                sum = sum + m[i][j];
            }
            System.out.println("Total of row " + i + "    : " + sum);
        }

        for (j = 0; j < cols; j++)
        {
            sum = 0;
            for (i = 0; i < rows; i++)
            {
                sum = sum + m[i][j];
            }
            System.out.println("Total of column " + j + " : " + sum);
        }
    }
}

Sample output:

The matrix is:
12  5   9   3
7   14  2   8
6   1   11  4
Total of row 0    : 29
Total of row 1    : 31
Total of row 2    : 22
Total of column 0 : 25
Total of column 1 : 20
Total of column 2 : 22
Total of column 3 : 15

Variable description:

[Table:] Table 8.25 – Variable description for the program RowColumnSum [/Table] | Variable | Type | Purpose | |—|—|—| | m | int[][] | the matrix, 3 rows by 4 columns | | rows | int | number of rows, taken from m.length | | cols | int | number of columns, taken from m[0].length | | i | int | row subscript | | j | int | column subscript | | sum | int | running total of the row or column being processed |

Notes: the two totalling loops differ only in which subscript is on the outside, and that single difference turns row totals into column totals. In both, sum is set to 0 immediately inside the outer loop, so each row or column starts afresh. As a check on the arithmetic, the three row totals and the four column totals both add up to 82 — every element has been counted exactly once either way.

the cost of a matrix traversal Let \(r\) be the number of rows and \(c\) the number of columns, so the matrix holds \(r \times c\) elements. A pair of nested loops visits each element once, so the work is proportional to \(r \times c\). For a square matrix of order \(n\) that is \(n^2\) elements and a cost of \(O(n^2)\) — a nested loop over a matrix is not expensive because it is nested, but because there is that much data.

8.8.4 Square Matrices and Their Diagonals

A matrix with as many rows as columns is a square matrix, and the number of rows is called its order. A square matrix of order 4 holds 16 elements, subscripted [0][0] to [3][3].

Only a square matrix has diagonals, and it has two.

The principal diagonal runs from the top left corner to the bottom right. An element lies on it when its row subscript equals its column subscript, so its members are exactly those cells m[i][j] for which i == j. It is also called the left or leading diagonal.

The secondary diagonal runs from the top right corner to the bottom left. For a matrix of order n, an element lies on it when i + j == n - 1. It is also called the right or trailing diagonal.

NoteDefinition

In a square matrix of order n, an element m[i][j] lies on the principal diagonal when i = j, and on the secondary diagonal when i + j = n − 1.

Both conditions are worth checking against the corners. In a matrix of order 4, i + j == 3 selects m[0][3], m[1][2], m[2][1] and m[3][0] — the top right cell, the bottom left cell, and the two between them. When the order is odd the centre element satisfies both conditions and lies on both diagonals, which is something to allow for when the two sums are being added together.

Diagram

Fig. 8.8-3 – a 4 by 4 grid with row subscripts 0 to 3 on the left and column subscripts 0 to 3 above. The four cells where i equals j are shaded in one tone and labelled ‘principal diagonal, i = j’; the four cells where i + j equals 3 are shaded in a second tone and labelled ‘secondary diagonal, i + j = n − 1’; each shaded cell annotated with its subscript pair

the two diagonals of a square matrix Problem: A square matrix of order 4 is fixed in the program. Display the matrix, list the elements of each diagonal, and display the total of each. Input: none. Output: the matrix followed by the two diagonals and their totals.

// Displays a square matrix and the elements and totals of its two diagonals.
class DiagonalSum
{
    public static void main(String args[])
    {
        int m[][] = {{3, 7, 1, 5},
                     {9, 2, 8, 4},
                     {6, 0, 11, 2},
                     {1, 5, 3, 7}};
        int n = m.length;
        int left = 0;
        int right = 0;
        int i, j;

        System.out.println("The matrix is:");
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
            {
                System.out.print(m[i][j] + "\t");
            }
            System.out.println();
        }

        System.out.print("Principal diagonal :");
        for (i = 0; i < n; i++)
        {
            System.out.print(" " + m[i][i]);
            left = left + m[i][i];
        }
        System.out.println();

        System.out.print("Secondary diagonal :");
        for (i = 0; i < n; i++)
        {
            System.out.print(" " + m[i][n - 1 - i]);
            right = right + m[i][n - 1 - i];
        }
        System.out.println();

        System.out.println("Sum of the principal diagonal : " + left);
        System.out.println("Sum of the secondary diagonal : " + right);
    }
}

Sample output:

The matrix is:
3   7   1   5
9   2   8   4
6   0   11  2
1   5   3   7
Principal diagonal : 3 2 11 7
Secondary diagonal : 5 8 0 1
Sum of the principal diagonal : 23
Sum of the secondary diagonal : 14

Variable description:

[Table:] Table 8.26 – Variable description for the program DiagonalSum [/Table] | Variable | Type | Purpose | |—|—|—| | m | int[][] | the square matrix, of order 4 | | n | int | the order of the matrix, taken from m.length | | left | int | running total of the principal diagonal | | right | int | running total of the secondary diagonal | | i | int | subscript of the diagonal element being visited | | j | int | column subscript, used only while displaying the matrix |

Notes: the diagonals need one loop, not two. Once the row is chosen the column is decided — i for the principal diagonal and n - 1 - i for the secondary — so a single counter reaches all n elements. The alternative is a full nested traversal with an if (i == j) inside it, which gives the same answer while examining all \(n^2\) cells in order to use \(n\) of them.

Symmetry

A square matrix is called symmetric when it is unchanged by reflecting it in its principal diagonal — that is, when m[i][j] equals m[j][i] for every pair of subscripts. The matrix above is not symmetric: m[0][1] is 7 while m[1][0] is 9. Testing for symmetry needs a full traversal and a boolean that starts at true and is set to false the moment any mismatched pair is met.

Change one value in the matrix of DiagonalSum so that the principal and secondary diagonals have equal totals, and predict the two new output lines before running the program. Then reduce the matrix to order 3 by removing a row and a column, and work out by hand which single element now lies on both diagonals at once.

8.9 Address Calculation in Arrays

Section 8.1 claimed that reaching m[499] costs no more than reaching m[1]. This section shows why, and in doing so explains how a table of rows and columns is stored in a memory that has neither.

Memory is a long sequence of numbered storage locations, each holding one byte, and the number of a location is its address. An array occupies a contiguous block of these locations — one element after another, with nothing in between. Two facts follow, and everything in this section comes from them: the position of the first element is known, and every element takes the same number of bytes.

The address of the first element of the block is called the base address, usually written \(B\). The number of bytes occupied by one element is the size of the element type, usually written \(w\).

Table 8.27 – Storage occupied by one element, for the Java primitive types

Element type Bytes occupied
byte 1
short 2
char 2
int 4
float 4
long 8
double 8

These sizes are fixed by the Java language and do not vary from one machine to another, which is one of the reasons a Java program behaves identically everywhere.

8.9.1 Address of an Element in a Single Dimensional Array

Consider an array of int, so \(w = 4\), whose base address \(B\) is 2000. The first element occupies the four bytes beginning at 2000, the second the four beginning at 2004, the third the four beginning at 2008. The element at subscript i therefore begins \(4 \times i\) bytes after the start of the block.

\[\text{Address of } a[i] = B + w \times (i - LB)\]

Here \(LB\) is the lower bound — the smallest legal subscript. In Java the lower bound is always 0, which reduces the formula to

\[\text{Address of } a[i] = B + w \times i\]

The subtraction of \(LB\) is kept in the general form because several other languages allow arrays to be subscripted from 1, or from any value the programmer chooses. What the formula really computes is how many elements lie before this one, and multiplying that count by the element size gives the distance in bytes.

For the array above, the element at subscript 5 begins at \(2000 + 4 \times 5 = 2020\), and the element at subscript 499 begins at \(2000 + 4 \times 499 = 3996\).

Diagram

Fig. 8.9-1 – a horizontal block of memory divided into equal cells of four bytes each; the leftmost cell labelled a[0] with the address 2000 written beneath it, the next cells labelled a[1] at 2004, a[2] at 2008, a[3] at 2012; a bracket spanning from the start of the block to the start of a[3] labelled ‘3 elements × 4 bytes = 12’; the general formula B + w × i shown alongside

Notice what the formula does not do. It does not count along the array, and it does not look at any element on the way. It performs one multiplication and one addition, and the size of the subscript makes no difference to that work.

why array access is constant time Let \(n\) be the number of elements. Reaching a[i] costs one multiplication and one addition, whatever \(i\) and \(n\) may be. The work does not grow with the amount of data at all, so the cost is \(O(1)\) — described as constant time. It is this property, and not any property of the data, that makes binary search possible on an array, since binary search must jump straight to a middle element.

Q2. A program can reach the 500th element of an array just as quickly as the 2nd. How is that possible when the 500th is so much further away?

A. Because the position is calculated, not travelled to. The elements sit in one contiguous block and every element occupies the same number of bytes, so the address of a[i] is simply \(B + w \times i\) — the start of the block plus the size of one element multiplied by the number of elements in front of it. Computing \(2000 + 4 \times 499\) takes exactly as long as computing \(2000 + 4 \times 1\). Nothing is stepped over, and no element between the two is so much as examined.

Q. Why does every element of an array have to be of the same type?

A. Because the address formula multiplies by a single element size. If the cells had different sizes, the position of the element at subscript i could not be worked out without adding up the sizes of all the elements before it — which would mean looking at them, and access would stop being constant time.

8.9.2 Row Major Address Calculation

Memory has one dimension; a matrix has two. Storing a matrix therefore means choosing an order in which to lay its elements out in a single line, and there are two standard choices.

Row major order stores the matrix one complete row at a time: the whole of row 0, then the whole of row 1, and so on. It is the order in which we read a printed page, and it is the order used by most languages.

For a matrix of \(R\) rows and \(C\) columns, how many elements come before m[i][j]? Every row before row i is complete, contributing \(i \times C\) elements, and within row i there are j elements to the left. So

\[\text{Address of } m[i][j] = B + w \times \left[ (i - LBR) \times C + (j - LBC) \right]\]

where \(LBR\) and \(LBC\) are the lower bounds of the row and column subscripts and \(C\) is the number of columns. With Java’s lower bounds of 0 this becomes

\[\text{Address of } m[i][j] = B + w \times (i \times C + j)\]

Diagram

Fig. 8.9-2 – a 3 by 4 grid at the top with cells labelled m[0][0] to m[2][3]; below it a single long strip of twelve memory cells; arrows carrying the grid cells into the strip in the order m[0][0], m[0][1], m[0][2], m[0][3], m[1][0] … m[2][3]; the strip annotated ‘row 0’, ‘row 1’, ‘row 2’ in three brackets, and the leftmost cell marked with the base address B

Take an int matrix of 3 rows and 4 columns with base address 1000, so \(w = 4\) and \(C = 4\).

  • m[0][0] lies at \(1000 + 4 \times (0 \times 4 + 0) = 1000\).
  • m[1][2] lies at \(1000 + 4 \times (1 \times 4 + 2) = 1000 + 24 = 1024\).
  • m[2][3] lies at \(1000 + 4 \times (2 \times 4 + 3) = 1000 + 44 = 1044\), which is the last of the twelve elements.

The number of columns appears in the formula and the number of rows does not. That is not an oversight: to skip over a complete row you need to know how long a row is, and a row is \(C\) elements long. How many rows exist below is irrelevant to how far you must travel.

When the subscripts do not start at zero

Questions are often set on arrays whose subscripts begin somewhere other than 0, and the general form handles them without modification. Suppose A[5][1] is the first element of an array declared as A[5...10][1...8], stored in row major order with a base address of 1500 and 2 bytes per element. Then

  • the number of rows is \(10 - 5 + 1 = 6\) and the number of columns is \(C = 8 - 1 + 1 = 8\);
  • the address of A[8][5] is \(1500 + 2 \times \left[ (8 - 5) \times 8 + (5 - 1) \right] = 1500 + 2 \times 28 = 1556\).

Work the two subtractions first, and the rest is arithmetic. The commonest slip is forgetting to subtract the lower bounds, which shifts every answer by a fixed amount.

8.9.3 Column Major Address Calculation

Column major order makes the opposite choice: the whole of column 0 is stored first, then the whole of column 1, and so on. Fortran uses this order, and it appears in numerical libraries descended from it.

The reasoning is the mirror image. Every column before column j is complete, contributing \(j \times R\) elements, and within column j there are i elements above. So

\[\text{Address of } m[i][j] = B + w \times \left[ (j - LBC) \times R + (i - LBR) \right]\]

where \(R\) is the number of rows. With lower bounds of 0,

\[\text{Address of } m[i][j] = B + w \times (j \times R + i)\]

Now it is the number of rows that appears, for the same reason as before — a column is \(R\) elements long.

Diagram

Fig. 8.9-3 – the same 3 by 4 grid at the top with cells labelled m[0][0] to m[2][3]; below it a single long strip of twelve memory cells; arrows carrying the grid cells into the strip in the order m[0][0], m[1][0], m[2][0], m[0][1], m[1][1] … m[2][3]; the strip annotated ‘column 0’, ‘column 1’, ‘column 2’, ‘column 3’ in four brackets, and the leftmost cell marked with the base address B

For the same int matrix of 3 rows and 4 columns with base address 1000, and now \(R = 3\):

  • m[1][2] lies at \(1000 + 4 \times (2 \times 3 + 1) = 1000 + 28 = 1028\), against 1024 in row major order.
  • m[2][3] lies at \(1000 + 4 \times (3 \times 3 + 2) = 1000 + 44 = 1044\) — the same address as before, because the last element is last in either order.

For the earlier example A[5...10][1...8] with a base address of 1500 and 2 bytes per element, the address of A[8][5] in column major order is \(1500 + 2 \times \left[ (5 - 1) \times 6 + (8 - 5) \right] = 1500 + 2 \times 27 = 1554\).

The full picture is easiest to see side by side. The table below gives the offset of each element of a 3 by 4 matrix — that is, the number of elements stored before it — under both orders.

Table 8.28 – Offset of each element of a 3 by 4 matrix, in row major and column major order

Element Offset, row major Offset, column major
m[0][0] 0 0
m[0][1] 1 3
m[0][2] 2 6
m[0][3] 3 9
m[1][0] 4 1
m[1][1] 5 4
m[1][2] 6 7
m[1][3] 7 10
m[2][0] 8 2
m[2][1] 9 5
m[2][2] 10 8
m[2][3] 11 11

Every element appears exactly once in each column of the table, and the offsets 0 to 11 are used exactly once each. The two orders store the same data in the same space; they disagree only about which element goes where.

Table 8.29 – Row major order compared with column major order

Feature Row major order Column major order
Order of storage one complete row after another one complete column after another
Elements before m[i][j] \(i \times C + j\) \(j \times R + i\)
Which size appears in the formula the number of columns, \(C\) the number of rows, \(R\)
Elements that end up adjacent in memory those next to each other in a row those above and below each other in a column
Traversal that runs straight through memory row-wise: i outside, j inside column-wise: j outside, i inside
Used by most languages, including C and Java’s own conventions Fortran and libraries derived from it

Q5. Memory is one long line of cells, yet a marks table has rows and columns. How does a two-dimensional table get laid out in a one-dimensional memory?

A. By choosing an order and then computing positions from it. Row major order writes the whole of row 0, then the whole of row 1, and so on; column major order writes column by column instead. Either way each element ends up at a definite distance from the start of the block, and a formula converts a pair of subscripts into that distance — \(i \times C + j\) elements for row major and \(j \times R + i\) for column major. The rows and columns are not stored anywhere; they exist only in the arithmetic that turns two subscripts into one offset.

Java takes a slightly different route. Because a double dimensional array in Java is an array of arrays — as section 8.8.1 explained — the rows are separate objects and need not sit next to one another in memory at all. The address formulas above describe the classical flat layout used by languages such as C and Fortran, which is the model the syllabus asks for and the model most hardware is built around. Within a single row, Java’s storage is exactly the contiguous block of section 8.9.1.

On paper, take a double matrix T[1...4][1...6] with a base address of 2000. Work out the address of T[3][4] in row major order and then in column major order, showing the two subtractions for the lower bounds in each case. Then check your answers by computing the address of the very last element, T[4][6], both ways — the two results must agree, and you should be able to say why.

8.10 Summary

Why arrays exist
  1. A single variable holds one value, and each assignment destroys the previous one, so data that must be revisited cannot be kept in one variable. Separate variables do not help either, because a name is fixed when the program is compiled while a loop can only change a value — no loop can turn one name into another.
  2. An array is a collection of a fixed number of elements of the same data type, stored under one name, each selected by an integer position. Because the position can be held in a variable, a loop can visit every element.
  3. Arrays are the right choice for a known quantity of same-typed data that must be visited repeatedly. Their limitations are real: the size cannot change after creation, the elements must share one type, and inserting or removing a value in the middle forces the rest to shift.
Creating and using a single dimensional array
  1. Declaring an array variable only creates a name; the new operator creates the block of cells and fixes its size. The size may be any integer expression, so it can be decided while the program runs, but it cannot change afterwards.
  2. An array variable holds a reference to the block, not the elements themselves. Assigning one array variable to another gives the same block a second name; it does not copy anything.
  3. The subscripts of an array of n elements run from 0 to n − 1, because a subscript records the distance of an element from the start of the block rather than its place in a count. There is no element at subscript n, and every access outside the range stops the program with an ArrayIndexOutOfBoundsException.
  4. Every cell is filled at creation with the default value of its type: zero for the integer types, 0.0 for the real types, the character with code 0 for char, false for boolean, and null for String and every other object type.
  5. Values known while the program is written can be given in an initialiser list, which creates the array and takes its size from the number of values listed. An initialiser list is allowed only in a declaration.
  6. Every array carries its own size in the length attribute, written without brackets. A loop bounded by length stays correct when the array’s size changes.
Getting data into an array
  1. Values may be assigned in the program, one at a time or computed inside a loop from the subscript; supplied as command-line arguments, which arrive in the String array received by main and must be converted from text before use; or read while the program runs with the Scanner class of the java.util package.
  2. Scanner supplies one method per type read. There is no method for a single character, which is obtained by reading a word and taking its first character.
Traversal
  1. Visiting every element exactly once, in order, is a traversal, and it is the shape of nearly every array operation. A variable that carries a result across the passes of the loop must be created before the loop and given a starting value.
  2. Some questions need more than one traversal. An average cannot be compared with the individual values until every value has been added, so counting the elements above the average requires two passes over the same data.
  3. The largest and smallest elements are found by holding a best-so-far and improving it. The starting value must be an element that is actually in the array; starting a maximum at zero gives a wrong answer for data that is entirely negative.
  4. The bounds of a traversal must match what the body touches. A body that reads the element after the current one may only run while the subscript is below n − 1.
  5. A single traversal of n elements costs \(O(n)\), where \(n\) is the number of elements. Two traversals of the same array still cost \(O(n)\), because a constant multiplier does not change how the work grows.
Searching
  1. Linear search, also called sequential search, compares the key with each element in turn and stops at the first match. It assumes nothing about the order of the data. Its best case is 1 comparison, its worst case is \(n\) comparisons where \(n\) is the number of elements, and its cost is \(O(n)\).
  2. Binary search requires the data to be in order. It compares the key with the middle element of the portion still under consideration and discards half of that portion at every step, because the ordering proves that the discarded half cannot contain the key. Its worst case is about \(\log_2 n\) comparisons and its cost is \(O(\log n)\).
  3. Applied to unsorted data, binary search does not fail loudly; it reports a value absent that is in fact present, because the reasoning that justifies discarding a half is no longer valid.
  4. A search should report the position, and −1 serves as the report of failure because it can never be a legal subscript.
Sorting
  1. Bubble sort compares neighbouring elements and exchanges those in the wrong order, so each pass carries the largest remaining value to the end. It always makes n(n − 1)/2 comparisons and cannot notice that the data is already sorted unless it is modified to do so.
  2. Selection sort finds the smallest element of the unsorted region and exchanges it with the first cell of that region. It always makes n(n − 1)/2 comparisons but performs at most n − 1 exchanges, so it moves data very little.
  3. Insertion sort keeps the front of the array in order and places each following element by shifting the larger elements one cell to the right. Its best case is data already in order, needing n − 1 comparisons and no shifting, which makes it \(O(n)\) on nearly sorted data.
  4. All three are \(O(n^2)\) in the worst case, where \(n\) is the number of elements: multiplying the data by ten multiplies the work by roughly a hundred.
  5. A sorting method is stable if equal values keep their original relative order. Bubble sort and insertion sort are stable; selection sort is not, because it exchanges distant elements.
Insertion, deletion and merging
  1. Because an array cannot grow, insertion is possible only in an array whose capacity exceeds the number of elements in use. The program keeps that count itself, and the elements occupy the subscripts below it.
  2. Inserting at a position means shifting every later element one cell to the right, and the shifting must run backwards from the last element; running it forwards copies one value over the whole tail of the list.
  3. Deleting at a position means shifting every later element one cell to the left and reducing the count. Nothing is erased — the last value remains in its cell and becomes unreachable only because the count no longer includes it.
  4. Both operations move up to \(n\) elements and therefore cost \(O(n)\), where \(n\) is the number of elements in use; both are cheapest at the end of the list and dearest at the front.
  5. Merging combines two sorted arrays into a sorted third by repeatedly taking the smaller of the two front elements, then copying whatever remains of the list that has not been exhausted. Each element is handled once, so the cost is \(O(m + p)\) for arrays of \(m\) and \(p\) elements — far less than discarding the order and sorting the combined data.
Double dimensional arrays
  1. A double dimensional array arranges elements in rows and columns, each element selected by two subscripts, the first for the row and the second for the column. The number of rows is the array’s own length; the number of columns is the length of a row.
  2. Processing a matrix needs two nested loops. With the row subscript on the outside the elements are visited row-wise; exchanging the nesting visits them column-wise, and that choice is what distinguishes a row total from a column total.
  3. A square matrix has as many rows as columns, and only a square matrix has diagonals. An element lies on the principal diagonal when its two subscripts are equal, and on the secondary diagonal when they add up to one less than the order. When the order is odd, the centre element lies on both.
  4. A square matrix is symmetric when the element at row i, column j equals the element at row j, column i for every pair of subscripts.
  5. Visiting every cell of a matrix of \(r\) rows and \(c\) columns costs \(O(r \times c)\), which for a square matrix of order \(n\) is \(O(n^2)\) — the cost of the quantity of data, not of the nesting.
Address calculation
  1. An array occupies a contiguous block of memory. The address of the first element is the base address, and every element occupies the same number of bytes, fixed by its type.
  2. In a single dimensional array, the address of the element at subscript i is the base address plus the element size multiplied by (i − lower bound). In Java the lower bound is always 0.
  3. This is a calculation, not a search: it costs the same for any subscript, so array access is constant time, \(O(1)\). That property is what allows binary search to jump straight to a middle element, and it is also why every element must be of the same size and therefore of the same type.
  4. A matrix must be laid out in a memory that has only one direction. Row major order stores one complete row after another, and the number of elements before the element at row i, column j is i × C + j, where C is the number of columns. Column major order stores one complete column after another, and the count is j × R + i, where R is the number of rows.
  5. The formula for row major order contains the number of columns and the formula for column major order contains the number of rows, because each must skip a whole row or a whole column at a time. Both orders use the same space and place the first and last elements identically; they disagree about everything between.

8.11 Key Terms

  1. array — a collection of a fixed number of elements of the same data type, stored under one name, each selected by an integer position.
  2. base address — the address of the memory location at which the first element of an array is stored.
  3. binary search — a search of sorted data that compares the key with the middle element of the portion still under consideration and discards half of it at every step.
  4. bubble sort — a sorting technique that repeatedly compares neighbouring elements and exchanges those that are in the wrong order.
  5. capacity — the number of cells an array has, fixed when it is created, as distinct from the number of cells currently in use.
  6. column major order — a layout that stores a matrix in memory one complete column after another.
  7. command-line argument — a word typed after the class name when a program is launched, received by main as an element of its String array.
  8. default value — the value automatically placed in every cell of an array when it is created, decided by the element type.
  9. double dimensional array — an array whose elements are arranged in rows and columns and selected by two subscripts.
  10. element — one individual value stored in an array.
  11. flag — a boolean variable used to record whether some condition has occurred, such as a successful search.
  12. in place — describing an operation that rearranges the elements of an existing array without creating a second one.
  13. index — another name for a subscript.
  14. initialiser list — a list of values in braces, given in a declaration, which creates an array and takes its size from the number of values listed.
  15. insertion sort — a sorting technique that keeps the front of the array in order and places each following element into it by shifting the larger elements to the right.
  16. linear search — a search that compares the key with each element in turn from the beginning until a match is found or the array is exhausted.
  17. matrix — a table of values arranged in rows and columns, held in a double dimensional array.
  18. merging — combining two sorted arrays into a single sorted array containing all their elements.
  19. pass — one complete sweep of a sorting or searching method through the data.
  20. principal diagonal — in a square matrix, the cells running from the top left corner to the bottom right, where the row and column subscripts are equal.
  21. reference — the value held in an array variable, identifying the block of memory where the elements are stored.
  22. row major order — a layout that stores a matrix in memory one complete row after another.
  23. search key — the value being looked for during a search.
  24. secondary diagonal — in a square matrix of order n, the cells running from the top right corner to the bottom left, where the two subscripts add up to n − 1.
  25. selection sort — a sorting technique that finds the smallest element of the unsorted region and exchanges it with the first cell of that region.
  26. sequential search — another name for linear search.
  27. single dimensional array — an array whose elements are selected by a single subscript.
  28. sorting — rearranging the elements of an array so that they run in ascending or descending order.
  29. square matrix — a matrix with as many rows as columns; the number of rows is called its order.
  30. stable — describing a sorting method that leaves equal values in their original relative order.
  31. structured data type — a type built out of many values of another type, held together and used as one thing.
  32. subscript — the integer written in brackets after an array name to select one element, measured as a distance from the start of the block and beginning at 0.
  33. subscripted variable — an array name together with a subscript, which behaves like an ordinary variable of the element type.
  34. swap — the exchange of the values held in two cells, performed with the help of a temporary variable.
  35. traversal — visiting every element of an array exactly once, in order.

8.12 Points to Ponder

  1. This chapter argued that numbering from 0 is the natural choice, because a subscript measures distance from the start of the block rather than position in a count. Yet the same choice is behind a large share of the errors beginners make, and a few languages number their arrays from 1 instead. If a language numbered from 1, which of the calculations in this chapter would become simpler and which would become clumsier — and is “easier to learn” the same thing as “easier to get right”?

  2. Bubble sort and selection sort made exactly the same number of comparisons on the same six values, but bubble sort moved data eight times and selection sort twice. For the small int arrays in this chapter that difference is invisible. What would the elements have to be like for movement to become the expensive part of sorting, and how would that change which of the three techniques you would choose?

  3. Binary search depends completely on the data being sorted, does not check that it is, and returns a confidently wrong answer when it is not. Checking would cost a full traversal — more than the search itself. Should an algorithm verify the assumption it rests on when the check costs more than the work, or is stating the assumption clearly the responsibility of whoever calls it?

  4. Deleting an element from an array leaves the value sitting in the last cell, unreachable only because the count no longer includes it. Is “deleted” an honest description of what happened? Consider what it would take to make the value genuinely gone, and whether any program would be worth the extra work.

  5. Java checks every subscript as the program runs and stops with an error when one falls outside the range; some languages perform no such check and run a little faster for it. The check catches a fault at the moment it is committed instead of allowing damage to surface somewhere unrelated. How would you decide what that certainty is worth, and does the answer depend on what the program is for?

  6. Row major and column major layouts store identical values, occupy identical space, and require identical numbers of operations to traverse — yet on real machines a traversal that runs against the storage order can be noticeably slower. If two programs perform the same number of steps on the same data, what could possibly make one of them slower, and what does that suggest about counting operations as a measure of cost?

8.13 Objective Questions

  1. An array is created as int a[] = new int[8];. The valid subscripts of this array are: [1 mark]
  1. 1 to 8
  2. 0 to 8
  3. 0 to 7
  4. 1 to 7
  1. Which of the following gives the number of elements in a single dimensional array a? [1 mark]
  1. a.length()
  2. a.length
  3. length(a)
  4. a.size()
  1. An array is created as String name[] = new String[4]; and nothing is assigned to it. The value of name[0] is: [1 mark]
  1. an empty piece of text
  2. a single space
  3. 0
  4. null
  1. Which of the following can be applied only to data that is already in order? [1 mark]
  1. Linear search
  2. Binary search
  3. Bubble sort
  4. Selection sort
  1. A matrix has R rows and C columns and is stored in row major order. The number of elements stored before m[i][j] is: [1 mark]
  1. i × R + j
  2. i × C + j
  3. j × R + i
  4. j × C + i
  1. Assertion (A): Selection sort performs at most n − 1 exchanges while sorting n elements. Reason (R): Selection sort makes n(n − 1)/2 comparisons whatever the arrangement of the data. Choose the correct option: [1 mark]
  1. Both A and R are true and R is the correct explanation of A.
  2. Both A and R are true but R is not the correct explanation of A.
  3. A is true but R is false.
  4. A is false but R is true.
  1. Assertion (A): Binary search cannot be relied upon when the elements of the array are not in order. Reason (R): After a single comparison, binary search discards half of the elements still under consideration without examining them. Choose the correct option: [1 mark]
  1. Both A and R are true and R is the correct explanation of A.
  2. Both A and R are true but R is not the correct explanation of A.
  3. A is true but R is false.
  4. A is false but R is true.
  1. Match each item in column A with the statement in column B that describes it. [1 mark]
Column A Column B
a. Linear search i. combines two sorted arrays into a single sorted array
b. Binary search ii. performs at most n − 1 exchanges for n elements
c. Selection sort iii. examines the elements one after another from the beginning
d. Merging iv. halves the portion still under consideration at every step

  1. Fill in the blank: in a square matrix of order n, the element m[i][j] lies on the secondary diagonal when ____________. [1 mark]

  2. State whether the following is true or false: deleting an element from an array reduces the capacity of the array. [1 mark]

8.14 Check Your Concepts

  1. Define an array, and state any two limitations that follow from the definition. [2 marks]

  2. State the default value placed in an element of a newly created array of each of these types: int, double, boolean and String. [2 marks]

  3. What is a subscripted variable? Give one example and state its type, for an array declared as double rate[] = new double[5];. [2 marks]

  4. An array is created as new int[n]. Give the range of its valid subscripts, and explain why the largest of them is n − 1 rather than n. [2 marks]

  5. Differentiate between linear search and binary search, giving any three points of difference. [3 marks]

  6. Differentiate between length as used with an array and length() as used with a String, and state what happens if the two are interchanged. [3 marks]

  7. Differentiate between bubble sort and selection sort on the basis of the number of comparisons and the amount of data movement each performs. [3 marks]

  8. An int matrix of 4 rows and 6 columns is stored from base address 1200, each element occupying 4 bytes. Calculate the address of m[2][3] in row major order and again in column major order, showing your working, and state the total number of bytes the matrix occupies. [4 marks]

  9. For a square matrix of order 5, name the five elements of the secondary diagonal. Explain why a single loop is enough to total that diagonal, and give the expression that produces the column subscript from the row subscript. [4 marks]

  10. A value is to be inserted into the middle of a list held in an array. Explain, with a small worked example of your own, why the shifting must begin at the last element and work backwards, and state what the list looks like if it is done the other way round. [4 marks]

  11. The array 8, 15, 23, 34, 47, 56, 68, 79 is searched for the value 56 using binary search. Show the values of the lower marker, the upper marker and the middle subscript at every step, state how many comparisons are made, and explain how the method would have detected the value 60 as absent. [6 marks]

  12. Compare bubble sort, selection sort and insertion sort with respect to their basic action, their behaviour on data that is already in order, and their worst-case cost in big O notation. State which of the three you would choose for a nearly sorted list, giving your reason. [6 marks]

8.15 Output & Debugging

  1. Give the output of the following fragment, and state in one line what it computes in general. [2 marks]
int a[] = {6, 2, 9, 4};
int s = 0;
for (int i = 0; i < a.length; i++)
{
    if (i % 2 == 0)
    {
        s = s + a[i];
    }
}
System.out.println(s);
  1. State the exact line printed by the fragment below, give the true average of the four marks, name the fault that accounts for the difference, and rewrite the offending statement correctly. [3 marks]
int m[] = {70, 65, 82, 60};
int total = 0;
for (int i = 0; i < m.length; i++)
{
    total = total + m[i];
}
int average = total / m.length;
System.out.println("Average = " + average);
  1. The fragment below compiles but does not run to completion. State what happens and at which value of i, name the error reported, and correct the loop so that all five cells are filled. [2 marks]
int p[] = new int[5];
for (int i = 1; i <= 5; i++)
{
    p[i] = i * i;
}
  1. Give the output of the following fragment, and name the set of elements whose total it produces. [3 marks]
int m[][] = {{3, 5, 7}, {2, 4, 6}, {8, 1, 9}};
int t = 0;
for (int i = 0; i < 3; i++)
{
    for (int j = 0; j < 3; j++)
    {
        if (i + j == 2)
        {
            t = t + m[i][j];
        }
    }
}
System.out.println(t);
  1. The fragment below is meant to sort the array into ascending order but stops with an error on its very first pass. Identify the single fault, correct it, and explain why the order of the two conditions matters. [3 marks]
int a[] = {9, 4, 7};
int i, j, temp;
for (i = 1; i < a.length; i++)
{
    temp = a[i];
    j = i - 1;
    while (a[j] > temp && j >= 0)
    {
        a[j + 1] = a[j];
        j--;
    }
    a[j + 1] = temp;
}
  1. The array below is searched for the value 31 by binary search. List, in order, the elements that are compared with the key, and state how many comparisons are made. [2 marks]
int v[] = {5, 11, 18, 24, 31, 40, 52};

8.16 Programming Practice

  1. Write a class that stores ten whole numbers in an array and displays the second largest of them without sorting the array and without using a second array. Submit the complete class and a variable description table. Sample input: 34, 78, 12, 90, 45, 67, 23, 90, 56, 81 — note that the largest value occurs twice, and state in a comment how your program treats that case. [4 marks]

  2. Write a class that stores ten whole numbers in an array, sorts them into descending order using bubble sort, and displays the whole array at the end of every pass, one pass to a line, followed by the sorted array. Submit the complete class. [4 marks]

  3. An array of capacity 30 holds n whole numbers in its first n cells, arranged in ascending order. Write a program that reads n (with 3 ≤ n ≤ 25) and the n numbers, then reads one further number and inserts it at its correct place so that the array remains in ascending order, and finally displays the enlarged list. The program must not sort the array again, and must display a suitable message if there is no spare cell. Submit an algorithm in pseudocode and the complete class. [6 marks]

  4. Write a program that reads two arrays of sizes m and p, each already in ascending order, and produces a third array containing all m + p values in ascending order, without sorting the third array at any stage. Display all three arrays. Submit an algorithm in pseudocode, the complete class, and a variable description table. [6 marks]

  5. Write a program that reads the order n of a square matrix (with 2 < n < 10, an unsuitable value producing a message and no further processing) and then reads n × n whole numbers into it. Display the matrix in its proper shape, the sum of the principal diagonal, the sum of the secondary diagonal, and a statement of whether the matrix is symmetric. Submit the complete class and a variable description table. Test with the order 3 and the values 4, 7, 2 / 7, 5, 9 / 2, 9, 6, and again with an order of your own choosing that is not symmetric. [6 marks]

  6. Write a single method with the header public static int countAbove(int a[], int limit) which returns how many elements of a are strictly greater than limit. Submit the method only, together with one line stating what your method returns when the array holds no such element. [4 marks]