Python · Syntax · Intermediate

Sorting and custom comparators

10 tasks

sorted() and list.sort() with key= functions, reverse, and multi-key comparators.

Quick topic start and explanations before exercises (exercises below):

sorted() vs list.sort(), key=, reverse=, and sort stability

#
Python has two built-in sort functions. The difference matters: ```python nums = [3, 1, 4, 1, 5] sorted(nums) # [1, 1, 3, 4, 5] — returns a NEW list, nums unchanged nums.sort() # modifies nums IN PLACE, returns None # Common mistake: result = nums.sort() # result is None ! ``` Use `sorted()` when you need the original preserved, or when the input is any iterable (not just a list). Use `.sort()` when you want to sort in place and save memory. **Reverse** ```python sorted([3, 1, 2], reverse=True) # [3, 2, 1] [3, 1, 2].sort(reverse=True) # in place: [3, 2, 1] # Alternative using reversed() — returns an iterator, not a list list(reversed(sorted([3, 1, 2]))) # [3, 2, 1] ``` **key= — sort by a derived value** The `key` function is called once per element, and the result is used for comparison: ```python words = ['banana', 'fig', 'apple', 'cherry'] sorted(words, key=len) # ['fig', 'apple', 'banana', 'cherry'] sorted(words, key=str.lower) # case-insensitive alphabetical sorted(words, key=lambda w: w[-1]) # by last character ``` **Stability — equal elements keep their original order** Python's sort is *stable*: if two elements compare equal, they appear in the same relative order as they were in the input. This is guaranteed — not an implementation detail. ```python students = [ {'name': 'Alice', 'grade': 'B'}, {'name': 'Bob', 'grade': 'A'}, {'name': 'Carol', 'grade': 'B'}, ] by_grade = sorted(students, key=lambda s: s['grade']) # [Bob(A), Alice(B), Carol(B)] # Alice comes before Carol even after sorting by grade, # because they were in that order originally. ``` Stability matters for multi-key sorting: sort by secondary key first, then by primary key — stability preserves the secondary order within equal primaries. ```python # Sort by grade (primary), then by name (secondary) step1 = sorted(students, key=lambda s: s['name']) # sort by name first step2 = sorted(step1, key=lambda s: s['grade']) # then by grade (stable!) # Result: within the same grade, students are alphabetical ```

Tuple keys, operator.itemgetter, and multi-field sorting

#
**Tuple keys — multi-field sort in one pass** When the key function returns a tuple, Python compares element by element — first field first, second field as tiebreaker: ```python students = [ {'name': 'Alice', 'grade': 'B', 'age': 22}, {'name': 'Bob', 'grade': 'A', 'age': 20}, {'name': 'Carol', 'grade': 'B', 'age': 21}, ] # Primary: grade ascending, secondary: age ascending sorted(students, key=lambda s: (s['grade'], s['age'])) # [Bob(A,20), Carol(B,21), Alice(B,22)] ``` **operator.itemgetter and operator.attrgetter** For common cases, `operator` module functions are cleaner and slightly faster than lambdas: ```python from operator import itemgetter, attrgetter # Sort list of dicts by a key sorted(students, key=itemgetter('grade')) # same as lambda s: s['grade'] sorted(students, key=itemgetter('grade', 'age')) # multi-field with one call # Sort objects by attribute from dataclasses import dataclass @dataclass class Person: name: str age: int people = [Person('Alice', 30), Person('Bob', 25), Person('Carol', 30)] sorted(people, key=attrgetter('age', 'name')) # by age, then name ``` **Reverse one field in a multi-field sort** There's no built-in way to reverse only one field in a tuple key. The standard trick is to negate numeric fields: ```python # Grade ascending, age DESCENDING sorted(students, key=lambda s: (s['grade'], -s['age'])) # [Bob(A,20), Alice(B,22), Carol(B,21)] — Carol is now before Alice ``` For non-numeric fields, use the two-pass stable sort trick from Block 1. **Sorting strings case-insensitively** ```python names = ['banana', 'Apple', 'cherry', 'Date'] sorted(names) # ['Apple', 'Date', 'banana', 'cherry'] (uppercase first) sorted(names, key=str.lower) # ['Apple', 'banana', 'cherry', 'Date'] (true alpha) sorted(names, key=str.casefold) # same but better for accented chars ``` **max() and min() use the same key=** ```python words = ['banana', 'fig', 'apple'] max(words, key=len) # 'banana' min(words, key=len) # 'fig' youngest = min(students, key=itemgetter('age')) ```

heapq, cmp_to_key, and Timsort internals

#
**heapq — efficient min-heap operations** `heapq` maintains a list as a min-heap. The smallest element is always at index 0. Use it when you need repeated access to the minimum, not a full sorted list: ```python import heapq nums = [5, 1, 3, 8, 2] heapq.heapify(nums) # rearrange list in-place into a heap: [1, 2, 3, 8, 5] heapq.heappush(nums, 0) # add 0 and maintain heap property heapq.heappop(nums) # remove and return smallest: 0 heapq.heappop(nums) # next smallest: 1 # Get N smallest / largest without full sort heapq.nsmallest(3, nums) # [2, 3, 5] — O(n + k log n) heapq.nlargest(3, nums) # [8, 5, 3] # With a key function: tasks = [{'priority': 3, 'name': 'write tests'}, {'priority': 1, 'name': 'fix bug'}] heapq.nsmallest(1, tasks, key=lambda t: t['priority']) # [{'priority': 1, ...}] ``` **functools.cmp_to_key — legacy comparison functions** Old code (Python 2 style) may use comparison functions that return -1/0/1. `cmp_to_key` adapts them to the modern `key=` interface: ```python from functools import cmp_to_key def compare_last_char(a, b): if a[-1] < b[-1]: return -1 if a[-1] > b[-1]: return 1 return 0 sorted(['banana', 'fig', 'apple'], key=cmp_to_key(compare_last_char)) # ['banana', 'apple', 'fig'] — sorted by last char: a, e, g ``` Prefer `key=` functions whenever possible — they're cleaner and faster. **Timsort — why Python's sort is fast** Python's built-in sort uses **Timsort**, a hybrid of merge sort and insertion sort. Key properties: - Time: O(n log n) worst case, O(n) on already-sorted data - Space: O(n) extra - Stable: equal elements preserve original order - Adaptive: detects and exploits existing sorted runs in the data This means sorting a nearly-sorted list is much faster than sorting a random one. In practice, Python's sort is fast enough that you rarely need to reach for alternatives. **When to use heapq vs sorted** ``` Need Use ──────────────────────────────────── ────────────────── All elements sorted once sorted() / .sort() Repeatedly get the minimum heapq Top-N from a large stream heapq.nsmallest/nlargest Priority queue (tasks by priority) heapq ```

Exercises:

01

Sort by absolute value

#
Write a function that takes a list of integers and returns them sorted by their absolute value, ascending.
def sort_by_abs(numbers):
    pass


print(sort_by_abs([-5, 3, -1, 4, -2, 8]))
Solution 
def sort_by_abs(numbers):
    return sorted(numbers, key=abs)


print(sort_by_abs([-5, 3, -1, 4, -2, 8]))
02

Sort strings case-insensitively

#
Write a function that takes a list of strings and returns them sorted alphabetically, ignoring case.
def sort_words(words):
    pass


print(sort_words(["Banana", "apple", "Cherry", "date"]))
Solution 
def sort_words(words):
    return sorted(words, key=str.lower)


print(sort_words(["Banana", "apple", "Cherry", "date"]))
03

Sort by last name

#
Write a function that takes a list of full names (strings like 'First Last') and returns them sorted alphabetically by last name.
def sort_by_last_name(names):
    pass


names = ["Alice Smith", "Bob Johnson", "Carol Adams", "Dave Brown"]
print(sort_by_last_name(names))
Solution 
def sort_by_last_name(names):
    return sorted(names, key=lambda name: name.split()[-1])


names = ["Alice Smith", "Bob Johnson", "Carol Adams", "Dave Brown"]
print(sort_by_last_name(names))
04

Sort dictionaries by multiple fields

#
Write a function that takes a list of product dictionaries (each with 'category' and 'price' keys) and returns them sorted first by category (A-Z), then by price (ascending) within each category.
def sort_products(products):
    pass


products = [
    {"name": "Bread", "category": "food", "price": 2},
    {"name": "TV", "category": "electronics", "price": 500},
    {"name": "Milk", "category": "food", "price": 1},
    {"name": "Phone", "category": "electronics", "price": 800},
]
for p in sort_products(products):
    print(p)
Solution 
def sort_products(products):
    return sorted(products, key=lambda p: (p["category"], p["price"]))


products = [
    {"name": "Bread", "category": "food", "price": 2},
    {"name": "TV", "category": "electronics", "price": 500},
    {"name": "Milk", "category": "food", "price": 1},
    {"name": "Phone", "category": "electronics", "price": 800},
]
for p in sort_products(products):
    print(p)
05

Sort in-place vs return new

#
Write two functions: one that sorts a list of numbers in-place (modifying the original) and returns None, and one that returns a sorted copy without modifying the original.
def sort_inplace(numbers):
    pass


def sort_copy(numbers):
    pass


nums = [3, 1, 4, 1, 5]
sort_inplace(nums)
print(nums)

nums2 = [3, 1, 4, 1, 5]
result = sort_copy(nums2)
print(nums2)
print(result)
Solution 
def sort_inplace(numbers):
    numbers.sort()


def sort_copy(numbers):
    return sorted(numbers)


nums = [3, 1, 4, 1, 5]
sort_inplace(nums)
print(nums)

nums2 = [3, 1, 4, 1, 5]
result = sort_copy(nums2)
print(nums2)
print(result)
06

Top N

#
Write a function that takes a list of numbers and an integer n, and returns the n largest numbers in descending order.
def top_n(numbers, n):
    pass


print(top_n([3, 1, 4, 1, 5, 9, 2, 6, 5, 3], 3))
Solution 
def top_n(numbers, n):
    return sorted(numbers, reverse=True)[:n]

# Or more efficient for large lists:
def top_n(numbers, n):
    import heapq
    return heapq.nlargest(n, numbers)


print(top_n([3, 1, 4, 1, 5, 9, 2, 6, 5, 3], 3))
07

Sort by frequency

#
Write a function that takes a list of numbers and returns them sorted by how often they appear — most frequent first. Elements with the same frequency should remain in their original relative order.
def sort_by_frequency(numbers):
    pass


print(sort_by_frequency([4, 2, 2, 8, 3, 3, 1, 3]))
Solution 
def sort_by_frequency(numbers):
    from collections import Counter
    freq = Counter(numbers)
    return sorted(numbers, key=lambda n: -freq[n])


print(sort_by_frequency([4, 2, 2, 8, 3, 3, 1, 3]))
08

Stable sort property

#
Write a function that takes a list of (name, score) tuples and returns them sorted by score descending. When scores are equal, preserve the original order of names (stable sort).
def rank_players(players):
    pass


players = [("Alice", 90), ("Bob", 85), ("Carol", 90), ("Dave", 85)]
print(rank_players(players))
Solution 
def rank_players(players):
    return sorted(players, key=lambda p: -p[1])


players = [("Alice", 90), ("Bob", 85), ("Carol", 90), ("Dave", 85)]
print(rank_players(players))
09

Sort with mixed ascending/descending

#
Write a function that takes a list of (name, age) tuples and returns them sorted by name ascending and age descending when names are equal.
def sort_people(people):
    pass


people = [("Alice", 30), ("Bob", 25), ("Alice", 25), ("Bob", 35)]
print(sort_people(people))
Solution 
def sort_people(people):
    return sorted(people, key=lambda p: (p[0], -p[1]))


people = [("Alice", 30), ("Bob", 25), ("Alice", 25), ("Bob", 35)]
print(sort_people(people))
10

Custom sort with functools.cmp_to_key

#
Write a function that sorts a list of version strings (like '1.10.2', '1.9.0') correctly as version numbers, not as plain strings. Use functools.cmp_to_key.
from functools import cmp_to_key


def sort_versions(versions):
    pass


print(sort_versions(["1.10.2", "1.9.0", "2.0.0", "1.9.10", "1.1.0"]))
Solution 
from functools import cmp_to_key


def sort_versions(versions):
    def compare(a, b):
        a_parts = list(map(int, a.split(".")))
        b_parts = list(map(int, b.split(".")))
        if a_parts < b_parts: return -1
        if a_parts > b_parts: return 1
        return 0
    return sorted(versions, key=cmp_to_key(compare))


print(sort_versions(["1.10.2", "1.9.0", "2.0.0", "1.9.10", "1.1.0"]))