Exercises: Searching and Sorting: Classic Algorithms

These exercises progress from concept checks through increasingly challenging algorithm problems. Implement every solution yourself — the muscle memory of writing these algorithms matters.

Difficulty Guide: - ⭐ Foundational (5-10 min each) - ⭐⭐ Intermediate (10-20 min each) - ⭐⭐⭐ Challenging (20-40 min each) - ⭐⭐⭐⭐ Advanced/Research (40+ min each)

Part A: Searching ⭐

A.1. Implement linear_search(data, target) that returns the index of the first occurrence of target in data, or -1 if not found. Test it with the list [10, 23, 45, 70, 11, 15] and targets 70, 15, and 99.

A.2. Modify your linear search to return a list of all indices where the target appears. For example, find_all([3, 1, 4, 1, 5, 1], 1) should return [1, 3, 5].

A.3. Implement count_comparisons_linear(data, target) that performs a linear search but also counts and returns the number of comparisons made. Return a tuple (index, comparisons). Test with a list of 100 elements where the target is (a) the first element, (b) the last element, (c) not present.

A.4. Implement binary_search(data, target) that returns the index of target in a sorted list, or -1 if not found. Test it with the sorted list [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] and targets 23, 91, and 50.

A.5. Implement count_comparisons_binary(data, target) that performs binary search and counts the number of comparisons made. Compare the number of comparisons with linear search for a sorted list of 1,000 elements.

Part B: Basic Sorting ⭐-⭐⭐

B.1. Implement selection_sort(data) and test it with: - [64, 25, 12, 22, 11] - [1, 2, 3, 4, 5] (already sorted) - [5, 4, 3, 2, 1] (reverse sorted) - [] (empty list)

Verify that all four cases produce correct output.

B.2. Implement insertion_sort(data) and test it with the same four lists as B.1. For the already-sorted list, add a print statement inside the inner loop to confirm that the inner loop body never executes (demonstrating O(n) best-case behavior).

B.3. Implement merge_sort(data) and merge(left, right). Test with the same four lists. Verify that the original list is not modified (merge sort returns a new list).

B.4. Add a print() statement at the beginning of your merge_sort function that shows the current sublist being processed. Run merge_sort([38, 27, 43, 3, 9, 82, 10]) and study the output to understand the recursive call tree.

B.5. Write a function is_sorted(data) that returns True if a list is in ascending order and False otherwise. Use this function to verify the output of each sorting algorithm you implemented.

Part C: Built-in Sorting and Key Functions ⭐⭐

C.1. Given a list of words, sort them: - (a) Alphabetically (default) - (b) By length (shortest to longest) - (c) By length (longest to shortest) - (d) By the last character of each word

Use sorted() with appropriate key and/or reverse parameters.

words = ["banana", "cherry", "apple", "date", "elderberry", "fig"]

C.2. Given a list of student dictionaries, write one sorted() call for each: - (a) Sort by name alphabetically - (b) Sort by grade descending (highest first) - (c) Sort by name length, then alphabetically for ties

students = [
    {"name": "Alice", "grade": 88},
    {"name": "Bob", "grade": 95},
    {"name": "Charlie", "grade": 88},
    {"name": "Di", "grade": 91},
    {"name": "Eve", "grade": 95},
]

C.3. Explain the difference between .sort() and sorted(). Then predict and verify the output:

original = [3, 1, 4, 1, 5]
result_a = original.sort()
print(f"original: {original}, result_a: {result_a}")

original2 = [3, 1, 4, 1, 5]
result_b = sorted(original2)
print(f"original2: {original2}, result_b: {result_b}")

C.4. Write a function sort_by_field(records, field, descending=False) that sorts a list of dictionaries by any specified field. Test it:

products = [
    {"name": "Laptop", "price": 999, "rating": 4.5},
    {"name": "Mouse", "price": 25, "rating": 4.8},
    {"name": "Keyboard", "price": 75, "rating": 4.2},
    {"name": "Monitor", "price": 350, "rating": 4.6},
]
# Sort by price ascending, then by rating descending, then by name

C.5. Use sorted() with a lambda to sort the following list of dates (given as strings in "YYYY-MM-DD" format) in chronological order:

dates = ["2025-03-15", "2024-12-01", "2025-01-20", "2024-11-30", "2025-03-01"]

Then sort them by month only (ignoring year and day).

Part D: Analysis and Comparison ⭐⭐-⭐⭐⭐

D.1. Write a timing function benchmark_sort(sort_func, data) that: - Makes a copy of the data - Times the sort using time.perf_counter() - Returns the elapsed time

Use it to compare selection sort, insertion sort, merge sort, and sorted() on random lists of sizes 500, 1000, 2000, and 5000. Print a formatted table of results.

D.2. Run insertion sort on three types of input: - (a) Random data - (b) Already-sorted data - (c) Reverse-sorted data

Time each for n=5000. Explain why the times are so different, using Big-O analysis.

D.3. You have a list of 100,000 customer records that you need to search 500 times by customer ID. Calculate the total number of operations for each strategy: - (a) Linear search each time: 500 * 100,000 = ? - (b) Sort once, then binary search each time: 100,000 * log₂(100,000) + 500 * log₂(100,000) = ?

Which is faster? At what number of searches does strategy (b) become worth the upfront sorting cost?

D.4. A stable sort preserves the relative order of equal elements. Design a test that demonstrates stability (or lack thereof): - Create a list of tuples like [(3, "A"), (1, "B"), (3, "C"), (1, "D"), (2, "E")] - Sort by the first element only - Check whether "A" still comes before "C" (both have key 3) and "B" still comes before "D" (both have key 1) - Test with insertion sort, selection sort, merge sort, and sorted()

D.5. The in operator on a Python list performs linear search. The in operator on a Python set performs O(1) hash-based lookup. Write a benchmark that searches for 1,000 random targets in (a) a list of 100,000 elements and (b) a set of 100,000 elements. How much faster is the set? Express the speedup as a ratio.

Part E: Challenges ⭐⭐⭐-⭐⭐⭐⭐

E.1. ⭐⭐⭐ Implement bubble sort: repeatedly pass through the list, swapping adjacent elements that are out of order, until no swaps are needed. Analyze its time complexity (best, average, worst). Compare it empirically to insertion sort — which is faster on random data? On nearly-sorted data?

E.2. ⭐⭐⭐ Implement a function binary_search_insert_position(sorted_data, value) that returns the index where value should be inserted to maintain sorted order (even if value isn't in the list). This is the idea behind Python's bisect.bisect_left(). Test it:

data = [10, 20, 30, 40, 50]
print(binary_search_insert_position(data, 25))  # 2 (between 20 and 30)
print(binary_search_insert_position(data, 10))  # 0 (before the existing 10)
print(binary_search_insert_position(data, 55))  # 5 (after everything)

E.3. ⭐⭐⭐ Implement a function top_k(data, k) that returns the k largest elements in data without fully sorting the list. Use a partial selection sort approach (only do k passes instead of n passes). What is its time complexity? When is this faster than sorting the whole list?

E.4. ⭐⭐⭐⭐ Implement quicksort: pick a pivot, partition elements into "less than pivot" and "greater than pivot" groups, and recursively sort each group. What is its average-case time complexity? What is its worst-case time complexity, and when does it occur?

E.5. ⭐⭐⭐⭐ The Dutch National Flag Problem: Given a list containing only the values 0, 1, and 2, sort it in a single pass (O(n) time, O(1) space) without using any comparison-based sorting algorithm. Hint: maintain three regions in the list using three pointers.

data = [2, 0, 1, 2, 1, 0, 0, 2, 1]
dutch_flag_sort(data)
print(data)  # [0, 0, 0, 1, 1, 1, 2, 2, 2]