Unit 4 Cycle 2 Day 7: Selection Sort: Two-Pass Trace
Share
Selection Sort: Two-Pass Trace
Section 4.7 — Sorting
Key Concept
A detailed selection sort trace shows the array state after each complete pass. In pass k, the algorithm scans from index k to the end, finds the minimum, and swaps it with position k. After the pass, elements 0 through k are in their final sorted positions. The AP exam asks you to show the array after a specific number of passes, or to count how many swaps and comparisons occur in two complete passes. Trace methodically: find the minimum, then show the swap.
Consider selection sort on the following array.
What does the array look like after TWO complete passes?
Answer: (A) {10, 13, 14, 37, 29}
Pass 1: min=10 (idx 1). Swap with idx 0: {10, 29, 14, 37, 13}. Pass 2: min of [1..4]=13 (idx 4). Swap with idx 1: {10, 13, 14, 37, 29}.
Why Not the Others?
(B) After pass 2, 14 is already at index 2 and unchanged.
(C) This shows only one pass.
(D) This is fully sorted. Only 2 of 4 passes completed.
Common Mistake
After k passes of selection sort, the first k elements are in their final position. Remaining elements may not yet be sorted.
AP Exam Tip
Trace selection sort pass by pass: find min in unsorted portion, swap. After 2 passes on 5 elements, indices 0-1 are finalized.