Rocket sorts cards for Nova and keeps a tally. Every time he checks two cards, he makes a mark.
"Ten marks for five cards," Rocket says. "Is that always the number?"
Raven sorts five cards that are already in order. She makes marks too. "What do you notice about my tally?"
"It is ten again! Even though nothing moved," Rocket says.
Nova blinks. "Here is a hint. Count how many cards each pass looks at."
A comparison checks two cards to see which is smaller. To find the smallest of 5 cards, you need 4 comparisons.
Pass 1 looks at 5 cards, so 4 comparisons. Pass 2 looks at 4 cards, so 3. Then 2, then 1.
| Pass | Cards looked at | Comparisons |
|---|---|---|
| 1 | 5 | 4 |
| 2 | 4 | 3 |
| 3 | 3 | 2 |
| 4 | 2 | 1 |
| Total | 10 |
Selection sort always makes the same number of comparisons for the same number of cards. It checks every unsorted card each pass, even when the list is already sorted.
A real swap is when two different cards trade places. If the smallest card is already in its spot, nothing moves.
| Starting cards | Real swaps |
|---|---|
| 7, 3, 9, 1, 5 | 2 |
| 1, 2, 3, 4, 5 | 0 |
| 5, 4, 3, 2, 1 | 2 |
| Statement about selection sort | True or false? |
|---|---|
| A list that is already sorted needs 0 comparisons. | ? |
| A list that is already sorted needs 0 real swaps. | ? |
| Sorting 10 cards takes more comparisons than sorting 5. | ? |
def count_comparisons(items):
n = len(items)
count = 0
for i in range(n - 1):
for j in range(i + 1, n):
count = count + 1
return count
print(count_comparisons([7, 3, 9, 1, 5]))
print(count_comparisons([1, 2, 3, 4, 5]))
print(count_comparisons([4, 2, 8, 6, 1, 3])) | Statement | True or false? |
|---|---|
| count_comparisons ignores the values in the list. | ? |
| A reversed list needs more comparisons than a sorted one. | ? |
| 7 cards need 21 comparisons. | ? |
| The number of swaps can change with the starting order. | ? |
Nice counting! Tomorrow we turn the card method into Python code.