Unit 4 Cycle 1 Day 18: Selection Sort
Share
Selection Sort
Section 4.7 — Sorting
Key Concept
Selection sort finds the minimum element in the unsorted portion and swaps it with the first unsorted position, repeating until the entire array is sorted. The outer loop tracks the current position, and the inner loop finds the minimum in the remaining elements. After pass k, the first k elements are in their final sorted positions. The AP exam tests selection sort by asking you to show the array state after each pass or to count the number of comparisons and swaps.
Consider the following array being sorted with selection sort.
What does the array look like after the FIRST pass of selection sort (after one swap)?
Answer: (A) {11, 25, 12, 22, 64}
Pass 1: find minimum in entire array = 11 (at index 4). Swap with index 0: {11, 25, 12, 22, 64}.
Why Not the Others?
(B) This looks like a different sorting approach.
(C) Selection sort swaps the minimum with the CURRENT position, not shifts everything.
(D) 12 is not the minimum. 11 is the smallest value.
Common Mistake
Selection sort: find minimum, swap with current position. After pass k, the first k elements are in their final sorted position.
AP Exam Tip
Selection sort: O(n^2). Each pass finds the minimum of the unsorted portion and swaps it into place. Know the step-by-step trace for the AP exam.