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.
row to the value 1.row < 10 evaluates to True, go to the line after while row < 10.True.column to 1.column < 10 is True. Go to the next line.row * column, with some fancy formatting. So print 1.column, so that column now equals 2.column < 10 is True. Go to the next line.row * column, with some fancy formatting. So print 2.column, so that column now equals 3.column < 10 is True. Go to the next line.column equals 9, and we add 1 to the value in column, givin 10.column < 10 is False. We have completed all iterations of the inner loop when row equals 1.row, so that row now equals 2.column to 1.column running from 1 to 9, printing the second row of the table.row, so that row now equals 3.column to 1.column running from 1 to 9, printing the third row of the table.row equals 9, and we add 1 to the value in row, giving 10.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.
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!