Sorting Algorithms
Introduced| English |
|---|
| Sorting/ˈsɔːtɪŋ/ |
| selection sort/sɪˈlekʃn sɔːt/ |
| insertion sort/ɪnˈsɜːʃn sɔːt/ |
| in place/ɪn pleɪs/ |
Putting things in order
- Sorting 排序 rearranges elements into order (smallest to largest, say).
- The AP course covers two simple sorts: selection sort 选择排序 and insertion sort 插入排序.
- Both use nested loops and swap or shift elements into place.
- Sorting first is what lets you use fast binary search afterwards.
Selection sort
- Find the smallest remaining element and swap it to the front.
- Then find the smallest of what's left, swap it into the next spot, and so on.
- The front of the array grows sorted; the back shrinks unsorted.
- One swap per pass — but it still scans the rest each pass.
Insertion sort
- Take the next element and shift it back into its correct place among the already-sorted front.
- Like sorting a hand of cards: slot each new card where it belongs.
- The sorted region grows by one each pass.
- Fast when the data is already nearly sorted.
How much work
- Both sorts use nested loops, so they do about
n²comparisons in the worst case. - That's fine for small arrays but slow for very large ones.
- They sort in place 原地 — no second array needed.
- The exam wants you to trace them, not just name them.
Selection sort SWAPS the smallest remaining element to the front; insertion sort SHIFTS each new element back into the sorted part — don't mix them up. Both are O(n²) nested-loop sorts and both sort in place. Trace them step by step (the AP exam asks for the array's state after each pass), rather than memorising a name.
Selection sort on [3, 1, 2]:
- Pass 1: smallest is
1; swap to front →[1, 3, 2]. - Pass 2: smallest of
[3, 2]is2; swap →[1, 2, 3]. - Sorted — the front grew one element per pass.
Sorting orders elements. Selection sort repeatedly swaps the smallest remaining element to the front; insertion sort shifts each new element back into the sorted part. Both are nested-loop, in-place, O(n²) sorts. Sorting enables fast binary search afterwards.
Stepping through a sort
Each pass places one more element in order.
Selection sort works by...
Selection sort selects the minimum and swaps it forward.
Insertion sort works by...
Insertion sort inserts each element into its sorted place.
In the worst case, both sorts do about...
Nested loops give O(n²).
Both selection and insertion sort work in place (no second array).
They rearrange the same array.
Order the passes of selection sort on [3, 1, 2].
Front grows sorted, one element per pass.
Sorting first is useful because it lets you later use...
Binary search needs sorted data.