Comet sorts a hand of cards the way she always has. She picks up one card at a time and slides it into place among the cards she is already holding.
"That is not selection sort," Wren says, watching. "You never search for the smallest."
"It works, though," Comet says. "What does the evidence say about that?"
Wren laughs at his own question coming back at him. Nova projects a row of cards, with larger cards sliding right to open a gap. "How can I help?" she asks. "Count the shifts as well as the comparisons."
Comet fans her cards toward you. "Lead programmer, show us what my hands are doing."
Insertion sort takes the next item from the unsorted part. It shifts larger items of the sorted part one place right to make room. Then it drops the item into the gap.
The place is correct for now, but not always final. A smaller item that comes later can still push it right.
def insertion_sort(nums):
for i in range(1, len(nums)):
current = nums[i]
j = i - 1
while j >= 0 and nums[j] > current:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = current # insertion_passes.py
# A copy of insertion_sort that prints the list after each item is placed.
def insertion_passes(nums):
for i in range(1, len(nums)):
current = nums[i]
j = i - 1
while j >= 0 and nums[j] > current:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = current
print("place", current, nums)
insertion_passes([42, 18, 65, 7, 30]) | i | current | Sorted part before | Shifted right | List after |
|---|---|---|---|---|
| 1 | 18 | 42 | 42 | [18, 42, 65, 7, 30] |
| 2 | 65 | 18, 42 | nothing | [18, 42, 65, 7, 30] |
| 3 | 7 | 18, 42, 65 | 65, 42, 18 | [7, 18, 42, 65, 30] |
| 4 | 30 | 7, 18, 42, 65 | 65, 42 | [7, 18, 30, 42, 65] |
place 18 [18, 42, 65, 7, 30] place 65 [18, 42, 65, 7, 30] place 7 [7, 18, 42, 65, 30] place 30 [7, 18, 30, 42, 65]
This counting copy runs insertion sort on the catalog grams, then again on the list it just sorted. Made-up data from the FieldSim story.
# count_insertion.py
# A copy of insertion_sort that counts comparisons.
from field_data import CATALOG
def insertion_count(nums):
"""Sorts nums in place and gives back the number of comparisons."""
comparisons = 0
for i in range(1, len(nums)):
current = nums[i]
j = i - 1
while j >= 0:
comparisons += 1
if nums[j] > current:
nums[j + 1] = nums[j]
j -= 1
else:
break
nums[j + 1] = current
return comparisons
grams = []
for label, kind, g in CATALOG:
grams.append(g)
print(insertion_count(grams))
print(grams)
print(insertion_count(grams)) 28 [7, 12, 18, 25, 30, 39, 42, 51, 65, 88] 9
| List | Selection sort comparisons | Insertion sort comparisons |
|---|---|---|
| Catalog grams (unsorted) | 45 | 28 |
| Already sorted | 45 | 9 |
This is the run for step 3, in a short file with the same mistake.
# insertion_oops.py
def insertion_oops(nums):
for i in range(1, len(nums)):
current = nums[i]
j = i - 1
while j >= 0 and nums[j] > current:
nums[j + 1] = nums[j]
j -= 1
nums[j] = current
nums = [42, 18, 65, 7, 30]
insertion_oops(nums)
print(nums) [42, 42, 42, 65, 7]
| Statement | True or false? |
|---|---|
| Insertion sort shifts larger items right to make room. | ? |
| Insertion sort puts each item in its final place straight away. | ? |
| On a sorted list, insertion sort did fewer comparisons than selection sort. | ? |
| Both sorts made the same number of comparisons on the catalog grams. | ? |
Same five numbers, a different way to sort them, and a very different count. Tomorrow you sort Sample objects.