← Back to course
Code Crew G5 / Week 08 / Friday
5/6
Week 08 · Sorting by hand

Friday

Sort, then search
// Selection sort and sorted()
⏱ about 15 min

Friday: Sort, then search

Mission Control wants the star records ranked from faintest to brightest.

"But each record is a dictionary," Rocket says. "How does sorted() know what to compare?"

Raven points at one record. "What do you notice that every record has?"

"A glow number!" Rocket says. "We want to sort by that."

Nova glows brighter. "Here is a hint. You can give sorted() a function that picks the value to compare."

Sorting records with a key

A key function takes one record and returns the value to sort by. Then sorted() calls it on every record.

catalog = [
    {"name": "Ember", "glow": 4},
    {"name": "Frost", "glow": 9},
    {"name": "Glow", "glow": 2},
    {"name": "Halo", "glow": 7},
]

def by_glow(star):
    return star["glow"]

ranked = sorted(catalog, key=by_glow)
for star in ranked:
    print(star["name"], star["glow"])
Output:
Glow 2
Ember 4
Halo 7
Frost 9
CHANGE THE PROGRAM.
  • Read the question.
  • Tap your answer.
With key=by_glow and reverse=True, which star prints first?
A new key function returns star["name"]. Which star prints first?

Sort once, search many times

Sorting takes work. But after one sort, every search can use fast binary search.

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

ids = [30, 3, 21, 8, 36, 12, 27, 15]
ids.sort()
print(ids)
print(binary_search(ids, 36))
Output:
[3, 8, 12, 15, 21, 27, 30, 36]
7
PUT THE STEPS IN ORDER TO FIND STAR IDS QUICKLY IN A JUMBLED LIST.
  • ?Binary search for the first target
  • ?Binary search for the next target
  • ?Get the jumbled list of IDs
  • ?Sort the list once
WHY THIS EXERCISESorting once lets every later search take the fast route.
StatementTrue or false?
A key function returns the value to sort by.?
Last week, binary search failed on the jumbled IDs. Sorting them first fixes that.?
You must sort again before every single search.?
WHY THIS EXERCISEA sorted list stays sorted until you change it.

Practice lab: rank the moons

moons = [
    {"name": "Cove", "size": 5},
    {"name": "Ash", "size": 3},
    {"name": "Bay", "size": 8},
]

def by_size(moon):
    return moon["size"]

def by_name(moon):
    return moon["name"]

for moon in sorted(moons, key=by_size):
    print(moon["name"])
for moon in sorted(moons, key=by_name, reverse=True):
    print(moon["name"])
How many lines print in all?
What is the first line?
What is the fourth line?
What is the last line?
KEY CHECK
  • Read the question.
  • Tap your answer.
What does a key function return?
With key=by_size and reverse=True, which moon prints first?
Does sorted(moons, key=by_size) change moons?
StatementTrue or false?
by_name sorts the moons A to Z.?
The first loop prints Ash, Cove, Bay.?
A key function must return a name.?
After sorting, binary search can find items fast.?
WHY THIS EXERCISEAny value that can be compared can be a key.
ids is [9, 4, 6]. After ids.sort(), what does binary_search(ids, 9) return?
WHY THIS EXERCISE9 sits in spot 2 of the sorted list.

Week 8 complete! You sorted by hand, by code and with Python's own tools. Next week we meet a faster sort that uses recursion.

← Thursday