Sorting Algorithms
Introduced| English | Meaning |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | Sorting |
| selection sort/sɪˈlekʃn sɔːt/ | A sorting algorithm that repeatedly selects the smallest remaining item and places it next in the sorted portion. |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | A sorting method that inserts each new item into its correct position in the already sorted part of a list. |
| in place/ɪn pleɪs/ | Describes an algorithm that rearranges its input using only a small amount of extra storage. |
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.
An insertion sort, shifting each key into place pass by 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...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Selection sort selects the minimum and swaps it forward.
Insertion sort works by...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Insertion sort inserts each element into its sorted place.
In the worst case, both sorts do about...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Nested loops give O(n²).
Both selection and insertion sort work in place (no second array).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
They rearrange the same array.
Order the passes of selection sort on [3, 1, 2].
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Front grows sorted, one element per pass.
Sorting first is useful because it lets you later use...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Binary search needs sorted data.