Sorting
Now, let’s look at a slightly more complex problem. The following table shows the number of acres burned in forest fires in Canada from 1918 to 1987. What were the worst years?
| 563 | 7590 | 1708 | 2142 | 3323 | 6197 | 1985 | 1316 | 1824 | 472 |
| 1346 | 6029 | 2670 | 2094 | 2464 | 1009 | 1475 | 856 | 3027 | 4271 |
| 3126 | 1115 | 2691 | 4253 | 1838 | 828 | 2403 | 742 | 1017 | 613 |
| 3185 | 2599 | 2227 | 896 | 975 | 1358 | 264 | 1375 | 2016 | 452 |
| 3292 | 538 | 1471 | 9313 | 864 | 470 | 2993 | 521 | 1144 | 2212 |
| 2212 | 2331 | 2616 | 2445 | 1927 | 808 | 1963 | 898 | 2764 | 2073 |
| 500 | 1740 | 8592 | 10856 | 2818 | 2284 | 1419 | 1328 | 1329 | 1479 |
One way to find out how much forest was destroyed in the N worst years is to sort the list and then take the last N values, as shown in the following code:
| | def find_largest(n: int, L: list) -> list: |
| | """Return the n largest values in L in order from smallest to largest. |
| | |
| | >>> L = [3, 4, 7, -1, 2, 5] |
| | >>> find_largest(3, L) |
| | [4, 5, 7] |
| | """ |
| | |
| | copy = sorted(L) |
| | return copy[-n:] |
This algorithm is short, clean, and easy to understand, but it relies on a bit of black magic. How do the function sorted and the method list.sort work? And how efficient are they?
Looking at how an algorithm’s running time grows with the input’s size is the standard way to analyze and compare efficiency
It turns out that many sorting algorithms have been developed over the years, each with its strengths and weaknesses. They can be divided into two categories: those that are simple but inefficient, and those that are efficient but more difficult to understand and implement. Let’s examine two of the former kind. The rest rely on more advanced techniques; you’ll see one of these, rewritten to use only the material seen so far.
Both of the simple sorting algorithms keep track of two sections in the list being sorted. The section at the front contains values that are now in sorted order; the section at the back contains values that have yet to be sorted. Here is the main part of the invariant that you can use for your two simple sorts:
One of the two algorithms has an additional property in its invariant: the items in the sorted section must be smaller than all the items in the unknown section.
Both of these sorting algorithms will work their way through the list, making the sorted section one item longer on each iteration. You’ll see that there are two ways to do this. Here is an outline for your code:
| | i = 0 # The index of the first unknown item in lst; lst[:i] is sorted |
| | while i != len(L): |
| | # Do something to incorporate L[i] into the sorted section |
| | |
| | i += 1 |
Most Python programmers would probably write the loop header as for i in range(len(L)) rather than incrementing i explicitly in the loop body. Let’s do the latter here to explicitly initialize i (to set up the loop invariant) and to show the increment separately from the work this particular algorithm is doing. The “do something…” part is where the two simple sorting algorithms will differ.
Selection Sort
Selection sort works by searching the unknown section for the smallest item and moving it to the index i. Here is your algorithm:
| | i = 0 # The index of the first unknown item in lst |
| | |
| | # lst[:i] is sorted and those items are smaller than those in list[i:] |
| | while i != len(L): |
| | # Find the index of the smallest item in lst[i:] |
| | # Swap that smallest item with the item at index i |
| | i += i |
As you can probably guess from this description, selection sort works by repeatedly selecting the smallest item in the unsorted section and placing it just after the sorted section. This method works because the items are selected in order. In the first iteration, i is 0, and lst[0:] refers to the entire list. That means that in the first iteration, select the smallest item and move it to the front. In the second iteration, select the second-smallest item and move it to the second spot, and so on:
The file named sorts.py contains a selection sort function, partially in English, as shown in the following code:
| | def selection_sort(L: list) -> None: |
| | """Reorder the items in L from smallest to largest. |
| | |
| | >>> L = [3, 4, 7, -1, 2, 5] |
| | >>> selection_sort(L) |
| | >>> L |
| | [-1, 2, 3, 4, 5, 7] |
| | """ |
| | |
| | i = 0 |
| | while i != len(L): |
| | # Find the index of the smallest item in L[i:] |
| | # Swap that smallest item with L[i] |
| | i += 1 |
You can replace the second comment with a single line of code.
| | def selection_sort(L: list) -> None: |
| | """Reorder the items in L from smallest to largest. |
| | |
| | >>> L = [3, 4, 7, -1, 2, 5] |
| | >>> selection_sort(L) |
| | >>> L |
| | [-1, 2, 3, 4, 5, 7] |
| | """ |
| | |
| | i = 0 |
| | while i != len(L): |
| | # Find the index of the smallest item in L[i:] |
| | L[i], L[smallest] = L[smallest], L[i] |
| | i += 1 |
Now, all that’s left is finding the index of the smallest item in L[i:]. This is complex enough that it’s worth making it a function:
| | def find_min(L: list, b: int) -> int: |
| | """Return the index of the smallest value in L[b:]. |
| | |
| | Precondition: L[b:] is not empty. |
| | |
| | >>> find_min([3, -1, 7, 5], 0) |
| | 1 |
| | >>> find_min([3, -1, 7, 5], 1) |
| | 1 |
| | >>> find_min([3, -1, 7, 5], 2) |
| | 3 |
| | """ |
| | |
| | smallest = b # The index of the smallest so far. |
| | i = b + 1 |
| | while i != len(L): |
| | if L[i] < L[smallest]: |
| | # We found a smaller item at L[i]. |
| | smallest = i |
| | |
| | i += 1 |
| | |
| | return smallest |
| | |
| | def selection_sort(L: list) -> None: |
| | """Reorder the items in L from smallest to largest. |
| | |
| | >>> L = [3, 4, 7, -1, 2, 5] |
| | >>> selection_sort(L) |
| | >>> L |
| | [-1, 2, 3, 4, 5, 7] |
| | """ |
| | |
| | i = 0 |
| | while i != len(L): |
| | smallest = find_min(L, i) |
| | L[i], L[smallest] = L[smallest], L[i] |
| | i += 1 |
The function find_min examines each item in L[b:], keeping track of the index of the minimum item so far in variable smallest. Whenever it finds a smaller item, it updates smallest. Because it is returning the index of the smallest value, it won’t work if L[b:] is empty; hence the precondition.
This operation is complicated enough that a couple of doctests may not be sufficient to test it thoroughly. Here’s a list of test cases for sorting:
- An empty list
- A list of length 1
- A list of length 2 (this is the shortest case where items can move)
- An already-sorted list
- A list with all the same values
- A list with duplicates
Here are your expanded doctests:
| | def selection_sort(L: list) -> None: |
| | """Reorder the items in L from smallest to largest. |
| | |
| | >>> L = [3, 4, 7, -1, 2, 5] |
| | >>> selection_sort(L) |
| | >>> L |
| | [-1, 2, 3, 4, 5, 7] |
| | >>> L = [] |
| | >>> selection_sort(L) |
| | >>> L |
| | [] |
| | >>> L = [1] |
| | >>> selection_sort(L) |
| | >>> L |
| | [1] |
| | >>> L = [2, 1] |
| | >>> selection_sort(L) |
| | >>> L |
| | [1, 2] |
| | >>> L = [1, 2] |
| | >>> selection_sort(L) |
| | >>> L |
| | [1, 2] |
| | >>> L = [3, 3, 3] |
| | >>> selection_sort(L) |
| | >>> L |
| | [3, 3, 3] |
| | >>> L = [-5, 3, 0, 3, -6, 2, 1, 1] |
| | >>> selection_sort(L) |
| | >>> L |
| | [-6, -5, 0, 1, 1, 2, 3, 3] |
| | """ |
| | |
| | i = 0 |
| | |
| | while i != len(L): |
| | smallest = find_min(L, i) |
| | L[i], L[smallest] = L[smallest], L[i] |
| | i += 1 |
As with binary search, the doctest is so long that, as documentation for the function, it obscures rather than helps clarify. Again, you’ll see how to fix this in Chapter 15, .
Insertion Sort
Like selection sort, insertion sort keeps a sorted section at the beginning of the list. Rather than scan all of the unsorted section for the next smallest item, though, it takes the next item from the unsorted section—the one at index i—and inserts it where it belongs in the sorted section, increasing the size of the sorted section by one.
| | i = 0 # The index of the first unknown item in lst; lst[:i] is sorted |
| | |
| | while i != len(L): |
| | # Move the item at index i to where it belongs in lst[:i + 1] |
| | |
| | i += 1 |
The reason you should use lst[i + 1] is that the item at index i may be larger than all the items in the sorted section. If that is the case, then the current item won’t move:
| | def insertion_sort(L: list) -> None: |
| | """Reorder the items in L from smallest to largest. |
| | |
| | >>> L = [3, 4, 7, -1, 2, 5] |
| | >>> insertion_sort(L) |
| | >>> L |
| | [-1, 2, 3, 4, 5, 7] |
| | """ |
| | |
| | i = 0 |
| | while i != len(L): |
| | # Insert L[i] where it belongs in L[0:i+1]. |
| | i += 1 |
The approach is the same as in selection sort; the difference lies in the comment within the loop. Like you did with selection sort, let’s write a helper function to do the work:
| | def insert(L: list, b: int) -> None: |
| | """Precondition: L[0:b] is already sorted. |
| | Insert L[b] where it belongs in L[0:b + 1]. |
| | |
| | >>> L = [3, 4, -1, 7, 2, 5] |
| | >>> insert(L, 2) |
| | >>> L |
| | [-1, 3, 4, 7, 2, 5] |
| | >>> insert(L, 4) |
| | >>> L |
| | [-1, 2, 3, 4, 7, 5] |
| | """ |
| | |
| | # Find where to insert L[b] by searching backwards from L[b] |
| | # for a smaller item. |
| | i = b |
| | while i != 0 and L[i - 1] >= L[b]: |
| | i -= 1 |
| | |
| | # Move L[b] to index i, shifting the following values to the right. |
| | value = L[b] |
| | del L[b] |
| | L.insert(i, value) |
| | |
| | def insertion_sort(L: list) -> None: |
| | """Reorder the items in L from smallest to largest. |
| | |
| | >>> L = [3, 4, 7, -1, 2, 5] |
| | >>> insertion_sort(L) |
| | >>> L |
| | [-1, 2, 3, 4, 5, 7] |
| | """ |
| | |
| | i = 0 |
| | |
| | while i != len(L): |
| | insert(L, i) |
| | i += 1 |
Selection sort and insertion sort differ only by how they make progress
How does insert work? It works by finding out where L[b] belongs and then relocating it. Where does it belong? It belongs after every value less than or equal to it and before every value that is greater than it. You need the check i != 0 in case L[b] is smaller than every value in L[0:b], which will place the current item at the beginning of the list. This code passes all the tests written earlier for selection sort. The following diagram illustrates the process: illustrates the process.
Performance
You now have two sorting algorithms. Which should you use? Because neither is too difficult to understand, it’s reasonable to decide based on how fast they are.
It’s easy enough to write a program to compare their running times, along with that for list.sort:
| | import time |
| | import random |
| | from sorts import selection_sort |
| | from sorts import insertion_sort |
| | |
| | def built_in(L: list) -> None: |
| | """Call list.sort --- we need our own function to do this so that we can |
| | treat it as we treat our own sorts. |
| | """ |
| | |
| | L.sort() |
| | |
| | def print_times(L: list) -> None: |
| | """Print the number of milliseconds it takes for selection sort, insertion |
| | sort, and list.sort to run. |
| | """ |
| | |
| | print(len(L), end='\t') |
| | for func in (selection_sort, insertion_sort, built_in): |
| | if func in (selection_sort, insertion_sort) and len(L) > 10000: |
| | continue |
| | |
| | L_copy = L[:] |
| | t1 = time.perf_counter() |
| | func(L_copy) |
| | t2 = time.perf_counter() |
| | print("{0:7.1f}".format((t2 - t1) * 1000.), end='\t') |
| | |
| | print() # Print a newline. |
| | |
| | for list_size in [10, 1000, 2000, 3000, 4000, 5000, 10000]: |
| | L = list(range(list_size)) |
| | random.shuffle(L) |
| | print_times(L) |
Here are the results:
| List Length | Selection Sort | Insertion Sort | list.sort |
|---|---|---|---|
| 1000 | 29 | 14 | 0.1 |
| 2000 | 117 | 59 | 0.2 |
| 3000 | 264 | 135 | 0.3 |
| 4000 | 471 | 239 | 0.4 |
| 5000 | 730 | 362 | 0.5 |
| 10000 | 2979 | 1477 | 1.3 |
Something is clearly wrong, as your sorting functions are thousands of times slower than the built-in function. What’s more, the time required by your routines is growing faster than the size of the data. On a thousand items, for example, selection sort takes about 0.03 milliseconds per item, but on ten thousand items, it needs about 3 milliseconds per item—far more than a tenfold increase! What is going on?
To answer this, examine what happens in the inner loops of your two algorithms. In the first iteration of selection sort, the inner loop examines every element to find the smallest one. In the second iteration, it examines all but one; in the third, it examines all but two, and so on.
The average running
time of simple sorting algorithms is
proportional to N*N
If there are N items in the list, then the number of iterations of the inner loop, in total, is roughly N + (N - 1) + (N - 2) + … + 1, or N*(N + 1)/2. Putting it another way, the number of steps required to sort N items is roughly proportional to N2 + N. For large values of N, you can ignore the second term and say that the time needed by selection sort grows as the square of the number of values being sorted. Indeed, examining the timing data further reveals that doubling the list size increases the running time by a factor of four.
The same analysis can be applied to insertion sort, as it also examines one element on the first iteration, two on the second, and so on. (It’s just examining the already sorted values rather than the unsorted values.)
So why is insertion sort slightly faster? The reason is that, on average, only half of the values need to be scanned to find the location in which to insert the new value. In contrast, with selection sort, every value in the unsorted section needs to be examined to select the smallest one. But, wow, list.sort is significantly faster!
