Unit 4 Cycle 1 Day 20: Comparing Sorts
Share
Comparing Sorts
Section 4.7 — Sorting
Key Concept
Selection sort and insertion sort have different performance characteristics. Selection sort always makes the same number of comparisons (n(n-1)/2) regardless of input order, but makes fewer swaps than insertion sort in the worst case. Insertion sort adapts to the input: nearly-sorted data requires few shifts, making it fast, while reverse-sorted data is the worst case. The AP exam tests your ability to compare these algorithms and determine which is more efficient for specific input scenarios.
Consider the following statements about sorting algorithms.
Which statements are true?
Answer: (B) I, II, and III
I: TRUE. Selection sort always scans the unsorted portion.
II: TRUE. Insertion sort needs few shifts on nearly-sorted data.
III: TRUE. Both are O(n^2) worst case.
Why Not the Others?
(A) II is also true. Insertion sort benefits from nearly-sorted input.
(C) I is also true. Selection sort's comparison count is independent of initial order.
(D) I and II are also true.
Common Mistake
Selection sort has consistent performance. Insertion sort adapts: best case O(n) for sorted data, worst case O(n^2) for reverse-sorted data.
AP Exam Tip
AP exam: know that both are O(n^2), but insertion sort can be O(n) best case. Selection sort always does the same number of comparisons.