Unit 4 Cycle 1 Day 19: Insertion Sort
Share
Insertion Sort
Section 4.7 — Sorting
Key Concept
Insertion sort builds a sorted portion of the array one element at a time. Each new element is compared to the sorted elements and inserted at the correct position by shifting larger elements right. After pass k, the first k + 1 elements are sorted relative to each other (but may not be in their final positions). The AP exam tests insertion sort tracing and asks about the number of comparisons and shifts. Insertion sort is efficient on nearly-sorted data.
Consider the following array being sorted with insertion sort.
What does the array look like after inserting the element at index 3 (value 1)?
Answer: (A) {1, 3, 5, 8, 2}
Sorted portion: {3, 5, 8}. Insert 1: 1<8 (shift), 1<5 (shift), 1<3 (shift). Place 1 at front: {1, 3, 5, 8, 2}.
Why Not the Others?
(B) 1 is smaller than 5 and 3, so it shifts further left.
(C) This is the fully sorted array. Index 4 has not been inserted yet.
(D) 1 is smaller than 3, so it goes before 3.
Common Mistake
Insertion sort maintains a sorted portion on the left. Each new element is inserted into its correct position by shifting larger elements right.
AP Exam Tip
Insertion sort: O(n^2). The sorted portion grows by one each pass. Elements shift right to make room. Know how to trace each insertion step.