Reordering Lists

Sometimes, we care about the order of a list (e.g., in a dictionary) and sometimes it doesn’t matter (e.g., in a shopping list). A very common task for lists is reordering them, either to impose an order that did not exist before (such as sorting a list—alphabetizing a list of names) or changing the ordering (such as reversing a list—taking the alphabetized list of names and making it a reverse-alphabetized list).

At the heart of the matter, reordering a list involves swapping the positions of two items repeatedly:

  • In the case of a reversal, this might entail taking the first item and swapping it with the last, then the second item with the second to last, etc.
  • In the case of sorting a list of names, it might involve taking what should be first (alphabetically) and swapping it with what actually is first, then continuing down the line.

NOTE: Sorting is a very well-studied topic in computer science. The sorting algorithm described above is a “selection sort.” Note the various sorting algorithms described here. “Selection sort” is not the most efficient way to sort a list, but it is the way humans typically manually alphabetize things. How might you apply one of the more efficient algorithms described to physically alphabetizing file folders, books, etc.?

The Trouble with Swapping

Because programs are ordered processes, the order in which events occur matter. What does this have to do with swapping? Well, consider the following algorithm for swapping:

15 32
  1. Copy X to Y.
  2. Copy Y to X.

Seems simple enough until you step through it. After Step 1, our table now looks like this:

15 15

Step 2 now depends on the “old” value of X, which was overwritten. We need to “save” that value somewhere in order to use it later. We cannot save it in Y, because then we’ll have the same problem in reverse. We need a third variable:

X Y SwapSpace
15 32

Using this third variable, write out the steps that would constitute an algorithm for swapping two values.