From Z to A: Reversing arrays (Part 3 of 4)
Using for loops to reverse arrays
This is an ongoing series. Please check out the collection for the rest of the articles.
How many ways can you travel through this patch of forest? One way is obvious: walk down the well-trodden path in the center of the photo. But there are other ways, as well. You can walk around to the left through the trees on the hill. You can trudge through the dense brush to the right. Getting a little more creative, you can hang-glide above the trees or dig a tunnel under the ground. Just because there is one very obvious way to traverse the land — walking down the path — doesn’t mean that the alternatives aren’t worth considering.
I’m not trying to be philosophical, by the way. There are real, practical reasons to consider alternatives. It all depends on the context. If it’s raining and you don’t have an umbrella, walking under the trees to the left will be a much drier journey than the exposed path. If you’re being pursued by bandits, the brush to the right provides more cover than the path even if it takes longer to navigate. There is no best way to travel unless you also specify a context, or set of goals. Once you have a set of goals, then you can examine which route is most helpful in achieving them, and the best route is simply the one that helps the most.
This case is precisely analogous to how algorithms are designed and chosen; there is no best way to reverse an array in general. Different contexts require different goals and only after specifying them can one choose a best algorithm. The strength of an algorithm depends on the context in which it is used.
Getting back to the core lesson, the algorithm I showed you last post is one of many ways to reverse an array. The alternative I’m going to show you this time has different strengths and weaknesses and is therefore useful in different contexts. Knowing how to reverse an array is useful but knowing many ways to reverse an array is even better.
The core of last post’s algorithm is the while loop. Accordingly, we’ll name that algorithm the while method. Let’s take a look at another algorithm based on the for loop. To do that, it would behoove us to define the for instruction:
- for (initial; condition; step) do (code): compute initial; while condition is true, compute code; after each iteration, compute step
The first thing to note is that instead of short, generic variable names like x, y, and z, I’ve used longer, descriptive labels like initial, condition, and step. That’s because for loops are syntactically complicated and I want each part to be clear; even though they function very similarly to while loops, they include a lot of parts that make them look complex.
So let’s examine what this for loop does. A for loop accepts four expressions, initial, condition, step, and code. initial initializes a variable that serves as a counter; it keeps track of how far the loop has gone. Each iteration, the step expression changes this counter by some amount (usually increasing it by 1). condition, like the while method’s equivalent, is a Boolean expression that determines whether or not to iterate through the loop; if condition returns true, code is computed; otherwise, Cake exits the for loop and moves on. Here’s an example of a for loop in action:
Let’s look at what’s going on here. First, we make a new variable named x and set it to 0. Then we encounter a for loop; it begins by computing the initial expression:
This instruction sets i to 0. Because this instruction happens inside the for loop, the variable i exists only as long as the for loop does. Unfortunately, this touches on the concept of scope, which is a big topic we’re not quite ready to cover. For now, don’t ask why this is the case, just accept it as is. (If you’re a curious individual, that last sentence may sound like anathema, but you can’t learn everything at once! I’ll explain scope as soon as I’m able to). The important part is to recognize that for the duration of the loop, there exists a variable i that is initially set to 0.
What happens next, you ask? First, the condition is checked:
i was initialized to 0 so the expression becomes 0 < 10, which returns true. Since the condition returned true, the code inside the loop is computed:
x started out at 0, so after the first iteration, it is now set to 1. Extrapolating, x gets increased by 1 each iteration of the loop. After the above code is computed, the step expression is computed (remember, the step code is supposed to increase the counter that keeps track of the loop’s progress):
Now i is 1. Next, the condition is checked again. 1 < 10, so the code inside the loop gets computed again; the step gets computed again; the condition is checked again. I hope you see the pattern. When i reaches 10, the condition returns false and Cake jumps out of the loop. By the end of the loop, x (which exists before, during, and after the loop) has been increased by 1 a total of 10 times. Since it started at 0, its final value is 10.
To practice understanding for loops, try to figure out what x will be after this loop:
When you think you’ve found the answer, read on. Notice that this code is similar to the last one but with a few key differences:
- The initial value of x; instead of being 0, this time x is initialized to 1
- The condition; instead of iterating 10 times, this loop iterates only 3
- The code computed each iteration; instead of adding 1 to x each iteration, this loop doubles x
Since the loop iterates 3 times and x, which is initially 1, is multiplied by 2 each time, at the end of the loop x equals 1 * 2 * 2 * 2, which is 8.
Returning to the theme of reversing arrays, how can we use a for loop to reverse an array? Given an array a, like this:
How does this work? The first important aspect to notice is the condition. This loop doesn’t iterate over the whole array — it stops halfway. That’s what the expression
says; once i reaches half of the size of the array, the loop exits. Since i increases by 1 each iteration, the loop iterates over every element of the array until it reaches halfway. Why should it do this? Because each iteration, the element with index i swaps values with the element with the opposite index. “Opposite” here means that if an element is 4 from the start of the array, its opposite is 4 from the end. Swapping each element of an array with its opposite is exactly the same as reversing the array, so this method works. (If the array has an odd number of elements, the element in the middle gets swapped with itself, which has no effect).
How does this swapping work? As before, we store the original value of the ith element of the array in a variable called temp, which stands for “temporary variable”:
Next, we calculate which element is opposite the one at index i:
To see how this code works, pick a few examples. Let’s say the array has 4 elements:
If i is 0, then opposite_i, according to the code above, equals 4 - 1 - 0, which is 3. Since 0 is 0 elements from the start, its opposite should be 0 elements from the end. What index is 0 from the end in a 4-element array? A 4-element array has 4 indices: 0, 1, 2, 3, so index 3 is 0 from the end. Accordingly, 3 is exactly what gets stored in opposite_i. What if i is 1? Then opposite_i is set to 4 - 1 - 1, which equals 2. Index 1 is 1 element from the start of the array and index 3 is 1 element from the end, so this example checks out too. Keep plugging in examples if you’re not convinced — really! I want you to see that this works.
A question remains, however: why does it work? Take another look at it:
Observe that size(a) returns 1 more than the final index of a — if a has 4 elements, the final index is 3. So subtracting 1 from the size of the array returns the final index. Subtracting i from this final index returns an index that is as far from the end of the array as i is from the start. For the example array,
size(a) - 1 is 3 (the index that points to 7); thus, when i is 1, then opposite_i is set to 4 - 1 - 1, which is 2. This means that the 8 (at index 1) swaps with the 2 (at index 2). This is exactly what should happen. It is not a coincidence or quirk of math that the code works; it was designed with this purpose in mind.
To reiterate what I said above, this method — let’s call it the for method — is just one of many ways to reverse an array. There are more methods that use for loops and many more that don’t. Like the while method, the for method alters the array its given — a is the reverse of what it was before the code runs. But this behavior is not always desired; what if we want to know the reverse of an array without modifying the original copy? A great way to achieve this is by reversing the array using recursion. In the next post, I’ll explain how a recursive method can be used to produce a reverse array without changing the original. I’ll also give a brief cost-benefit analysis of the three methods we’ve seen to give a broader perspective.
Image credit: forest
