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.

- Set
`row`

to the value 1. - If
`row < 10`

evaluates to`True`

, go to the line after`while row < 10`

. - OK, 1 < 10 evaluates to
`True`

. - Set
`column`

to 1. `column < 10`

is`True`

. Go to the next line.- Print
`row * column`

, with some fancy formatting. So print 1. - Add 1 to the value in
`column`

, so that`column`

now equals 2. `column < 10`

is`True`

. Go to the next line.- Print
`row * column`

, with some fancy formatting. So print 2. - Add 1 to the value in
`column`

, so that`column`

now equals 3. `column < 10`

is`True`

. Go to the next line.- …
- Eventually,
`column`

equals 9, and we add 1 to the value in`column`

, givin 10. - Now
`column < 10`

is`False`

. We have completed all iterations of the inner loop when`row`

equals 1. - Add 1 to the value in
`row`

, so that`row`

now equals 2. - Set
`column`

to 1. - 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. - Add 1 to the value in
`row`

, so that`row`

now equals 3. - Set
`column`

to 1. - 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. - …
- Eventually,
`row`

equals 9, and we add 1 to the value in`row`

, giving 10. - 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.

Here is some code:

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

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).

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.

- Find the smallest item in the list. Swap it into position 0 (the item at index 0).
- 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. - Find the third-smallest item in the list, which must be somewhere in positions 2 through
*n*− 1. Swap it into position 2. - …
- Stop when we have swapped the second-largest item into the second-to-last position (at index
*n*− 2). - 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.

**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!