Chapter 19 Quiz

Test your understanding of Chapter 19 concepts. Try to answer each question without looking back at the chapter. After answering, expand the solution to check your work.

Q1. What is the time complexity of linear search in the worst case? - (a) O(1) - (b) O(log n) - (c) O(n) - (d) O(n²)

Answer **(c) O(n).** In the worst case, linear search must examine every element in the list (the target is the last element or not present). The number of comparisons grows linearly with the size of the input.

Q2. What is the critical prerequisite for using binary search?

Answer The data must be **sorted**. Binary search works by comparing the target to the middle element and eliminating half of the remaining data. If the data isn't sorted, the elimination logic is invalid and binary search will produce incorrect results — without any error message.

Q3. A sorted list has 2,048 elements. What is the maximum number of comparisons binary search needs?

Answer **12 comparisons.** Since 2^11 = 2,048, binary search needs at most log₂(2,048) + 1 = 12 steps. Each step halves the search space.

Q4. What will this code print?

data = [15, 42, 8, 23, 4]
result = data.sort()
print(result)
Answer 
None
The `.sort()` method sorts the list **in place** and returns `None`. The sorted data is in `data` (which is now `[4, 8, 15, 23, 42]`), but `result` is `None`. To get the sorted list as a return value, use `sorted(data)` instead.

Q5. Describe the selection sort algorithm in your own words (2-3 sentences).

Answer Selection sort works by repeatedly finding the **smallest element** in the unsorted portion of the list and swapping it with the element at the current position. It starts by finding the minimum of the entire list and placing it at index 0, then finds the minimum of the remaining elements (index 1 onward) and places it at index 1, and so on. After n-1 passes, the entire list is sorted.

Q6. Why is insertion sort particularly good for nearly-sorted data?

Answer Insertion sort is **adaptive** — its performance depends on how much disorder exists in the input. For each element, the inner `while` loop only runs while there are larger elements to the left that need shifting. In nearly-sorted data, most elements are already close to their correct position, so the inner loop barely executes. This gives insertion sort **O(n)** performance on nearly-sorted data, compared to O(n²) on random data.

Q7. What does it mean for a sorting algorithm to be "stable"?

Answer A **stable** sort preserves the relative order of elements that compare as equal. For example, if you sort `[("Alice", 90), ("Bob", 85), ("Charlie", 90)]` by grade, a stable sort guarantees that Alice still appears before Charlie (both have 90) because Alice was first in the original list. Insertion sort, merge sort, and Python's Timsort are stable. Selection sort is not stable.

Q8. What is the time complexity of merge sort? - (a) O(n) best, O(n²) worst - (b) O(n log n) best, O(n log n) worst - (c) O(n²) best, O(n²) worst - (d) O(log n) best, O(n) worst

Answer **(b) O(n log n) in all cases.** Merge sort always divides the list in half (log n levels of recursion) and does O(n) work at each level (merging). It doesn't have a "bad case" — its performance is consistent regardless of input order. The trade-off is that it uses O(n) extra space.

Q9. What is the primary disadvantage of merge sort compared to insertion sort?

Answer **Space complexity.** Merge sort requires **O(n) extra memory** to hold the merged sublists, while insertion sort sorts **in place** using O(1) extra memory. For very large datasets where memory is constrained, this can be a significant drawback. Additionally, for small or nearly-sorted data, insertion sort can be faster due to lower constant factors and its adaptive behavior.

Q10. What will this code output?

words = ["banana", "Apple", "cherry", "date"]
result = sorted(words)
print(result)
Answer 
['Apple', 'banana', 'cherry', 'date']
Python's default string sorting is **lexicographic** and **case-sensitive**. Uppercase letters have lower Unicode values than lowercase letters, so `'A' < 'b'`, which puts `"Apple"` before `"banana"`. To sort case-insensitively, use `sorted(words, key=str.lower)`.

Q11. Write a sorted() call that sorts a list of strings by the number of vowels in each string (fewest vowels first).

Answer 
words = ["algorithm", "sort", "binary", "search", "key"]

def count_vowels(word):
    return sum(1 for ch in word.lower() if ch in "aeiou")

result = sorted(words, key=count_vowels)
# Or using a lambda:
result = sorted(words, key=lambda w: sum(1 for c in w.lower() if c in "aeiou"))
print(result)  # ['sort', 'key', 'binary', 'search', 'algorithm']
The vowel counts are `sort` 1, `key` 1 (`y` isn't in `"aeiou"`), `binary` 2, `search` 2, `algorithm` 3. Ties keep their original order because `sorted()` is stable, so `sort` stays ahead of `key` and `binary` ahead of `search`.

Q12. What is a lambda expression, and how does it relate to key functions?

Answer A **lambda expression** is a small anonymous (unnamed) function defined with the syntax `lambda parameters: expression`. Its body must be a single expression (no statements such as `return`, loops, or assignments), and it returns that expression's value automatically. For example, `lambda x: x * 2` is equivalent to: 
def double(x):
    return x * 2
Lambda expressions are commonly used as **key functions** in `sorted()` and `.sort()` because they provide a concise way to specify what value to sort by. For example, `sorted(students, key=lambda s: s["gpa"])` sorts students by their GPA field.

Q13. What is the difference between sorted() and .sort()? Give two differences.

Answer 1. **Return value:** `sorted()` returns a **new sorted list** and leaves the original unchanged. `.sort()` sorts the list **in place** and returns `None`. 2. **Applicability:** `sorted()` works on **any iterable** (lists, tuples, strings, generators, etc.). `.sort()` is a **list method** — it only works on lists. Additional difference: because `sorted()` creates a new list, you can chain it with other operations (e.g., `sorted(data)[:5]`). Since `.sort()` returns `None`, chaining doesn't work.

Q14. You have a list of 1,000,000 elements. Approximately how many comparisons would each algorithm need in the worst case?

Algorithm Comparisons
Linear search ?
Binary search ?
Selection sort ?
Merge sort ?
Answer | Algorithm | Comparisons | |-----------|-------------| | Linear search | ~1,000,000 (O(n)) | | Binary search | ~20 (O(log n), since log₂(1,000,000) ≈ 20) | | Selection sort | ~500,000,000,000 (O(n²), roughly n²/2) | | Merge sort | ~20,000,000 (O(n log n), roughly n × 20) | The difference between selection sort (500 billion) and merge sort (20 million) is a factor of 25,000. This is why O(n²) algorithms become unusable for large data.

Q15. Trace binary search on the list [5, 10, 15, 20, 25, 30, 35] searching for the target 15. Show the values of low, high, and mid at each step.

Answer 
Step 1: low=0, high=6, mid=3
        data[3]=20 > 15 → search left, high = 2

Step 2: low=0, high=2, mid=1
        data[1]=10 < 15 → search right, low = 2

Step 3: low=2, high=2, mid=2
        data[2]=15 == 15 → FOUND at index 2
Binary search found the target in 3 comparisons. Linear search would have also needed 3 in this case (checking indices 0, 1, 2), but the advantage of binary search grows with list size.

Q16. What is Timsort, and why should you usually prefer Python's built-in sorting over hand-written algorithms?

Answer **Timsort** is a hybrid sorting algorithm designed by Tim Peters in 2002 for Python. It combines merge sort and insertion sort: it finds "runs" that are already in order, extends short runs with insertion sort (fast for small pieces), and merges the runs merge-sort style. It is O(n) best case (already-sorted data), O(n log n) worst case, stable, and adaptive. You should prefer Python's built-in sorting because: (1) it's implemented in **optimized C code** on top of a smarter algorithm, making it roughly 10 to 1,000+ times faster than the pure Python sorts in this chapter, (2) it's **thoroughly tested** by millions of programs over more than two decades, (3) it handles edge cases correctly, and (4) using `sorted()` or `.sort()` is more **readable** and maintainable than custom sorting code.

Q17. Identify the bug in this binary search implementation:

def binary_search(data, target):
    low = 0
    high = len(data) - 1
    while low < high:           # Line A
        mid = (low + high) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
Answer **Line A uses `<` instead of `<=`.** When `low == high`, there is exactly one element left to check, but the loop exits without checking it. If the target is the element at that position, the function incorrectly returns -1. The fix is to change `while low < high:` to `while low <= high:`.

Q18. What will this code output?

data = [("Charlie", 88), ("Alice", 95), ("Bob", 88), ("Diana", 92)]
result = sorted(data, key=lambda x: x[1])
for name, grade in result:
    print(f"{name}: {grade}")
Answer 
Charlie: 88
Bob: 88
Diana: 92
Alice: 95
The list is sorted by grade (ascending). Because Python's `sorted()` is **stable**, Charlie and Bob (both with grade 88) maintain their original relative order — Charlie came before Bob in the input, so Charlie comes before Bob in the output.

Q19. You need to sort a list of file paths by file extension. Write the sorted() call:

files = ["report.pdf", "data.csv", "image.png", "notes.txt", "backup.csv"]
Answer 
files = ["report.pdf", "data.csv", "image.png", "notes.txt", "backup.csv"]
result = sorted(files, key=lambda f: f.rsplit(".", 1)[-1])
print(result)
# ['data.csv', 'backup.csv', 'report.pdf', 'image.png', 'notes.txt']
The lambda extracts the extension by splitting on `"."` from the right (at most once) and taking the last part. Files are then sorted alphabetically by extension: csv, pdf, png, txt. Notice that `data.csv` stays ahead of `backup.csv`: the key only looks at the extension, both are `"csv"`, and the stable sort keeps their original order. If you also want ties sorted by name, use `key=lambda f: (f.rsplit(".", 1)[-1], f)`.

Q20. In what situation is linear search actually better than binary search? Give two scenarios.

Answer 1. **The data is unsorted.** Binary search requires sorted data. If you'd have to sort first (O(n log n)) and then search (O(log n)), that's more work than a single linear search (O(n)) — unless you plan to search many times. 2. **The list is very small.** For a few dozen elements, the time saved by binary search is too small to notice, and keeping the list sorted (plus writing the trickier code) isn't worth it. Linear search has simpler logic and lower constant factors. Also valid: (3) You only search once — sorting first just to do one search is wasteful. (4) The data changes frequently — maintaining sorted order after every insertion is expensive.

Q21. What is meant by an "in-place" sorting algorithm? Which of the algorithms in this chapter are in-place, and which are not?

Answer An **in-place** sorting algorithm rearranges elements within the original list without allocating significant extra memory. It uses O(1) extra space (a few temporary variables). - **In-place:** Selection sort (O(1) extra), Insertion sort (O(1) extra) - **Not in-place:** Merge sort (O(n) extra for merged sublists), Python's Timsort (up to about n/2 extra slots while merging) Careful with `.sort()`: it changes your list "in place" in the everyday sense (no new list is returned), but the Timsort algorithm underneath still borrows O(n) temporary memory, so it isn't in-place in the algorithm-analysis sense. The trade-off in this chapter: the two in-place sorts pay for their memory savings with O(n²) time. In-place O(n log n) sorts do exist (heapsort is one), but they're trickier to write and usually give up stability.

Q22. Write a sorted() call that sorts a list of tasks by priority (ascending), breaking ties by due date (earliest first):

tasks = [
    {"title": "Study", "priority": 2, "due": "2025-03-20"},
    {"title": "Clean", "priority": 1, "due": "2025-03-18"},
    {"title": "Code", "priority": 2, "due": "2025-03-15"},
    {"title": "Read", "priority": 1, "due": "2025-03-16"},
]
Answer 
result = sorted(tasks, key=lambda t: (t["priority"], t["due"]))
for task in result:
    print(f"[{task['priority']}] {task['due']}: {task['title']}")
# [1] 2025-03-16: Read
# [1] 2025-03-18: Clean
# [2] 2025-03-15: Code
# [2] 2025-03-20: Study
Using a **tuple** as the key sorts by priority first. For tasks with the same priority, it then sorts by due date (string comparison works correctly for `"YYYY-MM-DD"` format because lexicographic order matches chronological order).