Lab 15: Search and Sort

After this lab, you will be able to:

• Implement selection sort with an explicit swap helper method
• Write binary search on a sorted array and return the correct index (or -1)
• Sort parallel arrays in lockstep so corresponding elements stay aligned
• Trace through sort and search algorithms by hand to verify correctness

What You’re Building

You will sort an array of student scores using selection sort, then search the sorted array using binary search. The twist: a parallel array of student names must stay synchronized with the scores array throughout the sort. When you sort scores, the corresponding name must move with its score. The final program prints a sorted roster and lets the user search for a score to find the student who earned it.

Concepts and Misconceptions

Checkpoints

Checkpoint 1: Selection Sort with a Swap Helper

What to do: Write a swap method that takes an array and two indices, then swaps the elements at those positions using a temporary variable. Write selectionSort that finds the minimum element in the unsorted portion and calls swap to place it. Sort an int[] of scores.

What the test checks: The array is in ascending order after selectionSort returns.

Debugging tip: If your array is partially sorted or unchanged, print the array after each pass. Verify that your inner loop starts at i + 1, not 0. If swap does nothing, make sure it receives the array and indices, not the values themselves.

Checkpoint 2: Binary Search on a Sorted Array

What to do: Write binarySearch that takes a sorted int[] and a target value. Return the index where the target is found, or -1 if it is not present. Use low, high, and mid variables with a while loop.

What the test checks: Returns the correct index for values that exist and -1 for values that do not.

Debugging tip: If the method returns -1 for a value you know is in the array, check your loop condition. It should be while (low <= high), not while (low < high) — the = case handles a one-element remaining range. Also verify that you update low = mid + 1 and high = mid - 1, not low = mid or high = mid, which can cause infinite loops.

Checkpoint 3: Sort Parallel Arrays Together

What to do: Modify your selectionSort to accept two arrays: int[] scores and String[] names. Every time you swap two elements in scores, perform the same swap in names. After sorting, each name still corresponds to its original score.

What the test checks: Both arrays are sorted by score in ascending order, and names match their original scores.

Debugging tip: If names are scrambled after sorting, add a print statement inside your swap that shows which indices are being swapped and the values in both arrays. Confirm that every swap call on scores is immediately followed by the same index swap on names.

How to Debug

1. Print the array after every pass. Selection sort makes n - 1 passes. Print the full array after each one. You should see one more element “locked in” at the front on each pass.

2. Test binary search on edge cases. Search for the first element, the last element, and a value that does not exist. These three cases exercise all branches.

3. Use small arrays. Debug with 4-5 elements where you can trace every comparison by hand. Once the logic works, the autograder’s larger arrays will pass automatically.

Scoring