Implementing Array Algorithms: Study Guide (Computer Science A 4.5)

Standard plans, now in Java

Topic 4.2 taught you the shape of a plan for a data set: set up, repeat for each value, report. Topic 4.4 taught you how to traverse an array. This topic puts them together. The course names a set of standard algorithms that use array traversals, and you are expected to write them, trace them and spot faults in them. They are:

• determine a minimum or maximum value;
• compute a sum or average;
• determine whether at least one element has a particular property;
• determine whether all elements have a particular property;
• determine the number of elements having a particular property;
• access all consecutive pairs of elements;
• determine the presence or absence of duplicate elements;
• shift or rotate elements left or right;
• reverse the order of the elements.

Each one is a short traversal with one extra idea. The methods below are written as class methods (static) that take an array parameter. Remember from Topic 3.6 that an array parameter holds a copy of the reference: a method that only reads the array leaves it alone, and a method that assigns to a[i] changes the caller’s array.

Minimum and maximum

Keep a best so far, start it at the first element, and replace it when a better one appears.

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

public static int minOf(int[] a)
{
    int best = a[0];
    for (int v : a)
    {
        if (v < best)
        {
            best = v;
        }
    }
    return best;
}

Starting from a[0] is essential. If you started best at 0 and every element were negative, nothing would ever beat it and the method would return 0, which is not in the array. In maxOf the loop starts at index 1 because index 0 is already the starting value; minOf uses an enhanced for loop, which is fine because only the values matter.

Sum and average

Keep a running total that starts at 0.

public static int sum(int[] a)
{
    int total = 0;
    for (int v : a)
    {
        total += v;
    }
    return total;
}

public static double average(int[] a)
{
    return (double) sum(a) / a.length;
}

The cast in average matters: (double) sum(a) / a.length divides as a double. Without the cast, sum(a) / a.length would use integer division and drop the fractional part.

At least one, and all

These two are mirror images, and mixing them up is a classic fault.

public static boolean anyNegative(int[] a)
{
    for (int v : a)
    {
        if (v < 0)
        {
            return true;
        }
    }
    return false;
}

public static boolean allPositive(int[] a)
{
    for (int v : a)
    {
        if (v <= 0)
        {
            return false;
        }
    }
    return true;
}

• At least one element has the property: as soon as you find one, you know the answer is true, so you return true inside the loop. Only after the loop has examined every element without success can you say false.
• All elements have the property: as soon as one element fails, the answer is false. Only after the loop has found no failure can you say true.

Note the test in allPositive checks for the failure (v <= 0), not the property.

Counting

Keep a count that starts at 0 and add 1 for each element with the property. Never reset it inside the loop.

public static int countAbove(int[] a, int limit)
{
    int count = 0;
    for (int v : a)
    {
        if (v > limit)
        {
            count++;
        }
    }
    return count;
}

Consecutive pairs

To compare each element with the next one, use a[i] and a[i + 1]. The largest i that has a next element is a.length - 2, so the loop test is i < a.length - 1.

public static int countRisingPairs(int[] a)
{
    int count = 0;
    for (int i = 0; i < a.length - 1; i++)
    {
        if (a[i] < a[i + 1])
        {
            count++;
        }
    }
    return count;
}

Duplicates

To find out whether any two elements are equal you need to compare each element with every element after it. That takes a loop inside a loop. The inner loop starts at i + 1 so that an element is never compared with itself.

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

Shifting, rotating and reversing

These algorithms change the array.

To rotate left by one place, every element moves one place left and the first element wraps round to the end. You must save the first element before it is overwritten.

public static void rotateLeft(int[] a)
{
    int first = a[0];
    for (int i = 0; i < a.length - 1; i++)
    {
        a[i] = a[i + 1];
    }
    a[a.length - 1] = first;
}

public static void rotateRight(int[] a)
{
    int last = a[a.length - 1];
    for (int i = a.length - 1; i > 0; i--)
    {
        a[i] = a[i - 1];
    }
    a[0] = last;
}

To rotate right, work from the end so you do not overwrite elements you still need: save the last element, copy each element one place right starting at the last index, then put the saved value at index 0. (Copying left to right would copy the same value over every box.)

To reverse the order, swap the elements at the two ends and move inwards, stopping at the middle. Stopping at the middle matters: if the loop went to the end, every pair would be swapped twice and the array would be restored to its original order.

public static void reverse(int[] a)
{
    for (int i = 0; i < a.length / 2; i++)
    {
        int temp = a[i];
        a[i] = a[a.length - 1 - i];
        a[a.length - 1 - i] = temp;
    }
}

Worked example 1: max, average and count on one array

Task. For t = {4, 9, 2, 7, 9}, find the maximum, the minimum, the average and the count of elements greater than 5.

Maximum. best starts at t[0] = 4.

i	t[i]	t[i] > best?	best
(start)			4
1	9	yes	9
2	2	no	9
3	7	no	9
4	9	no (9 > 9 is false)	9

The maximum is 9. The minimum, found the same way with <, is 2.

Sum and average. 4 + 9 + 2 + 7 + 9 = 31, and (double) 31 / 5 = 6.2.

Count above 5. The elements above 5 are 9, 7 and 9, so the count is 3.

The compiled program printed 9 2, 31 6.2 and 3 for these three results. Starting from 0 would also have worked for this array, but for {-4, -9, -2} the correct maximum is -2, while a method starting at 0 returns 0; the compiled program printed -2 0 for the correct and the faulty method.

Check. The maximum 9 and minimum 2 can be read straight off the array; the sum can be rechecked by adding in a different order.

Worked example 2: pairs, duplicates, rotation and reversal

Rising pairs in t = {4, 9, 2, 7, 9}. The pairs are (4, 9), (9, 2), (2, 7) and (7, 9). Rising means the first is less than the second: yes, no, yes, yes. The count is 3. The loop ran for i = 0, 1, 2, 3, that is i < 4, which is a.length - 1.

Duplicates in t. i = 0 (value 4) compares with 9, 2, 7, 9: no match. i = 1 (value 9) compares with 2, 7, 9: the last is equal, so the method returns true at once. For u = {2, 7, 1, 8} every pair is different, the loops finish and the result is false. Printed: true, then false.

Rotating {1, 2, 3, 4, 5} left.

Step	first	a[0]	a[1]	a[2]	a[3]	a[4]
start		1	2	3	4	5
first = a[0]	1	1	2	3	4	5
i = 0: a[0] = a[1]	1	2	2	3	4	5
i = 1: a[1] = a[2]	1	2	3	3	4	5
i = 2: a[2] = a[3]	1	2	3	4	4	5
i = 3: a[3] = a[4]	1	2	3	4	5	5
a[4] = first	1	2	3	4	5	1

The result is 2 3 4 5 1. Applying rotateRight to that array gives 1 2 3 4 5, and applying rotateRight again to the original gives 5 1 2 3 4 (all three confirmed by running the code).

Reversing {4, 8, 15, 16, 23}. The loop runs for i < 5 / 2, which is i < 2: i = 0 swaps a[0] and a[4]; i = 1 swaps a[1] and a[3]. The middle element, 15, stays where it is. The result is 23 16 15 8 4. For an even length such as {1, 2, 3, 4}, the loop runs for i < 2 and every element moves: 4 3 2 1.

Check. After each of these algorithms, check the extreme positions (first and last), which is where off-by-one mistakes hide.

Common faults the exam likes to test

• Starting a maximum at 0. Fails for all-negative data.
• Returning too early. For “all”, return true on the first element that passes is wrong. allEvenFlawed({2, 4, 5}) returns true because 2 is even; the correct allEven returns false because 5 is not. The compiled program printed true false for the flawed and correct methods on {2, 4, 5}.
• Integer division in an average. total / a.length with two ints drops the fraction: for {1, 2, 2} the flawed version printed 1.0 while the correct one printed 1.6666666666666667.
• Resetting a count inside the loop.
• Comparing neighbours with i < a.length. It makes a[i + 1] go out of bounds on the last pass.
• Rotating right from the front. It copies one value into every position.
• Reversing to the end instead of the middle. The array comes back unchanged.

Common misconceptions

• “A maximum of an empty array is 0.” Starting from a[0] fails on an empty array; these methods assume at least one element.
• “For ‘at least one’ I need a counter.” A boolean result and an early return true are enough.
• “The two loops for duplicates can both start at 0.” Then each element matches itself.
• “Rotating an array creates a new array.” These methods change the array they are given.
• “The enhanced for loop can reverse or rotate.” Those need indices.

Where this leads

These algorithms are the heart of the multiple-choice tracing questions and of the array free-response questions. Next in Unit 4 come text files, wrapper classes and the ArrayList, where the same plans reappear with different syntax. For a mixed check on Unit 3 first, use the Unit 3 review. Practise this topic with the practice questions, read the revision notes and tick the topic checklist. For the traversal tools, revisit Array Traversals.