Chapter 23 Exercises: Searching and Sorting

Part A: Conceptual Understanding

A.1. Explain why binary search requires sorted data. What happens if you apply binary search to an unsorted array? Give a concrete example of an incorrect result.

Guidance Binary search assumes that if the target is less than the middle element, it must be in the left half. With unsorted data, this assumption is false. Example: array [5, 1, 8, 3, 7], searching for 3. Mid = 8, so we search left half [5, 1] — but 3 is in the right half. Binary search returns "not found" even though 3 is present.

A.2. Explain the difference between a stable and an unstable sort. Give a practical example where stability matters.

Guidance A stable sort preserves the relative order of equal elements. Example: expenses sorted by date, then re-sorted by category. With a stable sort, expenses in the same category remain in date order. With an unstable sort, the date order within each category may be scrambled.

A.3. Why is insertion sort often faster than quicksort for small arrays (n < 20), despite having worse theoretical complexity?

Guidance Insertion sort has low constant overhead: no recursive calls, no partitioning, simple inner loop. Quicksort's recursive calls, pivot selection, and partitioning have higher constant costs. For very small n, the constants dominate the asymptotic complexity. This is why production sort implementations switch to insertion sort for small sub-arrays.

A.4. Merge sort is guaranteed O(n log n) while quicksort can degrade to O(n²). Why, then, is quicksort typically the default sort in standard libraries?

Guidance Quicksort has smaller constant factors: it sorts in-place (no O(n) temporary array), has better cache locality (sequential access to contiguous memory), and the O(n²) worst case is easily avoided with good pivot selection (median-of-three, random). In practice, quicksort is 2-3x faster than merge sort on most inputs.

A.5. Trace the execution of insertion sort on the array [5, 3, 8, 1, 9, 2]. Show the array after each insertion.

Guidance Start: [5, 3, 8, 1, 9, 2]. Insert 3: [3, 5, 8, 1, 9, 2]. Insert 8: [3, 5, 8, 1, 9, 2] (no move). Insert 1: [1, 3, 5, 8, 9, 2]. Insert 9: [1, 3, 5, 8, 9, 2] (no move). Insert 2: [1, 2, 3, 5, 8, 9]. Done.

A.6. Trace the execution of quicksort on [7, 2, 1, 6, 8, 5, 3, 4] using the last element as pivot. Show each partition step.

Guidance Pivot=4: partition → [2, 1, 3] 4 [8, 5, 7, 6]. Left: pivot=3, partition → [2, 1] 3 []. Sub: pivot=1, partition → [] 1 [2]. Right: pivot=6, partition → [5] 6 [8, 7]. Sub: pivot=7, partition → [] 7 [8]. Result: [1, 2, 3, 4, 5, 6, 7, 8].

A.7. In the merge sort trace for [38, 27, 43, 3, 9, 82, 10], how many total comparisons are made during all merge operations combined? How does this compare to the total comparisons in selection sort of the same array?

Guidance Merge sort: approximately n * log2(n) ≈ 7 * 2.8 ≈ 20 comparisons total across all merge operations. Selection sort: n*(n-1)/2 = 21 comparisons. For this small array they are similar, but for n=1000, merge sort ≈ 10,000 vs. selection sort ≈ 500,000.

Part B: Applied Analysis

B.1. Rosa has 5,000 expenses in PennyWise. She sorts them by date and then wants to find all expenses on a specific date. Should she use linear search or binary search? What if she wants to find all expenses in a date range (e.g., March 1-15)?

Guidance For a specific date: binary search to find any expense on that date (O(log n)), then scan left and right to find all matching dates (O(k) where k is the number of matches). For a date range: binary search for the start date and end date boundaries, then return all elements between them. Both are much faster than linear scanning.

B.2. GradeBook Pro needs to display students sorted by GPA (descending) with ties broken by last name (ascending). Write the comparison function. Which sorting algorithm should be used, and why?

Guidance Comparison function: first compare GPA in reverse order (B.GPA - A.GPA); if equal, compare LastName in normal alphabetical order. Use merge sort for stability (preserves alphabetical order among equal GPAs) or quicksort with median-of-three for speed. The composed comparison handles both criteria.

B.3. Tomás downloads 10,000 bank transactions for PennyWise. The transactions are already in chronological order (the bank sorts them by date). Which sorting algorithm would be fastest if he wants to re-sort by amount? What if the data were already sorted by amount?

Guidance Re-sort by amount (data is sorted by date, so randomly ordered by amount): quicksort or merge sort, both O(n log n). If already sorted by amount: insertion sort at O(n) would be fastest, since it detects sorted data immediately. This is why insertion sort is called "adaptive."

Part C: Code Exercises

C.1. Implement a recursive binary search function for an array of strings (alphabetical search). Test it with a sorted array of 10 names.

Hint Same structure as integer binary search, but compare strings using < and > operators. Pascal's string comparison is lexicographic by default.

C.2. Implement bubble sort (not covered in the chapter). Compare its performance to selection sort and insertion sort by counting comparisons and swaps on a 100-element random array.

Hint Bubble sort: repeatedly pass through the array, swapping adjacent out-of-order elements. Stop when no swaps occur in a pass. Worst case O(n²) comparisons and O(n²) swaps — worse than selection sort on swaps.

C.3. Write a function IsSorted(Arr, Size): Boolean that checks whether an array is sorted in ascending order. Use it to verify your sort implementations.

Hint Linear scan: check that Arr[I] <= Arr[I+1] for all I from 0 to Size-2. If any pair violates this, return False.

C.4. Implement merge sort for an array of TExpense records using a comparison function parameter. Test by sorting 20 expenses first by date, then by amount.

Hint Modify the merge sort code to work with TExpense records and accept a TExpenseCompare function. The merge step uses Compare(A, B) <= 0 instead of A <= B for stability.

C.5. Write a program that counts the number of comparisons each sorting algorithm makes on a random array of 1000 integers. Display results in a table.

Hint Add a global counter variable. Increment it before each comparison. Reset between runs. Sort a copy of the same array with each algorithm to ensure fair comparison.

C.6. Implement a BinarySearchInsertPoint function that, given a sorted array and a target, returns the index where the target should be inserted to maintain sorted order (even if the target is not present).

Hint Modify binary search: instead of returning -1 when not found, return the Low index (which will be the correct insertion point after the while loop terminates).

C.7. Write a function that removes duplicate values from a sorted array in O(n) time. How much harder is this problem if the array is unsorted?

Hint Sorted: scan with two pointers (read and write). Copy only when the current element differs from the previous one. If unsorted, you must either sort first (O(n log n)) or use a hash set (O(n) but requires extra data structure).

C.8. Implement a stable version of selection sort. (This is trickier than it sounds — you need to shift elements rather than swap.)

Hint Instead of swapping the minimum into position, shift all elements between the current position and the minimum's position one step right, then place the minimum at the current position. This preserves relative order but increases the number of moves.

Part D: Challenge Exercises

D.1. Hybrid Sort. Implement a hybrid quicksort that switches to insertion sort for sub-arrays smaller than 16 elements. Compare its performance to pure quicksort on arrays of 10,000 random integers.

Hint In the QuickSort procedure, replace the base case if Low >= High with if High - Low < 16 then InsertionSort(Arr, Low, High). The hybrid is typically 15-20% faster due to reduced function call overhead on small sub-arrays.

D.2. Counting Sort. Implement counting sort for arrays of integers in the range [0, MaxVal]. What is its time complexity? When is it better than comparison-based sorts?

Hint Count occurrences of each value, then reconstruct the sorted array from the counts. Time: O(n + MaxVal). Better than comparison sorts when MaxVal is small (e.g., sorting exam scores 0-100 for 10,000 students).

D.3. Merge Sort on Linked Lists. Implement merge sort for a linked list (not an array). Linked-list merge sort has an advantage: the merge step requires no extra memory because you can re-link nodes. Compare to array merge sort.

Hint Split the list using slow/fast pointer technique to find the middle. Recursively sort each half. Merge by relinking nodes. No temporary array needed — O(1) extra space compared to array merge sort's O(n).

D.4. Quicksort with Random Pivot. Implement quicksort using random pivot selection instead of last-element. Demonstrate that it does not degrade to O(n²) on sorted input.

Hint Use Random(High - Low + 1) + Low to pick a random index. Swap it with the last element, then proceed with normal partitioning. Time the sort on already-sorted input and compare to last-element pivot.

D.5. PennyWise Top-K Expenses. Rosa wants to find her 10 most expensive transactions without sorting the entire array. Implement a partial selection algorithm (based on quicksort's partition) that finds the top K elements in average O(n) time.

Hint This is the quickselect algorithm: partition once, then recurse only on the side containing the K-th element. Average O(n), worst O(n²). After finding the K-th largest, the K largest elements are all to its right.

Part M: Interleaving Review (Spaced Practice)

M.1. (From Ch 9) Why does binary search work in O(log n) on an array but not on a linked list? What property of arrays enables this?

Guidance Arrays provide O(1) random access — you can jump to any index instantly using address arithmetic. Linked lists require O(n) sequential traversal to reach the middle element, making binary search O(n log n) on a linked list — worse than linear search. This is why sorted arrays are preferred for search-heavy operations.

M.2. (From Ch 22) Merge sort and quicksort are both recursive. Compare their recursive structures: how many recursive calls does each make, and what work is done before vs. after the recursive calls?

Guidance Both make two recursive calls. In merge sort, the work (merging) happens AFTER the recursive calls — the halves are sorted first, then merged. In quicksort, the work (partitioning) happens BEFORE the recursive calls — the array is partitioned, then the partitions are sorted. This is a fundamental difference in divide-and-conquer strategy.

M.3. (From Ch 11) How does Pascal's strong typing help when implementing comparison functions for sorting records? What error would a dynamically typed language potentially miss?

Guidance Pascal's type system ensures that comparison functions receive the correct record type — you cannot accidentally pass a TStudent record to a function expecting TExpense. A dynamically typed language might accept the wrong type at compile time and crash at runtime when accessing a field that does not exist.

M.4. (From Ch 7/8) The comparison function CompareByAmount is passed to SortExpenses using the @ operator. Explain what @ does and how the sort function calls it. How does this relate to function pointers?

Guidance The @ operator takes the address of the function, creating a function pointer. The sort function stores this pointer in its Compare parameter (a procedural type). When it calls Compare(A, B), it uses the pointer to invoke the actual function. This is Pascal's mechanism for higher-order functions — passing behavior as a parameter.