4.5 Implementing Array Algorithms

Jump to topic

Unit 4 · Data Collections · Topic 4.5

Implementing Array Algorithms

Skill 2.BSkill 3.BSkill 3.DSkill 4.A

Big idea: Most array problems are variations on a few standard algorithms. Recognize the pattern and you have most of the code.

Learning objectives

Develop code for standard and original algorithms for a particular context or specification that involves arrays and determine the result of these algorithms.

Min, max, sum, average

Code

int[] a = {7, -2, 11, 4};
int max = a[0];
int sum = 0;
for (int x : a) {
  if (x > max) max = x;
  sum += x;
}
System.out.println(max + " " + sum + " " + (double) sum / a.length);

Output

11 20 5.0

Any, all, and count

Code

int[] a = {3, 8, 5, 12};
boolean anyEven = false;
boolean allPositive = true;
int big = 0;
for (int x : a) {
  if (x % 2 == 0) anyEven = true;
  if (x <= 0) allPositive = false;
  if (x > 4) big++;
}
System.out.println(anyEven + " " + allPositive + " " + big);

Output

true true 3

Consecutive pairs and duplicates

When comparing a[i] with a[i + 1], stop at length - 1 so i + 1 stays in bounds.

Code

int[] a = {1, 3, 3, 7, 2};
int ups = 0;
for (int i = 0; i < a.length - 1; i++) {
  if (a[i + 1] > a[i]) ups++;
}
boolean dup = false;
for (int i = 0; i < a.length; i++) {
  for (int j = i + 1; j < a.length; j++) {
    if (a[i] == a[j]) dup = true;
  }
}
System.out.println(ups + " " + dup);

Output

2 true

Reverse and rotate

Reverse by swapping from both ends toward the middle, stopping halfway. Rotate left by saving the first element, shifting everything down, and placing the saved value at the end.

Code

int[] a = {1, 2, 3, 4, 5};
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;
}
System.out.println(Arrays.toString(a));
int first = a[0];
for (int i = 0; i < a.length - 1; i++) {
  a[i] = a[i + 1];
}
a[a.length - 1] = first;
System.out.println(Arrays.toString(a));

Output

[5, 4, 3, 2, 1]
[4, 3, 2, 1, 5]

Key points

Standard algorithms: min/max, sum/average, any has a property, all have a property, count, consecutive pairs, duplicates, shift/rotate, reverse.
Start min/max at a[0] so negative-only arrays work.

Watch out

Swaps need a temporary variable.
Reversing with a loop that goes all the way to length swaps everything twice and leaves the array unchanged.
a[i + 1] with i < a.length goes out of bounds on the last pass.

Exam tip

Arrays.toString is used here only to show results; it isn't on the exam.

Quick check

What does this do?

for (int i = 1; i < a.length; i++)
  a[i] = a[i - 1];

Show answer

It copies a[0] into every element (each value is overwritten by the one just copied).

Practice 4.5 (11 questions)