2.1 Algorithms with Selection and Repetition

2.1 Algorithms with Selection and Repetition

An algorithm is a precise sequence of steps for solving a problem or producing an outcome. Algorithms use sequencing, and may also use selection and repetition, depending on the problem: a recipe can be sequencing alone, while a traffic-control system may repeatedly check conditions and choose different actions.

Learning Objective 2.1.A — Represent algorithms using sequencing, selection, and iteration.

The three control structures are the building blocks for describing how execution moves:

• Sequencing performs instructions in a particular order.
• Selection makes a decision and chooses which instructions execute.
• Repetition executes one or more steps more than once, using a condition, counter, collection, or other rule to determine when repetition stops.
• Iteration is repetition that changes the flow of control by returning execution to a segment of code. In Java, iteration is represented by while and for loops.

Selection depends on a true-or-false condition. If the condition is true, one path executes; if it is false, another path may execute or the algorithm may continue without performing that action. The exact order of these structures contributes to the algorithm’s outcome: checking a condition before updating a value can produce a different result from updating first and checking afterward.

A worked algorithm: filling seats

Imagine a theater assigning seats to arriving guests. The algorithm should examine each guest, assign a seat if one is available, and stop when there are no guests left or no seats remaining.

Here, sequencing establishes the order of actions, selection decides whether a seat can be assigned, and repetition processes multiple guests. The stopping rule is not necessarily “until the desired outcome is reached”; it can be a counter, a condition, a collection becoming empty, or another rule.

int seatsRemaining = 3;
int guestsWaiting = 5;

while (guestsWaiting > 0 && seatsRemaining > 0) {
    if (seatsRemaining > 0) {
        seatsRemaining--;
        guestsWaiting--;
    }
}

Trace the state after each iteration:

Iteration	seatsRemaining before	guestsWaiting before	seatsRemaining after	guestsWaiting after
1	3	5	2	4
2	2	4	1	3
3	1	3	0	2

The loop stops after the third iteration because seatsRemaining > 0 is false. Two guests remain waiting. The algorithm therefore reaches a valid stopping condition without serving every guest.

Fixed repetition and conditional repetition

A while loop is useful when the number of repetitions depends on a changing condition. A for loop is often useful when the algorithm has a clear counter or fixed range.

int total = 0;

for (int day = 1; day <= 7; day++) {
    total += day;
}

This loop repeats exactly seven times. The variable day starts at $1$, the body executes while day <= 7, and the update day++ prepares the next iteration. Repetition can therefore be controlled by a counter rather than by an unknown event.

Algorithms as diagrams and written language

An algorithm does not need to begin as Java code. A written description or flowchart can expose the logic before syntax is added:

Start
  ↓
Are guests waiting and seats available?
  ├── No → Stop
  └── Yes
          ↓
       Assign one seat
          ↓
       Update both counts
          ↺ Check the condition again

Representations are especially valuable when determining the result of an algorithm. Follow the instructions in order, record changing variables after each iteration, and identify the precise condition that causes execution to stop.

Iterative sorting algorithms

Selection sort and insertion sort are iterative sorting algorithms. Selection sort repeatedly selects the smallest remaining element and places it into the next position. Insertion sort repeatedly takes the next unsorted element and inserts it into its correct position among the elements already processed. Both algorithms use repetition to make progress through a collection, but their repeated actions organize elements differently.

Misconception check

Misconception: Every algorithm must contain all three structures. Algorithms may use sequencing alone, or sequencing combined with selection, repetition, or both.

Misconception: Repetition always means “repeat until the desired answer appears.” Repetition may stop after a fixed number of iterations, when a condition becomes false, when a collection is exhausted, or according to another explicit rule.

AP skill connection

This topic is assessed through Practice 1 — Design Code. Apply it by translating an everyday process into ordered steps, identifying decisions and repeated actions, choosing a suitable representation, and explaining why the order of operations produces the stated result.

Retrieval check: An algorithm scans five temperatures and stops early if it finds one below freezing. Which control structures are present, and what determines whether all five values are examined?
Answer: Sequencing orders the scan; selection tests each temperature; repetition processes multiple temperatures; the stopping condition determines whether the scan ends early or reaches all five values.