Unit 4.5: Implementing Array Algorithms

Standard Algorithms

Essential Knowledge 4.5.A.1 identifies several standard algorithms that utilize array traversals. You must be able to develop, write, and trace code for these operations.

1. Determine a Minimum or Maximum Value

Initializing & Updating

To find the smallest or largest element, initialize a variable to the first element and update it as you traverse the remaining elements.

Task: Finding both the minimum and maximum values in an array of integers.

int[] arr = {5, 12, 3, 8, 1, 15};
int min = arr[0]; 
int max = arr[0];

for (int i = 1; i < arr.length; i++) {
    if (arr[i] < min) {
        min = arr[i];
    }
    if (arr[i] > max) {
        max = arr[i];
    }
}

2. Compute a Sum or Average

Accumulation

Use a cumulative sum variable to accumulate a total as you traverse the array. To find the average, divide that sum by the array length.

Task: Calculating the average of a double array.

double[] temps = {72.5, 80.0, 78.2, 69.9, 75.0};
double sum = 0;

for (double val : temps) {
    sum += val;
}
double average = sum / temps.length;

3. Determine if at least one element has a property

"Any" Match Logic

This is often called an "any" check. You can stop the traversal early (using break or return) as soon as you find a match.

Task: Checking if an array contains any negative numbers.

boolean hasNegative = false;
for (int n : nums) {
    if (n < 0) {
        hasNegative = true;
        break; 
    }
}

4. Determine if ALL elements have a property

"All" Match Logic

This is often called an "all" check. Assume the property is true and set it to false the moment you find an element that fails the criteria.

Task: Checking if all elements in an array are positive.

boolean allPositive = true;
for (int n : nums) {
    if (n <= 0) {
        allPositive = false;
        break;
    }
}

5. Determine the number of elements having a property

Incrementing Counters

Use a counter variable that increments each time an element meets the specified criteria.

Task: Counting elements that are greater than 100.

int count = 0;
for (int n : nums) {
    if (n > 100) {
        count++;
    }
}

6. Access all consecutive pairs of elements

Pairwise Comparison

To compare neighbors, use an indexed loop that stops at length - 1 to avoid an ArrayIndexOutOfBoundsException when accessing i + 1.

Task: Comparing adjacent elements to find consecutive duplicates.

for (int i = 0; i < arr.length - 1; i++) {
    if (arr[i] == arr[i + 1]) {
        // Found a consecutive duplicate pair
    }
}

7. Determine the presence or absence of duplicate elements

Nested Comparisons

This usually requires a nested loop to compare every element with every other element in the collection.

Task: Using nested loops to check for any duplicate values in an array.

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

8. Shift or Rotate elements left or right

Positional Shifting

Moving elements requires a loop and a temporary variable to prevent data loss. Rotate moves the element that "falls off" to the other end.

Task: Rotating an array one position to the right (wrap-around).

// Rotate Right by 1
int last = arr[arr.length - 1]; 
for (int i = arr.length - 1; i > 0; i--) {
    arr[i] = arr[i - 1];
}
arr[0] = last;

9. Reverse the order of the elements

Midpoint Swapping

Swap elements from the outside moving inward, stopping halfway through the array.

Task: Reversing the elements of an array in-place.

for (int i = 0; i < arr.length / 2; i++) {
    int temp = arr[i];
    arr[i] = arr[arr.length - 1 - i];
    arr[arr.length - 1 - i] = temp;
}