2 Swapping

Programs commonly need to swap the contents of two variables. While this probably seems simple at first glance, it’s actually a little more complicated than it seems.

Motivation

Suppose, for example, that you are writing a fantasy role playing game. In such games, players commonly acquire items of various kinds (e.g., weapons, spells, gold, food). When they acquire such an item, a representation of it (e.g., a 'T' character for a teleportation spell) is assigned to a variable of appropriate type (e.g., a char variable named spell). As the game progresses, two players meet and realize that it would benefit both of them to swap their spells. This chapter considers a sequence of statements that can be used to solve this problem.

Review

There are a couple of things to recall in this regard. First, remember that the assignment operator (i.e., the = operator), stores the right side operand in the memory location identified by the left side operand. So, the statements in the following fragment:

        char swordOfAlice, swordOfBetty;
        
        swordOfAlice = 'C'; // Caladbolg
        swordOfBetty = 'D'; // Durendal

can be visualized as in Figure 2.1. The first assignment statement stores the binary representation of the character 'C' (i.e., 01000011 using an ASCII representation) into the memory location identified by swordOfAlice and the second assignment statement stores the binary representation of the character 'D' (i.e., 01000100 using an ASCII representation) into the memory location identified by swordOfAlice.

image
Figure 2.1. A Visualization of Two Assignment Statements

Second, remember that a variable can hold only one “thing” (either a value or a reference, depending on the type of the variable). So, the statements in the following fragment:

        swordOfAlice = swordOfBetty;
        swordOfBetty = swordOfAlice;

can be visualized as in Figure 2.2. The first assignment statement stores the current contents[1] of swordOfBetty (i.e., a 'D') in the memory location identified by swordOfAlice. The second assignment statement stores the current contents of swordOfAlice (i.e., now a 'D') in the memory location identified by swordOfBetty. In other words, these statements didn’t swap the contents of the two variables at all. Instead, the memory locations identified by both variables now contain a binary representation of the character 'D'.

image
Figure 2.2. A Defective Swapping Algorithm

Thinking About The Problem

One way to think about solving the swapping problem is to imagine a situation in which you have Caladbolg in your left hand and Durendal in your right hand and you now want to swap the two. Since both of your hands are already full, there’s no way for you to make any progress. To make progress, you need a place where you can temporarily store one of the swords. For example, you can place Caladbolg on a table, move Durendal from your right hand to your left hand, and then pick up Caladbolg with your right hand.

Note that this situation is not completely analogous to the way assignment works because the assignment operator replaces the current contents of the memory identified by a variable with a copy of the right side operand. However, it does provide the foundation of a pattern that can be used to solve the swapping problem.

The Pattern

Suppose you want to swap the contents of two memory locations identified by a and b (or, more succinctly, suppose you want to swap the contents of two variables, a and b). Before starting, you need a memory location that can be used to temporarily store the contents of either a or b. Calling that variable temp, the swapping pattern can then be implemented as follows:

        temp = a;
        a = b;
        b = temp;

The process can be visualized as in Figure 2.3. In step 1, the contents of a is temporarily stored in the memory location identified by temp. In step 2, the contents of b is stored in the memory location identified by a. Finally, in step 3, the contents of temp is stored in the memory location identified by b.

Figure 2.3. A Visualization of the Swapping Pattern

Examples

It’s instructive to use the pattern to swap swords, carefully illustrating what happens step by step. The statements needed to conduct the swap are contained in the following fragment:

        temp = swordOfAlice;        
        swordOfAlice = swordOfBetty;
        swordOfBetty = temp;

Before the swap, the memory location identified by swordOfAlice contains the character 'C', the memory location identified by swordOfBetty contains the character 'D', and the memory location identified by temp doesn’t contain anything (or contains “garbage”, depending on your perspective). This is illustrated in Figure 2.4a.

image
Figure 2.4. Steps in a Swap

In step 1, the contents of swordOfAlice is assigned to temp. Hence, both temp and swordOfAlice now contain a 'C'. The assignment statement and its result are illustrated in Figure 2.4b. In step 2, the contents of swordOfBetty is assigned to swordOfAlice. Hence, both swordOfAlice and swordOfBetty now contain a 'D'. The assignment statement and its result are illustrated in Figure 2.4c. In step 3, the contents of temp is assigned to swordOfBetty. Hence, both swordOfBetty and temp now contain a 'C'. The assignment statement and its result are illustrated in Figure 2.4d. The result is that, as desired, swordOfAlice now contains a 'D' and swordOfBetty now contains a 'C'.

A Warning

At this point, if you know about methods, you might be tempted to write a swap() method so that you don’t have to duplicate this code every time you want to swap the contents of two variables. However, though your motivations are to be applauded, it would be ill-advised to do so.

It turns out that there are different ways to pass parameters to methods, and the approach used in a particular language has a dramatic impact on the way in which one should implement a swap() method (and, indeed, whether it’s even possible to do so). So, until you fully understand parameter passing, you may need to have duplicate code in your programs. That said, be careful — it’s easy to make subtle mistakes when you cut and paste code fragments and then rename variables.


  1. The use of the plural noun "contents" rather than "content" may be a little confusing to some readers. Though a variable holds a single thing, it is a kind of container, and we normally talk about the "contents" of a container.

License

Icon for the Creative Commons Attribution 4.0 International License

Patterns for Beginning Programmers by David Bernstein is licensed under a Creative Commons Attribution 4.0 International License, except where otherwise noted.

Share This Book