2.9 Implementing Selection and Iteration Algorithms

2.9 Implementing Selection and Iteration Algorithms

A useful algorithm is more than a clever idea: it is a sequence of instructions that makes a decision, repeats a process, or both. In Java, selection chooses among paths of execution, while iteration repeats a block of code until a condition or counting rule says to stop.

Learning Objective 2.9.A: Develop code for standard and original algorithms, without data structures, and determine the result of these algorithms.

The topic is associated with Practices 2, 3, and 4: Develop Code, Analyze Code, and Document Code and Computing Systems. Its suggested skills are 2.A: Write program code to implement an algorithm, 3.A: Determine the result or output based on statement execution order in an algorithm, and 4.A: Describe the behavior of a code segment or program.

The algorithmic toolkit

Selection and iteration work together like a sorting station. A conveyor belt repeatedly presents items; a decision gate examines each item and sends it down a particular path.

Structure	Question it answers	Typical Java form
Selection	“Which action should happen?”	if, else if, else
Iteration	“How many times should this action happen?”	for or while
Combined algorithm	“Repeat a process, making decisions along the way”	loop containing if

Essential Knowledge 2.9.A.1 identifies standard algorithms that can be implemented with these structures:

• determine whether one integer is evenly divisible by another;
• identify the individual digits in an integer;
• determine how frequently a criterion is met;
• determine a minimum or maximum value; and
• compute a sum or average.

Worked example: analyzing a rainfall record

Suppose a weather station receives one rainfall measurement at a time. Without using an array or other data structure, the program should count how many measurements are at least $10$ millimeters and calculate the total rainfall.

The algorithm needs three variables: total stores the running sum, heavyDays stores the frequency of measurements meeting the criterion, and measurement stores the current input.

int total = 0;
int heavyDays = 0;

for (int day = 1; day <= 5; day++) {
    int measurement = /* next rainfall measurement */;
    total += measurement;

    if (measurement >= 10) {
        heavyDays++;
    }
}

double average = total / 5.0;

The loop performs the same sequence for each of the five days. On every iteration, the assignment updates total; the selection updates heavyDays only when the current measurement satisfies measurement >= 10. After the loop, average is computed from the completed sum.

A useful invariant—a condition that remains true at a particular point in every repetition—is: before the next day begins, total equals the sum of all measurements already processed, and heavyDays equals the number of processed measurements that are at least $10$. This makes the algorithm easier to trace and debug.

Standard integer algorithms

Selection can test a remainder, while iteration can process digits or count events. For example, n % d == 0 is true exactly when integer n is evenly divisible by integer d, provided d is not zero.

To inspect the digits of a positive integer from right to left, repeatedly use number % 10 to obtain the last digit, then use integer division by $10$ to remove it:

int number = 4826;

while (number > 0) {
    int digit = number % 10;
    System.out.println(digit);
    number /= 10;
}

The output is 6, 2, 8, 4. The algorithm reverses the visual order because it removes the rightmost digit first. A selection statement can be added inside the loop to count even digits, test for a particular digit, or track a maximum.

Translating a for loop into a while loop

A for loop is not a fundamentally different kind of repetition. Its three control actions can be written explicitly in a while loop:

for (int count = 1; count <= 4; count++) {
    System.out.println(count);
}

int count = 1;              // initialization

while (count <= 4) {        // condition test
    System.out.println(count);
    count++;                // update
}

The equivalence depends on preserving the order: initialize once, test before each execution, run the body, then update. Moving the update before the body or forgetting it can change the result or create an infinite loop.

Misconception check: “The loop does the algorithm by itself”

Misconception: Any loop automatically computes the desired result. Correction: A loop only supplies repetition. The algorithm also needs correctly initialized variables, a meaningful condition, an update that makes progress, and selection logic that changes the result when a criterion is met.

Another frequent error is using total / 5 when both operands are integers. Java performs integer division first, potentially discarding the fractional part; total / 5.0 produces a double result.

Retrieval check

What must be added when converting for (int i = 0; i < 6; i++) to a while loop? State the three parts and identify where each appears.

Answer: Initialize i to $0$ before the loop, test i < 6 in the while condition, and update i—usually with i++—inside the loop body after the repeated work. If the update is missing, the condition remains true and the loop may never terminate.