Chapter 3 - Control Flow and Advanced Array Problems

Problem Solving with Arrays

We can traverse arrays, read and write elements, swap values, count matches, and sum totals. These are useful tools, but many real problems demand more from us.

Consider an array of exam scores. We want to find the highest one. There is no built-in operation for this. We can count, sum, and print elements, but finding the highest score requires something those operations do not: comparing elements to each other across the whole array. The answer is not in any single element. It emerges from visiting them all while keeping track of the best we have seen so far.

By the end of this section, you will find maximums and minimums, search for specific values, filter arrays into new ones, and sort elements into order. The tools are the ones you already have. What changes is how you combine them.

The Accumulation Pattern

We have already written loops that count matches and compute sums. Both of those loops follow the same shape: start with a variable, update it on each iteration, and use the final value after the loop ends. Here is a third problem with that same shape.

Suppose we have an array of quiz multipliers and want to compute the combined effect. If the multipliers are {2, 3, 4, 5}, the combined multiplier is 2 × 3 × 4 × 5 = 120. We need to multiply all the elements together and produce a single number.

int[] ar = new int[4];
ar[0] = 2;
ar[1] = 3;
ar[2] = 4;
ar[3] = 5;
 
int product = 1;
int i = 0;
while (i < ar.Length)
{
    product = product * ar[i];
    i++;
}

Translation: “Create an integer product and bind 1 to it. Starting at index 0, while i is less than ar.Length, multiply product by the element at index i of ar, then add 1 to i.”

Let’s trace it:

Iteration	i	ar[i]	product (before)	Calculation	product (after)
1	0	2	1	1 × 2	2
2	1	3	2	2 × 3	6
3	2	4	6	6 × 4	24
4	3	5	24	24 × 5	120

After the loop, product holds 120.

Now look at sum, count, and product side by side. All three follow the same shape: initialize a variable, visit each element, update the variable based on the element, and use the final value after the loop. This shape is called accumulation, and the variable that builds up the result is the accumulator.

Problem	Initial Value	Update Rule	Why This Initial Value
Sum	0	accumulator += element	Adding 0 changes nothing
Count (matching)	0	if condition: accumulator++	No matches found yet
Product	1	accumulator *= element	Multiplying by 1 changes nothing

The initial value must be a starting point that does not distort the result. Sum starts at 0 because adding 0 changes nothing. Product starts at 1 because multiplying by 1 changes nothing. Each operation has a value that leaves the other operand unchanged. In mathematics, this is called the identity element for the operation. Getting the initial value wrong corrupts every iteration that follows.

---

Try it yourself.

Predict the final value of product if the array is {1, 2, 3, 4, 5, 6} and the initial value is 0 instead of 1. What goes wrong?

Write your answer before revealing ours.

Reveal answer

The product stays 0 forever. On the first iteration, 0 × 1 = 0. On the second, 0 × 2 = 0. Multiplying by 0 produces 0 regardless of the elements. The wrong initial value poisons the entire computation.

If your answer differed, note what you missed before continuing.

---

Finding Maximum and Minimum

The accumulation pattern handles sum, count, and product. Finding the largest value in an array follows the same shape, but with a twist: the initial value is not a fixed number.

Imagine you have an array of 100 exam scores and want to report the highest one. There is no built-in operation for this. You have to look through the data yourself.

Try this mentally with a shorter list: {17, 42, 8, 99, 23}. Use a single finger and move left to right, one element at a time. How do you keep track of the largest value you have seen so far? How do you decide whether the current element is bigger than your best? And how do you know, when you reach the end, that you have the right answer?

If you did this by hand, you probably remembered the first value (17), then updated your memory when you saw 42, skipped 8 because it was smaller, updated again at 99, and skipped 23. At the end, 99 was your answer. That process is exactly what the code does. The result should be 99.

int[] values = new int[5];
values[0] = 17;
values[1] = 42;
values[2] = 8;
values[3] = 99;
values[4] = 23;
 
int max = values[0];
int i = 1;
while (i < values.Length)
{
    if (values[i] > max)
    {
        max = values[i];
    }
    i++;
}

Translation: “Create an integer max and bind the element at index 0 of values to it. Starting at index 1, while i is less than values.Length, if the element at index i is greater than max, update max to that element. Then add 1 to i.”

The initial value comes from the array itself. If we used 0 instead, an array of all-negative values would produce 0 as the maximum, a value that does not appear in the array. The maximum must be a value that actually exists in the array, so we start with the first element. The loop starts at index 1, since index 0 is already in the accumulator.

Iteration	i	values[i]	values[i] > max	max (after)
1	1	42	42 > 17 → true	42
2	2	8	8 > 42 → false	42
3	3	99	99 > 42 → true	99
4	4	23	23 > 99 → false	99

After the loop, max holds 99.

Finding the minimum uses the same pattern with < instead of >, and initializes min to values[0].

---

Try it yourself.

Translate the max-finding loop above to English and build the state table for the array {-5, -12, -3, -8, -1}. What is the final value of max?

Write your answer before revealing ours.

Reveal answer

Translation: “Create an integer max and bind the element at index 0 of values to it. Starting at index 1, while i is less than values.Length, if the element at index i is greater than max, update max to that element. Then add 1 to i.”

Iteration	i	values[i]	values[i] > max	max (after)
1	1	-12	-12 > -5 → false	-5
2	2	-3	-3 > -5 → true	-3
3	3	-8	-8 > -3 → false	-3
4	4	-1	-1 > -3 → true	-1

The final value of max is -1. Starting at values[0] (-5) ensured the answer is a value that actually exists in the array.

If your answer differed, note what you missed before continuing.

---

Practice Round 1: Accumulation Patterns

Translate and predict:

1. Translate this loop to English and predict the final value of average. The line (double)sum converts the integer sum to a double before the division. This is a cast, a conversion from one type to another. Without it, sum / ar.Length would be integer division, which discards the remainder.

int[] ar = new int[5];
ar[0] = 85;
ar[1] = 92;
ar[2] = 78;
ar[3] = 90;
ar[4] = 88;
 
int sum = 0;
int i = 0;
while (i < ar.Length)
{
    sum = sum + ar[i];
    i++;
}
double average = (double)sum / ar.Length;

What type is average, and why does the cast matter?

2. Translate this loop and predict the final value of min:

int[] ar = new int[5];
ar[0] = 42;
ar[1] = 17;
ar[2] = 8;
ar[3] = 99;
ar[4] = 23;
 
int min = ar[0];
int i = 1;
while (i < ar.Length)
{
    if (ar[i] < min)
    {
        min = ar[i];
    }
    i++;
}

Write code. For each problem, write the complete code including the array declaration.

3. Find the product of all elements in an array holding {2, 3, 4, 5}.
4. Count how many elements in an array holding {-3, 5, 0, -8, 12} are negative.
5. Translate this loop to English and predict the final value of aCount:

int[] scores = new int[6];
scores[0] = 95;
scores[1] = 82;
scores[2] = 91;
scores[3] = 67;
scores[4] = 88;
scores[5] = 74;
 
int aCount = 0;
int i = 0;
while (i < scores.Length)
{
    string grade = scores[i] switch
    {
        >= 90 => "A",
        >= 80 => "B",
        >= 70 => "C",
        >= 60 => "D",
        _ => "F"
    };
 
    if (grade == "A")
    {
        aCount++;
    }
    i++;
}

Write your answers before revealing ours.

Reveal answer

1. Translation: “Create an integer sum and bind 0 to it. Starting at index 0, while i is less than ar.Length, add the element at index i of ar to sum. Then add 1 to i. After the loop, create a double average and bind the result of casting sum to double, then dividing by ar.Length.”

Sum is 433. Average is 86.6. The cast matters because sum and ar.Length are both integers. Without (double), the division would produce 86 (integer division truncates). The cast converts sum to a double before the division, so the result keeps its decimal portion.

2. Translation: “Create an integer min and bind the element at index 0 of ar to it. Starting at index 1, while i is less than ar.Length, if the element at index i is less than min, update min to that element. Then add 1 to i.”

The final value of min is 8.

3.

int[] ar = new int[4];
ar[0] = 2;
ar[1] = 3;
ar[2] = 4;
ar[3] = 5;
 
int product = 1;
int i = 0;
while (i < ar.Length)
{
    product = product * ar[i];
    i++;
}
// product is 120

4.

int[] ar = new int[5];
ar[0] = -3;
ar[1] = 5;
ar[2] = 0;
ar[3] = -8;
ar[4] = 12;
 
int count = 0;
int i = 0;
while (i < ar.Length)
{
    if (ar[i] < 0)
    {
        count++;
    }
    i++;
}
// count is 2

5. Translation: “Create an integer aCount and bind 0 to it. Starting at index 0, while i is less than scores.Length: evaluate the element at index i using a switch expression. If it is at least 90, the result is ‘A’. If at least 80, the result is ‘B’. If at least 70, ‘C’. If at least 60, ‘D’. Otherwise, ‘F’. Bind the result to a string grade. If grade equals ‘A’, add 1 to aCount. Then add 1 to i.”

The scores are 95, 82, 91, 67, 88, 74. The switch expression classifies 95 as “A”, 82 as “B”, 91 as “A”, 67 as “D”, 88 as “B”, and 74 as “C”. Two scores are classified as “A”, so aCount is 2.

Compare each answer to the model. Note specific differences. Write the corrected version before continuing.

---

Linear Search

We can find the maximum, but what if we need to know whether a specific value exists, and where it is?

Imagine a program that stores student ID numbers in an array. A student types in their ID, and the program needs to answer two questions: is this ID in the list, and if so, at which position? The only way to find out is to check each element, one at a time, until we find a match or run out of elements.

Given {7, 3, 9, 5, 1, 8} and target 5, the result should be 3, because 5 is at index 3. If the target is 42, it does not appear in the array, and we need a way to report that. Think about what you would do by hand: you would scan left to right, and the moment you found 5, you would stop. You would not keep checking the rest. If you reached the end without finding it, you would know it was not there.

int[] data = new int[6];
data[0] = 7;
data[1] = 3;
data[2] = 9;
data[3] = 5;
data[4] = 1;
data[5] = 8;
 
int target = 5;
int foundIndex = -1;
bool found = false;
int i = 0;
 
while (i < data.Length && !found)
{
    if (data[i] == target)
    {
        foundIndex = i;
        found = true;
    }
    i++;
}

Translation: “Create an integer foundIndex and bind -1 to it. Create a boolean found and bind false to it. Starting at index 0, while i is less than data.Length and found is false, read the element at index i. If it equals the target, store i in foundIndex and set found to true. Then add 1 to i.”

Two ideas in this code are worth naming.

The variable foundIndex starts at -1. No valid index is -1, so this value signals that the search failed. A value chosen specifically to signal an outcome like this is called a sentinel value. If the loop ends without finding the target, foundIndex is still -1. If it finds the target, foundIndex holds a valid index.

The loop condition includes a boolean variable, found, that controls whether the loop continues. The condition i < data.Length && !found tells the complete story: keep going while there are elements left AND we have not found what we are looking for. This is the boolean flag pattern.

When the target is present, the loop ends early:

Iteration	i	data[i]	data[i] == target	found	foundIndex
1	0	7	false	false	-1
2	1	3	false	false	-1
3	2	9	false	false	-1
4	3	5	true	true	3
exit	4	—	—	true → !found is false	3

On iteration 4, the target is found at index 3. The variable found becomes true. On the next condition check, !found evaluates to false, and the loop stops. The remaining elements are never checked.

When the target is absent, the loop runs to completion:

Iteration	i	data[i]	data[i] == target	found	foundIndex
1	0	7	false	false	-1
2	1	3	false	false	-1
3	2	9	false	false	-1
4	3	5	false	false	-1
5	4	1	false	false	-1
6	5	8	false	false	-1
exit	6	—	—	6 < 6 → false	-1

With target = 42, no element matches. The loop checks every element, i reaches 6 (data.Length), and the first half of the condition stops the loop. The variable foundIndex is still -1, signaling that the target was not found.

Either way, foundIndex tells us the result: a valid index if found, -1 if not.

How many steps does a search take? In the best case, the target is at index 0, and we find it in 1 comparison. In the worst case, the target is at the last index or absent entirely, and we check every element. For an array of 1000 elements, that could mean up to 1000 comparisons. Compare this to accessing an element by index, which is always 1 step regardless of position.

---

Try it yourself.

Given the array above, trace the search loop for target = 1. How many iterations run before found becomes true? What is foundIndex after the loop?

Write your answer before revealing ours.

Reveal answer

Iteration	i	data[i]	data[i] == 1	found	foundIndex
1	0	7	false	false	-1
2	1	3	false	false	-1
3	2	9	false	false	-1
4	3	5	false	false	-1
5	4	1	true	true	4
exit	5	—	—	true → !found is false	4

Five iterations run. After the loop, foundIndex is 4.

If your answer differed, note what you missed before continuing.

---

Any and All Checks

Linear search answers “where is this value?” Two related questions come up constantly when working with data: “does any element satisfy a condition?” and “do all elements satisfy a condition?”

Before posting final grades, you might want to check: did any student score below 60? Do all students have passing grades? These are yes-or-no questions about the entire array. You do not need an index or a value. You need a boolean.

Given {4, 7, -2, 8, 1}, are any values negative? The answer is yes, because -2 is negative. Are all values positive? No, for the same reason. Notice that once you find the -2, you can stop. You do not need to check the rest of the array. The answer to “any negative?” is already determined.

Any: Does at least one element satisfy a condition?

int[] values = new int[5];
values[0] = 4;
values[1] = 7;
values[2] = -2;
values[3] = 8;
values[4] = 1;
 
bool anyNegative = false;
int i = 0;
while (i < values.Length && !anyNegative)
{
    if (values[i] < 0)
    {
        anyNegative = true;
    }
    i++;
}

Translation: “Create a boolean anyNegative and bind false to it. Starting at index 0, while i is less than values.Length and anyNegative is false, if the element at index i is less than 0, set anyNegative to true. Then add 1 to i.”

Start with false. The moment we find one match, flip to true. The condition !anyNegative stops the loop.

All: Do all elements satisfy a condition? Using the same array:

bool allPositive = true;
int i = 0;
while (i < values.Length && allPositive)
{
    if (values[i] <= 0)
    {
        allPositive = false;
    }
    i++;
}

Translation: “Create a boolean allPositive and bind true to it. Starting at index 0, while i is less than values.Length and allPositive is true, if the element at index i is less than or equal to 0, set allPositive to false. Then add 1 to i.”

Start with true. The moment we find one violation, flip to false. The condition allPositive stops the loop.

Notice the relationship: “any negative” and “not all positive” ask the same question from opposite directions.

Both patterns use a boolean flag in the condition. Both stop as soon as the answer is determined. This is the same mechanism as linear search, applied to a yes/no question instead of an index question.

---

Try it yourself.

Given {4, 7, -2, 8, 1}, trace the any-negative loop. On which iteration does the loop stop? What is the value of i when the loop exits?

Write your answer before revealing ours.

Reveal answer

Iteration	i	values[i]	values[i] < 0	anyNegative
1	0	4	false	false
2	1	7	false	false
3	2	-2	true	true
exit	3	—	—	true → !anyNegative is false

The loop stops after iteration 3. The value of i when the loop exits is 3. The elements at indices 3 and 4 are never checked.

If your answer differed, note what you missed before continuing.

---

Index of Maximum

Finding the maximum value is useful, but sometimes we need to know where the maximum lives, not just what it is. Suppose you have two arrays: one holding student names and another holding their scores, lined up by position. To display the top scorer’s name, knowing the highest score is 99 is not enough. You need to know that 99 is at index 3, so you can look up the name at index 3 in the other array.

Given {17, 42, 8, 99, 23}, we want the index of the largest value. The largest value is 99, which is at index 3, so the result should be 3. This combines the max-finding pattern with index tracking.

int maxIndex = 0;
int i = 1;
while (i < values.Length)
{
    if (values[i] > values[maxIndex])
    {
        maxIndex = i;
    }
    i++;
}

Translation: “Create an integer maxIndex and bind 0 to it. Starting at index 1, while i is less than values.Length, if the element at index i is greater than the element at index maxIndex, update maxIndex to i. Then add 1 to i.”

We track the index, not the value. The value is always available as values[maxIndex]. Using the array {17, 42, 8, 99, 23}:

Iteration	i	values[i]	values[maxIndex]	values[i] > values[maxIndex]	maxIndex (after)
1	1	42	17	true	1
2	2	8	42	false	1
3	3	99	42	true	3
4	4	23	99	false	3

After the loop, maxIndex is 3, and values[3] is 99. The index-of-minimum pattern is the same with < instead of >.

This pattern is a building block for sorting, which we reach later in this section.

---

Try it yourself.

Find the index of the minimum value in {12, 5, 8, 3, 15}. What is minIndex after the loop? What value does values[minIndex] hold?

Write your answer before revealing ours.

Reveal answer

int minIndex = 0;
int i = 1;
while (i < values.Length)
{
    if (values[i] < values[minIndex])
    {
        minIndex = i;
    }
    i++;
}

Iteration	i	values[i]	values[minIndex]	values[i] < values[minIndex]	minIndex (after)
1	1	5	12	true	1
2	2	8	5	false	1
3	3	3	5	true	3
4	4	15	3	false	3

After the loop, minIndex is 3 and values[3] is 3.

If your answer differed, note what you missed before continuing.

---

Practice Round 2: Search and Check Problems

Translate and predict:

1. Translate this loop to English and predict the value of foundIndex after it runs:

int[] ar = new int[5];
ar[0] = 10;
ar[1] = 25;
ar[2] = 42;
ar[3] = 8;
ar[4] = 16;
 
int target = 42;
int foundIndex = -1;
bool found = false;
int i = 0;
 
while (i < ar.Length && !found)
{
    if (ar[i] == target)
    {
        foundIndex = i;
        found = true;
    }
    i++;
}

2. Translate this loop and predict the value of allEven after it runs:

int[] ar = new int[4];
ar[0] = 6;
ar[1] = 12;
ar[2] = 9;
ar[3] = 4;
 
bool allEven = true;
int i = 0;
while (i < ar.Length && allEven)
{
    if (ar[i] % 2 != 0)
    {
        allEven = false;
    }
    i++;
}

Write code. For each problem, write the loop pattern. Assume the array is already declared and populated.

3. Write a linear search for the value 42 in an array named ar. Use the -1 sentinel and a boolean flag in the condition.
4. Check if any element in an array named scores is below 60.
5. Find the index of the minimum value in an array named ar.

Write your answers before revealing ours.

Reveal answer

1. Translation: “Create an integer foundIndex and bind -1 to it. Create a boolean found and bind false to it. Starting at index 0, while i is less than ar.Length and found is false, if the element at index i equals the target, store i in foundIndex and set found to true. Then add 1 to i.”

foundIndex is 2 after the loop. The target 42 is at index 2. The loop runs 3 iterations and stops.

2. Translation: “Create a boolean allEven and bind true to it. Starting at index 0, while i is less than ar.Length and allEven is true, if the element at index i is odd (ar[i] % 2 != 0), set allEven to false. Then add 1 to i.”

allEven is false. The value 9 at index 2 is odd, which sets allEven to false and stops the loop.

3.

int target = 42;
int foundIndex = -1;
bool found = false;
int i = 0;
while (i < ar.Length && !found)
{
    if (ar[i] == target)
    {
        foundIndex = i;
        found = true;
    }
    i++;
}

4.

bool anyBelow60 = false;
int i = 0;
while (i < scores.Length && !anyBelow60)
{
    if (scores[i] < 60)
    {
        anyBelow60 = true;
    }
    i++;
}

5.

int minIndex = 0;
int i = 1;
while (i < ar.Length)
{
    if (ar[i] < ar[minIndex])
    {
        minIndex = i;
    }
    i++;
}

Compare each answer to the model. Note specific differences. Write the corrected version before continuing.

---

Filtering: Building a New Array

Suppose you have survey data with a mix of positive, negative, and zero responses, and you want to extract just the positive ones into a separate list.

Given {-3, 5, 0, -8, 12, -7, 9}, we want a new array holding just the positive values. The result should be {5, 12, 9}. Try it by hand: scan through the original array, and each time you find a positive value, write it down. By the end, you have three values written down.

That is easy on paper. But arrays have a fixed size. We cannot add elements one at a time. Before we create the new array, we have to know how big it will be. And we cannot know that until we count the matches. This means filtering requires two passes through the data: one to count how many elements match, and one to copy them into a new array of the right size.

Pass 1: Count matches.

int[] values = new int[7];
values[0] = -3;
values[1] = 5;
values[2] = 0;
values[3] = -8;
values[4] = 12;
values[5] = -7;
values[6] = 9;
 
int positiveCount = 0;
int i = 0;
while (i < values.Length)
{
    if (values[i] > 0)
    {
        positiveCount++;
    }
    i++;
}

After this loop, positiveCount is 3 (the values 5, 12, and 9).

Pass 2: Fill new array.

int[] positives = new int[positiveCount];
int fillIndex = 0;
i = 0;
while (i < values.Length)
{
    if (values[i] > 0)
    {
        positives[fillIndex] = values[i];
        fillIndex++;
    }
    i++;
}

Two indices advance at different rates. The variable i visits every element of the original array. The variable fillIndex only advances when an element passes the condition. They start together at 0 but diverge immediately.

This is the scenario where precise language prevents confusion, so we return to the full shift form. With two arrays and two indices, the compressed form “store the value at fillIndex” does not make clear which array we are writing to. Translation: “While i is less than values.Length, go to the location of values, shift by i, and read the value there. If it is greater than 0, go to the location of positives, shift by fillIndex, and store that value there. Then add 1 to fillIndex. After the condition check, add 1 to i.”

Here is the full state table for pass 2:

Iteration	i	values[i]	values[i] > 0	fillIndex (before)	Action	fillIndex (after)
1	0	-3	false	0	skip	0
2	1	5	true	0	positives[0] = 5	1
3	2	0	false	1	skip	1
4	3	-8	false	1	skip	1
5	4	12	true	1	positives[1] = 12	2
6	5	-7	false	2	skip	2
7	6	9	true	2	positives[2] = 9	3

After the loop, i reached 7 (values.Length) and fillIndex reached 3 (positiveCount). The positives array holds {5, 12, 9}.

Notice the two indices at work. By iteration 7, i is at 6 while fillIndex is only at 2, because four elements failed the condition and were skipped:

  values:    [ -3 ][ 5 ][ 0 ][ -8 ][ 12 ][ -7 ][ 9 ]
                    ↑              ↑              ↑
                    passed         passed         passed
               i moves through every element →

  positives: [ 5 ][ 12 ][ 9 ]
               fillIndex moves only when an element passes →

The two-pass approach is the cost of fixed-size arrays. We count first, allocate, then fill.

---

Try it yourself.

Write the two-pass filtering code to keep only even values from {3, 8, 1, 6, 5, 4}. Build the state table for pass 2.

Write your answer before revealing ours.

Reveal answer

Pass 1:

int[] ar = new int[6];
ar[0] = 3;
ar[1] = 8;
ar[2] = 1;
ar[3] = 6;
ar[4] = 5;
ar[5] = 4;
 
int evenCount = 0;
int i = 0;
while (i < ar.Length)
{
    if (ar[i] % 2 == 0)
    {
        evenCount++;
    }
    i++;
}
// evenCount is 3

Pass 2:

int[] evens = new int[evenCount];
int fillIndex = 0;
i = 0;
while (i < ar.Length)
{
    if (ar[i] % 2 == 0)
    {
        evens[fillIndex] = ar[i];
        fillIndex++;
    }
    i++;
}

State table for pass 2:

Iteration	i	ar[i]	ar[i] % 2 == 0	fillIndex (before)	Action	fillIndex (after)
1	0	3	false	0	skip	0
2	1	8	true	0	evens[0] = 8	1
3	2	1	false	1	skip	1
4	3	6	true	1	evens[1] = 6	2
5	4	5	false	2	skip	2
6	5	4	true	2	evens[2] = 4	3

The evens array holds {8, 6, 4}.

If your answer differed, note what you missed before continuing.

---

Reversing into a New Array

Sometimes data arrives in one order but needs to be used in another. A list of recent transactions might be stored newest-first, but a report needs oldest-first.

Given {10, 20, 30, 40, 50}, we want a new array holding the same elements in reverse order: {50, 40, 30, 20, 10}. The original array stays unchanged. The question is: for each position in the original, where does that element land in the reversed array?

Each element needs to go to its mirror position. Element at index i in the original goes to index Length - 1 - i in the reversed array.

int[] reversed = new int[original.Length];
int i = 0;
while (i < original.Length)
{
    reversed[original.Length - 1 - i] = original[i];
    i++;
}

Translation: “Starting at index 0, while i is less than original.Length, read the element at index i of original and store it at index Length - 1 - i of reversed. Then add 1 to i.”

For a 5-element array, the mapping works out as follows:

i	original.Length - 1 - i	Mapping
0	4	original[0] → reversed[4]
1	3	original[1] → reversed[3]
2	2	original[2] → reversed[2]
3	1	original[3] → reversed[1]
4	0	original[4] → reversed[0]

The formula Length - 1 - i maps the first index to the last, the second to the second-to-last, and so on. When i reaches the middle, the mapping crosses over and continues to the other end.

---

Try it yourself.

Predict the contents of reversed after reversing the array {10, 20, 30, 40}. Write out the mapping table showing which index in original maps to which index in reversed.

Write your answer before revealing ours.

Reveal answer

i	original.Length - 1 - i	Mapping
0	3	original[0] (10) → reversed[3]
1	2	original[1] (20) → reversed[2]
2	1	original[2] (30) → reversed[1]
3	0	original[3] (40) → reversed[0]

The reversed array holds {40, 30, 20, 10}.

If your answer differed, note what you missed before continuing.

---

Selection Sort

Sorting is one of the most common operations in programming. Any time you display a leaderboard, rank search results, or organize records by date, the data needs to be in order.

Given {38, 27, 43, 3, 9}, we want the elements in order from smallest to largest: {3, 9, 27, 38, 43}.

Think about how you would do this by hand. One natural approach: scan the whole list, find the smallest value, and write it down first. Then scan what remains, find the next smallest, and write it down second. Keep going until everything is in order. Each round, the unsorted portion shrinks by one and the sorted portion grows by one.

That is exactly the strategy here. It combines three skills from earlier in the chapter: traversal, finding the index of the minimum, and swapping.

int outer = 0;
while (outer < ar.Length - 1)
{
    int minIndex = outer;
    int inner = outer + 1;
    while (inner < ar.Length)
    {
        if (ar[inner] < ar[minIndex])
        {
            minIndex = inner;
        }
        inner++;
    }
 
    int temp = ar[outer];
    ar[outer] = ar[minIndex];
    ar[minIndex] = temp;
 
    outer++;
}

Translation: “Starting at index 0, while outer is less than ar.Length - 1: find the index of the smallest element from index outer to the end of the array. Swap the element at index outer with the element at minIndex. Then add 1 to outer.”

The outer loop condition is outer < ar.Length - 1, not ar.Length. When the last element is the only one remaining, it is already in its correct position. There is nothing left to compare it to.

Let’s walk through {38, 27, 43, 3, 9}. Each pass finds the minimum in the unsorted portion and swaps it into place. A boundary separates the sorted elements (on the left) from the unsorted elements (on the right):

  Pass 0:  [ 38 | 27 | 43 |  3 |  9 ]     all unsorted
                                            sorted ‖ unsorted

  Pass 1:  [  3 | 27 | 43 | 38 |  9 ]     min was 3 at index 3, swapped with index 0
            ─────                           sorted ‖ unsorted

  Pass 2:  [  3 |  9 | 43 | 38 | 27 ]     min was 9 at index 4, swapped with index 1
            ──────────                      sorted ‖ unsorted

  Pass 3:  [  3 |  9 | 27 | 38 | 43 ]     min was 27 at index 4, swapped with index 2
            ───────────────                 sorted ‖ unsorted

  Pass 4:  [  3 |  9 | 27 | 38 | 43 ]     min was 38 at index 3, swapped with itself
            ────────────────────            sorted ‖ last element in place

The same data in table form:

After pass	ar[0]	ar[1]	ar[2]	ar[3]	ar[4]
start	38	27	43	3	9
1	3	27	43	38	9
2	3	9	43	38	27
3	3	9	27	38	43
4	3	9	27	38	43

Each pass, the sorted portion grows by one element. The unsorted portion shrinks by one. After 4 passes, the array is sorted.

How much work does selection sort do? The first pass checks 4 elements, the second checks 3, the third checks 2, the fourth checks 1. Total comparisons: 4 + 3 + 2 + 1 = 10. For an array of n elements, that is roughly n × n / 2 comparisons. For 10 elements, about 45. For 1000 elements, about 500,000.

---

Try it yourself.

Trace selection sort on {5, 2, 8, 1, 4}. Show the array state after each pass and identify which elements were swapped.

Write your answer before revealing ours.

Reveal answer

After pass	ar[0]	ar[1]	ar[2]	ar[3]	ar[4]	What happened
start	5	2	8	1	4
1	1	2	8	5	4	min was 1 at index 3, swapped with index 0
2	1	2	8	5	4	min was 2 at index 1, swapped with itself
3	1	2	4	5	8	min was 4 at index 4, swapped with index 2
4	1	2	4	5	8	min was 5 at index 3, swapped with itself

If your answer differed, note what you missed before continuing.

---

Insertion Sort

Selection sort finds the smallest and puts it in place. Here is a different strategy that produces the same result.

Think about how you sort a hand of playing cards. You probably do not scan for the smallest card each time. Instead, you pick up one card at a time and slide it into the right spot among the cards you have already sorted. The sorted portion of your hand grows by one card with each insertion.

Given {38, 27, 43, 3, 9}, we still want {3, 9, 27, 38, 43}, but instead of finding the smallest each time, we take the next unsorted element and slide it into its correct position among the elements already sorted.

This introduces a new operation: shifting. Multiple elements move one position to the right to make room for the element being inserted. This is different from a swap, where only two elements exchange positions.

int i = 1;
while (i < ar.Length)
{
    int key = ar[i];
    int j = i - 1;
 
    while (j >= 0 && ar[j] > key)
    {
        ar[j + 1] = ar[j];
        j--;
    }
    ar[j + 1] = key;
 
    i++;
}

Translation of the outer loop: “Starting at index 1, while i is less than ar.Length: save the element at index i in key. Then shift elements to the right until key’s correct position is found, and place key there. Then add 1 to i.”

Translation of the inner loop: “While j is at least 0 and the element at index j is greater than key, store the element at index j into index j + 1, then subtract 1 from j.”

The inner loop condition tells the complete story. The check j >= 0 prevents shifting before the start of the array. The check ar[j] > key stops when we find an element that is not greater than key, which is the correct insertion point. Both exit paths are visible in the condition.

Let’s visualize the shifting for one pass. On pass 4, key is 9:

  Before (key = 9):
  [  3 | 27 | 38 | 43 |  9 ]
                          ^ key = 9, saved

  43 > 9? Yes, shift right:   [  3 | 27 | 38 |    | 43 ]
  38 > 9? Yes, shift right:   [  3 | 27 |    | 38 | 43 ]
  27 > 9? Yes, shift right:   [  3 |    | 27 | 38 | 43 ]
   3 > 9? No, stop.

  Insert key at j + 1:        [  3 |  9 | 27 | 38 | 43 ]

Three elements shifted one position to the right, creating space for 9 at index 1.

Here is the full walkthrough with the same array used for selection sort, {38, 27, 43, 3, 9}:

After pass	ar[0]	ar[1]	ar[2]	ar[3]	ar[4]	What happened
start	38	27	43	3	9
1	27	38	43	3	9	key=27, shifted 38 right, inserted at index 0
2	27	38	43	3	9	key=43, no shifting needed, stays in place
3	3	27	38	43	9	key=3, shifted 43, 38, 27 right, inserted at index 0
4	3	9	27	38	43	key=9, shifted 43, 38, 27 right, inserted at index 1

Both selection sort and insertion sort produce a sorted array. The difference is in how much work they do. Selection sort always makes the same number of comparisons regardless of the input. Insertion sort does fewer comparisons when the array is already partially sorted. On a fully sorted array, insertion sort does only n - 1 comparisons, since each element is already in the right position and no shifting occurs. Selection sort still does roughly n × (n - 1) / 2 comparisons even on a sorted array.

---

Common Bugs Revisited

The patterns in this section create bugs that are harder to spot than those in basic traversals. Some are off-by-one errors. Others involve missing updates that silently corrupt the result.

Bug 1: Filtering, forgetting to advance fillIndex.

// Bug: fillIndex never increments
if (values[i] > 0)
{
    positives[fillIndex] = values[i];
}

Every matching element overwrites index 0 of the positives array. The result has only the last match at index 0, and the rest of the array holds default values. The fix: add fillIndex++; inside the if block, after the assignment.

Bug 2: Reverse, using Length - i instead of Length - 1 - i.

// Bug: off by one in the index formula
reversed[original.Length - i] = original[i];

When i is 0, the expression original.Length - 0 evaluates to Length, which is one past the last valid index. The program crashes with an IndexOutOfRangeException on the very first iteration. The fix: use original.Length - 1 - i.

Bug 3: Selection sort, inner loop starting at outer instead of outer + 1.

// Bug: inner starts at outer, not outer + 1
int inner = outer;
while (inner < ar.Length)

The element at index outer is compared to itself. The comparison ar[outer] < ar[minIndex] is never true (a value is not less than itself), so minIndex is not affected. The loop wastes one comparison per pass but does not crash or produce wrong results. The fix: start inner at outer + 1.

---

Practice Round 3: Problem Solving

Translate and predict:

1. Translate this program to English and predict the contents of the filtered array:

int[] scores = new int[6];
scores[0] = 55;
scores[1] = 82;
scores[2] = 91;
scores[3] = 47;
scores[4] = 73;
scores[5] = 88;
 
int sum = 0;
int i = 0;
while (i < scores.Length)
{
    sum = sum + scores[i];
    i++;
}
double average = (double)sum / scores.Length;
 
int aboveCount = 0;
i = 0;
while (i < scores.Length)
{
    if (scores[i] > average)
    {
        aboveCount++;
    }
    i++;
}
 
int[] aboveAverage = new int[aboveCount];
int fillIndex = 0;
i = 0;
while (i < scores.Length)
{
    if (scores[i] > average)
    {
        aboveAverage[fillIndex] = scores[i];
        fillIndex++;
    }
    i++;
}

Write code. For each problem, write the complete code including the array declaration.

2. Find the range (max - min) of an array holding {12, 4, 7, 2, 9}.
3. Determine if an array holding {3, 5, 8, 12, 20} is already sorted in ascending order. Use a boolean flag in the while condition: check whether every element is less than or equal to the next one.
4. Sort {12, 4, 7, 2, 9} using selection sort. Show the array state after each pass.
5. Sort {12, 4, 7, 2, 9} using insertion sort. Show the array state after each pass.
6. Given an array of scores {95, 72, 88, 61, 55, 90, 83, 77}, use a switch expression to classify each score as a letter grade (“A” for 90+, “B” for 80+, “C” for 70+, “D” for 60+, “F” otherwise). Count how many scores earned a “B” or higher. Use two passes: one to count, one to filter those scores into a new array.

Write your answers before revealing ours.

Reveal answer

1. Translation: “Create an integer sum and bind 0 to it. Starting at index 0, while i is less than scores.Length, add the element at index i of scores to sum. Then add 1 to i. After the loop, create a double average and bind the result of casting sum to double, then dividing by scores.Length.

“Create an integer aboveCount and bind 0 to it. Starting at index 0, while i is less than scores.Length, if the element at index i is greater than average, add 1 to aboveCount. Then add 1 to i.

“Create an integer array of size aboveCount and store a reference to it in aboveAverage. Create an integer fillIndex and bind 0 to it. Starting at index 0, while i is less than scores.Length, if the element at index i is greater than average, go to the location of aboveAverage, shift by fillIndex, and store that value there. Then add 1 to fillIndex. After the condition check, add 1 to i.”

The sum is 436. The average is 72.666… (a double). The scores above average are 82, 91, 73, and 88, so aboveCount is 4. The aboveAverage array holds {82, 91, 73, 88}.

2.

int[] ar = new int[5];
ar[0] = 12;
ar[1] = 4;
ar[2] = 7;
ar[3] = 2;
ar[4] = 9;
 
int max = ar[0];
int min = ar[0];
int i = 1;
while (i < ar.Length)
{
    if (ar[i] > max)
    {
        max = ar[i];
    }
    if (ar[i] < min)
    {
        min = ar[i];
    }
    i++;
}
int range = max - min;
// max is 12, min is 2, range is 10

3.

int[] ar = new int[5];
ar[0] = 3;
ar[1] = 5;
ar[2] = 8;
ar[3] = 12;
ar[4] = 20;
 
bool sorted = true;
int i = 0;
while (i < ar.Length - 1 && sorted)
{
    if (ar[i] > ar[i + 1])
    {
        sorted = false;
    }
    i++;
}
// sorted is true

Notice that the loop runs while i < ar.Length - 1, not ar.Length. Each iteration compares ar[i] to ar[i + 1], so we must stop one position before the end to avoid going out of bounds.

4. Selection sort on {12, 4, 7, 2, 9}:

After pass	ar[0]	ar[1]	ar[2]	ar[3]	ar[4]	What happened
start	12	4	7	2	9
1	2	4	7	12	9	min was 2 at index 3, swapped with index 0
2	2	4	7	12	9	min was 4 at index 1, swapped with itself
3	2	4	7	12	9	min was 7 at index 2, swapped with itself
4	2	4	7	9	12	min was 9 at index 4, swapped with index 3

5. Insertion sort on {12, 4, 7, 2, 9}:

After pass	ar[0]	ar[1]	ar[2]	ar[3]	ar[4]	What happened
start	12	4	7	2	9
1	4	12	7	2	9	key=4, shifted 12 right, inserted at index 0
2	4	7	12	2	9	key=7, shifted 12 right, inserted at index 1
3	2	4	7	12	9	key=2, shifted 12, 7, 4 right, inserted at index 0
4	2	4	7	9	12	key=9, shifted 12 right, inserted at index 3

6.

int[] scores = new int[8];
scores[0] = 95;
scores[1] = 72;
scores[2] = 88;
scores[3] = 61;
scores[4] = 55;
scores[5] = 90;
scores[6] = 83;
scores[7] = 77;
 
// Pass 1: count scores that earned B or higher
int highCount = 0;
int i = 0;
while (i < scores.Length)
{
    string grade = scores[i] switch
    {
        >= 90 => "A",
        >= 80 => "B",
        >= 70 => "C",
        >= 60 => "D",
        _ => "F"
    };
 
    if (grade == "A" || grade == "B")
    {
        highCount++;
    }
    i++;
}
 
// Pass 2: filter into new array
int[] highScores = new int[highCount];
int fillIndex = 0;
i = 0;
while (i < scores.Length)
{
    string grade = scores[i] switch
    {
        >= 90 => "A",
        >= 80 => "B",
        >= 70 => "C",
        >= 60 => "D",
        _ => "F"
    };
 
    if (grade == "A" || grade == "B")
    {
        highScores[fillIndex] = scores[i];
        fillIndex++;
    }
    i++;
}

The classifications are: 95→A, 72→C, 88→B, 61→D, 55→F, 90→A, 83→B, 77→C. Four scores earned B or higher (95, 88, 90, 83), so highCount is 4. The highScores array holds {95, 88, 90, 83}.

Compare each answer to the model. For the sorting exercises, compare your state table to the model pass by pass. Note specific differences and write the corrected version before continuing.

---

Review

Before continuing, test yourself on what you have learned. Use the protocol from Chapter 0: attempt each exercise from memory, then search the chapter to check your answers, then note what you missed.

Part 1: Definitions

Write the definition from memory, then find it in the chapter to check.

1. What is an accumulator?

If your answer differed, note what you missed and write the corrected version.

Part 2: Translations (Code → English)

Translate each loop to English.

int foundIndex = -1;
bool found = false;
int i = 0;
while (i < data.Length && !found)
{
    if (data[i] == 10)
    {
        foundIndex = i;
        found = true;
    }
    i++;
}

int max = data[0];
int i = 1;
while (i < data.Length)
{
    if (data[i] > max)
    {
        max = data[i];
    }
    i++;
}

int[] negatives = new int[negCount];
int fillIndex = 0;
int i = 0;
while (i < data.Length)
{
    if (data[i] < 0)
    {
        negatives[fillIndex] = data[i];
        fillIndex++;
    }
    i++;
}

int aCount = 0;
int i = 0;
while (i < scores.Length)
{
    string grade = scores[i] switch
    {
        >= 90 => "A",
        >= 80 => "B",
        _ => "Other"
    };
 
    if (grade == "A")
    {
        aCount++;
    }
    i++;
}

Check your translations against the patterns in this section and the switch expression syntax from Chapter 2.

Part 3: Writing Code (English → Code)

Write C# code for each description.

1. “Create an integer foundIndex and bind -1 to it. Create a boolean found and bind false to it. Starting at index 0, while i is less than ar.Length and found is false, if the element at index i equals 7, store i in foundIndex and set found to true. Then add 1 to i.”

2. “Create an integer maxIndex and bind 0 to it. Starting at index 1, while i is less than ar.Length, if the element at index i is greater than the element at index maxIndex, update maxIndex to i. Then add 1 to i.”

3. Write code to check if all elements in an array are positive, using a boolean flag in the while condition.

4. Write the two-pass filtering code to keep only values greater than 10.

5. Reverse an array into a new array.

Check your code against the examples in this section.

Part 4: Iteration Tables

Build a complete iteration table for this code:

int[] ar = new int[6];
ar[0] = 4;
ar[1] = -2;
ar[2] = 7;
ar[3] = 1;
ar[4] = -5;
ar[5] = 3;
 
bool anyNegative = false;
int i = 0;
while (i < ar.Length && !anyNegative)
{
    if (ar[i] < 0)
    {
        anyNegative = true;
    }
    i++;
}

Your table should include columns for i, ar[i], the condition check, and anyNegative after each iteration. On which iteration does the loop exit?

Part 5: Bug Identification

Each loop has a bug. Identify the problem and write the corrected version.

int[] positives = new int[count];
int fillIndex = 0;
int i = 0;
while (i < ar.Length)
{
    if (ar[i] > 0)
    {
        positives[fillIndex] = ar[i];
    }
    i++;
}

int[] reversed = new int[ar.Length];
int i = 0;
while (i < ar.Length)
{
    reversed[ar.Length - i] = ar[i];
    i++;
}

int outer = 0;
while (outer < ar.Length - 1)
{
    int minIndex = outer;
    int inner = outer;
    while (inner < ar.Length)
    {
        if (ar[inner] < ar[minIndex])
        {
            minIndex = inner;
        }
        inner++;
    }
    int temp = ar[outer];
    ar[outer] = ar[minIndex];
    ar[minIndex] = temp;
    outer++;
}

For each, trace the loop with an iteration table to confirm your fix.

Part 6: State Tables

Complete the state table for selection sort on {9, 3, 7, 1, 5}. Show the array after each pass and identify which elements were swapped.

Part 7: Complete Program

Write a program that creates an array holding {15, 8, 22, 3, 17, 10, 25, 6}. Compute the average. Filter the array to keep only values above the average. Sum the filtered values and display the result.

Trace through your program with state tables to verify it produces the correct result.

Previous: Section 2 - Basic Computation

Next: Section 4 - Functions on Arrays