From Z to A: Reversing arrays (Part 2 of 4)

Using while loops and variables to reverse arrays

This is an ongoing series. Please check out the collection for the rest of the articles.

In the first part of this series, we explored while loops and variables. In this part, we’re going to utilize them in our quest to reverse an array. I don’t want to show you any code yet, however. I want you to think about how you would reverse an array. First, think of it in broad terms; don’t worry about Cake instructions or technical details. Instead, try to imagine what reversing an array involves. To help visualize the problem, here’s a sample array:

And here it is reversed:

How do we get from the first array to the second one? Take a minute and brainstorm before moving on.

I hope you’ve thought of some ideas. They don’t have to be good ideas or even ideas that work — just ideas. The goal is to practice this kind of problem solving. As we did with finding the biggest number in an array, let’s start with the easiest case first: when the array has just 1 element. If the array is [7] then reversing it is also [7]. If there is just one element, reversing the array doesn’t change anything. What about when there are 2 elements, such as [7, 9]? The reverse is [9, 7], which can be computed by swapping the two elements in the array. If the array [7, 9] is called a, then you can reverse it like this:

The variable reversed equals [9, 7], as expected. How? The value assigned to reversed, [a[1], a[0]], is an array with two elements. The first element of reversed is the second element of a and the second element of reversed is the first element of a. So the two values of a have been swapped to get its reverse, which is stored in the variable reversed. To be clear, the name reversed is for human readability, not computer readability; we could name the variable ham_sandwich and giving it the same value would still properly store the reverse of a. The name of a variable should reflect its contents, but it certainly doesn’t determine them.

So the cases of 1-element and 2-element arrays are fairly straightforward. The trouble comes with arrays that have more than 2 elements. Let’s turn our attention to the 3-element case. If the array a is [3, 4, 5], then the reverse of a is [5, 4, 3]. Notice that in both the original and reverse arrays, 4 is the second element. The difference is that the 3 and 5 swap spots. So the instructions to reverse it go like this:

reversed stores the reverse of a. The first element in reversed is the last element in a and the last element in reversed is the first element in a. The situation is, as you can see, much like the 2-element case but with a middle element added. The 4-element case proceeds in the same manner. If a equals [10, 12, 18, 20] then:

The inner elements (indices 1 and 2) have swapped and the outer elements (indices 0 and 3) have swapped. As expected the result is [20, 18, 12, 10]. Now look at the 5-element case (I swear we’re almost done going over individual cases!):

This is just like the 4-element case except there’s a middle element (index 2) that has the same indices in both arrays. What’s the pattern here? Once again, spend a minute or two thinking about how you can use what we’ve uncovered here to find a good solution to the general reversal instruction. You could manually write each case, of course, but that would be silly and cumbersome; we need a general solution that works for any size array. In fact, our general solution shouldn’t even mention size in its description:

• reverse(a): reverses the array a

No matter what the size of a is, reverse should work correctly. I’ll give you a couple more hints before revealing my answer: first, there are many different ways to reverse an array, but aim for using one while loop and one or two variables. Second, the set instruction introduced last post can be used with array elements as well:

In this case, a is originally [1, 5]. Then the first element, a[0] is set to 6. Finally, the second element, a[1], is set to 2. Thus, the final value of a is [6, 2]. One last thing to mention is that, when devising your solution, don’t try to be clever — try to be clear and obvious. The goal isn’t ingenuity, it’s correctness.

OK, ready for the general solution? Given an array a, here’s my answer (remember that mine is not the only correct answer):

This is the longest, most complex code I’ve introduced so far, and I want to go over every detail, so please don’t worry if it’s meaning it’s immediately clear.

To start, let’s divide the code into three parts: initialization, which takes place on lines 0 and 1, the while loop condition, which is on line 2, and the while loop content, which is on lines 3-7. The final line, a closing parenthesis, simply closes the opening parenthesis after do on line 2 (it’s on its own line for the sake of readability since newlines don’t affect how Cake interprets the code).

Regarding the initialization lines (lines 0-1), they establish two variables, left and right. These variables represent indices in the array; left starts at the left (first index) of the array and (in the while loop) repeatedly increments so that it approaches the other end of the array. right starts at the right (last index) of the array and (in the while loop) repeatedly decrements so that it approaches the other end of the array. In other words left and right start at opposite ends of the array and approach each other as the reversing continues.

Now let’s get into the specifics of the initialization — why, in order to accomplish their goals, left and right are initialized to the values they are. left is pretty obvious: the first index of the array is 0. On the other hand, right takes a bit of explanation. Let’s look at the value it’s initialized with:

size(a) returns the size of a, which is 1 more than the last index of a. To see why this is true, think of some specific examples: if a has 1 element, size(a) returns 1 and the last index of a is 0 (since a has only one index) so the size is one more than the last index; if a has 3 elements, size(a) returns 3 and the last index of a is 2 so the size is one more than the last index. You can see that the trend continues no matter how big a gets. So, the last index of a is the size of a minus 1, which is exactly what right is set to.

Up next is the while loop conditional. This is the line that dictates whether or not the code inside the loop gets run. As long as the condition returns true, the code is run; the first time it returns false, Cake skips past the code inside the loop and moves to the next line. The condition here is

As long as the left index is less than the right index, the code is run. When is this true? Well, that depends on the size of a. left gets set to 0 no matter what so if a has a size of 0, right gets set to -1, which is less than 0, meaning the code inside the loop is never run. The same thing happens if the size of a is 1: left is 0 and right is 0, so left isn’t less than right and nothing happens.

The situation becomes more interesting when a has 2 or more elements; at the start, left is 0 and right is 1, which means the condition returns true and the code gets run. Everything inside the parentheses following do gets evaluated once and then the condition is checked again. Notice that at the end of the code inside the loop, left is incremented and right is decremented. That means left becomes 1 and right becomes 0, which makes the condition return false and jump out of the loop.

What if a is a 3-element array? Then left starts at 0 and right starts at 2. The condition obviously returns true the first time it’s checked and then the indices are updated: left becomes 1 and right becomes 1. That means that this time, the condition returns false and we’re done. Does this make sense? Yes, because as we saw before, to reverse a 3-element array, only 1 pair of elements must be swapped: the first and last; the middle element isn’t changed. As we’ll soon see, each time the code inside the loop runs, 1 pair of elements is swapped, so 1 iteration of the loop makes sense. If “iteration” is an unfamiliar word, don’t worry — it just means a run through the loop. If the loop gets evaluated 3 times, that’s 3 iterations.

Finally, let’s look at the 4-element case. This is the first time the loop gets evaluated twice, as expected. left starts at 0 and right starts at 3, so the condition returns true. Next, left becomes 1 and right becomes 2, so the condition returns true again. The next time, however, left becomes 2 and right becomes 1, so we get a false and finish our iterations.

OK, almost there! Let’s tackle the code inside the loop. The last two lines,

have already been discussed. At the end of each iteration, left is incremented and right is decremented, as seen above. This ensures that the outermost elements get swapped, then the elements inside those, etc. all the way to the innermost elements. If there is an odd number of elements, the middle element is never swapped with anything. If there is an even number of elements, every element gets swapped with its appropriate pair.

The only tricky part left is the first three lines in the loop:

This counterintuitive bit of code swaps the values of a[left] and a[right]. You might think swapping could be done more concisely like this:

But this poses a problem! The first line sets a[left] to a[right], which overwrites the original value in a[left]. So when, on the next line, a[right] is set to a[left], a[right] gets set to itself. To see this more clearly, let’s use simpler variables:

After the first line, x and y have the same value, so setting y to x on the second line just sets y to itself — the value of x is lost forever!

Therefore, we need a temporary variable to store the value of x (that is, a[left]) so that y (a[right]) can be set to it on the next line. So the first line,

stores the value in a[left] so that when, on the next line, a[left] is set to a[right], the original value in a[left] is still stored somewhere in the run-time system’s state (specifically, in temp). The final line then sets a[right] to temp, which holds the correct value. Ta-da! The two variables have swapped values. As an aside, temp is no longer needed and will be reset in the next iteration.

So there you have it. Defining reverse with the code discussed above gives you an instruction that correctly reverses the array you give it every time no matter the size of the array. One thing to note is that this instruction overrides the array you give it — after computing reverse(a), a will be the reverse of what it was. This means that reverse changes the system’s state. This is an important aspect of the instruction because if you use a later, you need to remember that it’s been reversed. Next post, we’ll discuss alternative algorithms for reversing arrays and how to reverse arrays without modifying them by creating new arrays on the fly.