Nested loops

You’ve already seen that, for example, a while-loop might contain an if-statement. (Not an “if-loop,” right?) A while-loop can also contain another while-loop. This structure is called a nested loop, since one loop, the inner loop, is “nested” inside of another “larger” loop, the outer loop. Here’s an example to print out a times table.

What’s this += business? In Python, you can combine a binary operator, such as +, -, *, /, or % with assignment, using the combination operators +=, -=, *=, /=, and %=. The pattern is variable op= expression, which is the same as variable = variable op expression, where op is any of the five binary operators above, variable is a variable, and expression is any expression that can be an operand of op. So to multiply money by 10 and store the result back into money, you can write money *= 10.

The call to print_justified prints each character within a string of length three even if the number has only one digit. The string is right justified, so that the spaces that pad the string out to three digits go on the left. In this way, the columns of the table line up so that the table is easy to read.

Let’s step through what happens.

  1. Set row to the value 1.
  2. If row < 10 evaluates to True, go to the line after while row < 10.
  3. OK, 1 < 10 evaluates to True.
  4. Set column to 1.
  5. column < 10 is True. Go to the next line.
  6. Print row * column, with some fancy formatting. So print 1.
  7. Add 1 to the value in column, so that column now equals 2.
  8. column < 10 is True. Go to the next line.
  9. Print row * column, with some fancy formatting. So print 2.
  10. Add 1 to the value in column, so that column now equals 3.
  11. column < 10 is True. Go to the next line.
  12. Eventually, column equals 9, and we add 1 to the value in column, givin 10.
  13. Now column < 10 is False. We have completed all iterations of the inner loop when row equals 1.
  14. Add 1 to the value in row, so that row now equals 2.
  15. Set column to 1.
  16. Do all the iterations of the inner loop, with the value of column running from 1 to 9, printing the second row of the table.
  17. Add 1 to the value in row, so that row now equals 3.
  18. Set column to 1.
  19. Do all the iterations of the inner loop, with the value of column running from 1 to 9, printing the third row of the table.
  20. Eventually, row equals 9, and we add 1 to the value in row, giving 10.
  21. Now row < 10 is False, and we drop out of the outer loop.

What we see is that for each iteration of the outer loop, all iterations of the inner loop occur. Since the outer loop iterates 9 times, and the inner loop iterations 9 times per outer-loop iteration, the total number of inner-loop iterations is 9 × 9, or 81.

Nested loops will eventually be very familiar and comfortable to you, but they can be tricky at first. Here’s what I recommend. Get an index card. Use it to cover all lines below the current line (the line the program counter is pointing at). Step through the code one line at a time until you are comfortable with it.

Exercise: stepping through

Here is some code:

Step through the code by hand. In the text box below, at each step, write down the value of the program counter (which line the program is on), the names and values of each variable. Press the blue arrow button when done.

Here is a solution. No peeking until you have solved it yourself!

Nested for-loops

You can often use for-loops to make code easier to read. The following code with nested for-loops prints out the same table as the example above.

In this case, you don’t have to explicitly add to row or column, or reset their values, since stepping through the lists created by the range function takes care of these details. If you wanted to print out a times table that showed only products of even numbers (though I have no idea why you want to do that), it would be harder to use for-loops, since range always gives sequential integers.

A good rule of thumb is to use a for-loop if the for-loop is easier to read than the corresponding while-loop, and if the goal of the loop is to iterate over some all values in a list (or some values for which you can easily construct a list).

Selection sort

On the first day, I gave an example of how quickly you could find a name in a phone book using a process called binary search. Tear the book in half. If the name you want is before the middle, keep the first half and throw away the second half. If the name you want is after the middle, keep the second half instead. Repeat, starting with the tear operation, until you have found the name or run out of pages.

Binary search was much faster than looking through every name in sequence. But binary search relied on knowing that the book was already sorted. Let’s look at a method for sorting a list of items. This is not the most efficient possible method in all cases; we’ll see other methods later.

The method we will look at now is called selection sort. We’re looking at selection sort because sorting a list is sometimes useful, and second, because it is an example of an algorithm design problem that uses a list. Selection sort works like this. Let n be the length of the list.

  1. Find the smallest item in the list. Swap it into position 0 (the item at index 0).
  2. Find the second-smallest item in the list. Because we’ve already put the smallest item into position 0, the second-smallest item must be somewhere in positions 1 through n − 1. Swap the second-smallest item into position 1.
  3. Find the third-smallest item in the list, which must be somewhere in positions 2 through n − 1. Swap it into position 2.
  4. Stop when we have swapped the second-largest item into the second-to-last position (at index n − 2).
  5. Only one item remains. It must be the largest item, and it must be in the last position (at index n − 1). We don’t need to do anything more.

You can see a PowerPoint demo in selection_sort.pptx.

Here is the code for selection sort.

Exercise: factoring selection sort

Objective: Factor out the inner loop of a while loop.

Factoring code is the process by which common operations are recognized and moved into functions, to increase readability and the possibility of re-use of code. In selection sort, the inner loop finds the smallest value in the list, starting at some index. Write a function find_min_in_sublist(list, start) that returns the index of the smallest value in a list at or after index start. Then use a call to that function to replace the inner loop of selection sort.

Here is a solution. No peeking until you have solved it yourself!