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)  # ['key', 'sort', 'search', 'binary', 'algorithm']

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`. It returns the value of the expression. 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 divides data into small "runs," sorts each run with insertion sort (fast for small data), and merges runs using merge sort's strategy. 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**, making it 30-3000x faster than equivalent pure Python code, (2) it's **thoroughly tested** and bug-free, (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)
# ['backup.csv', 'data.csv', 'report.pdf', 'image.png', 'notes.txt']
The lambda extracts the extension by splitting on `"."` from the right and taking the last part. Files are then sorted alphabetically by extension: csv, pdf, png, txt.

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 lists under ~50 elements, the overhead of calculating midpoints and managing pointers in binary search 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 (O(n) extra) The trade-off: in-place algorithms save memory but are often harder to implement correctly or have worse time complexity.

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).