What an algorithm is

Written Explanation

An algorithm is a recipe

A recipe takes ingredients (input), follows steps in a fixed order, and produces a dish (output). An algorithm is the same shape:

• It has input: the data it starts with.
• It has steps that are clear and unambiguous. "Add some salt" is not clear enough for a computer; "add 2 to the counter" is.
• It has output: the answer.
• It finishes: after a limited number of steps it stops.

The pseudocode you wrote earlier is an algorithm written for people. A Java method is the same algorithm written for the computer. The method largest(int[] a) that returns the biggest number of an array is a good small example. In words:

1. Remember the first number as the best so far.
2. Look at each remaining number in turn.
3. If it is bigger than the best so far, make it the new best.
4. When the numbers run out, the best so far is the answer.

Many algorithms, one problem

Suppose a class list is in alphabetical order and you want to find "Mona".

• Way 1: read from the top. Check the first name, then the second, and so on, until you find her or run out of names.
• Way 2: open in the middle. Look at the middle name. If it comes after "Mona" in the alphabet, Mona must be in the first half, so ignore the second half. Repeat with the half that is left.

Both ways find Mona. They are two different algorithms for the same problem. Way 1 works on any list. Way 2 is much faster on a long list, but it only works because the list is sorted. You will write both in the next two lessons.

The same is true for putting books on a shelf by height. You could repeatedly swap neighbours that are in the wrong order, or repeatedly pick the shortest remaining book and place it next. Different steps, same result.

How we compare algorithms

When two algorithms exist, which one is better? We ask two questions, in this order:

1. Is it correct? Does it give the right answer for every valid input, including the awkward ones (an empty array, one element, a target that is not there)? A fast algorithm that is sometimes wrong is useless.
2. How many steps does it take? For a small list the difference does not matter. For large lists it matters a great deal. We will measure this by counting steps, such as comparisons, and later by timing.

Other qualities exist (how easy the code is to read, how much memory it needs), and readability matters in real teams. In this module we focus on correctness and the number of steps.

Searching and sorting

Two problems appear everywhere, so they are the classic starting point:

Sorting and searching are linked: a sorted collection can be searched much faster, which is why a book index, a phone book, and a dictionary are all in order.

Writing an algorithm as a method

Turning an algorithm into code follows the habits you already have: understand the problem, write the steps, then code, then test the edge cases. Here is largest and a second algorithm, isSorted, which we will reuse in this module to check that our sorting code works.

static int largest(int[] a) {
    int best = a[0];
    for (int i = 1; i < a.length; i++) {
        if (a[i] > best) best = a[i];
    }
    return best;
}

static boolean isSorted(int[] a) {
    for (int i = 0; i + 1 < a.length; i++) {
        if (a[i] > a[i + 1]) return false;
    }
    return true;
}

Notice that largest starts with a[0]. That is fine for an array with at least one element, but an empty array has no a[0] and the program would fail with an ArrayIndexOutOfBoundsException. A correct algorithm states what input it accepts; here, "at least one element". isSorted has no such problem: for an empty array or a one-element array the loop body never runs and the method returns true, which is the right answer (nothing is out of order).