Free for students · Ad-free · WCAG 2.1 AA Compliant · Accessibility

Sorting Algorithms

Lesson ~10 min read 8 MCQs

In simple terms: In simple terms, sorting algorithms are step-by-step methods, like recipes, that a computer uses to arrange a list of items, such as numbers or names, into a specific order (like smallest to largest).

Why this matters

Imagine you're a camp counselor in charge of lining up your group of kids for a photo. They're all jumbled up, and you need to arrange them from shortest to tallest. How would you do it?

You could find the shortest kid in the entire group and place them at the very front. Then, you could look at the remaining kids, find the next shortest, and place them in the second spot. Or, you could start with the first kid, then have the second kid stand in the right spot relative to the first. Then the third kid finds their spot among the first two, and so on, like people joining a line at a concession stand.

These are two different strategies—two different algorithms—for achieving the same goal. Today, we're going to explore the computer science versions of these strategies: Selection Sort and Insertion Sort.

Concept overview

flowchart TD
    A[Start with unsorted array] --> B{Is there an unsorted part?};
    B -- Yes --> C[Find the minimum value in the unsorted part];
    C --> D[Swap minimum with the first element of the unsorted part];
    D --> E[Mark that element as sorted];
    E --> B;
    B -- No --> F[End: Array is sorted];

Core explanation

When you have a jumble of data—test scores, contact names, product prices—you often need to put it in order. Sorting algorithms are the specific, step-by-step procedures a computer follows to do this. For the AP exam, you need to be able to trace two common sorting algorithms: Selection Sort and Insertion Sort.

Let's imagine we have an array of integers we want to sort from smallest to largest: [6, 2, 8, 4].

Selection Sort: The Patient Planner

Think of Selection Sort as the "find the best and put it in place" method. It works by repeatedly finding the smallest element in the unsorted part of the list and swapping it into its correct, final position.

Let's use our camp counselor analogy. You have a line of kids of different heights.

  1. Pass 1: You scan the entire line to find the absolute shortest kid. You then take that kid and swap them with the person currently at the front of the line. Now, the first position is correct and final. You can mentally "rope off" that spot.
  2. Pass 2: You look at the rest of the line (everyone except the first kid). You find the shortest kid among this remaining group and swap them into the second position. Now the first two spots are correct.
  3. You repeat this process, with your "unsorted" section getting smaller by one each time, until the whole line is sorted.

Let's trace Selection Sort with our array: [6, 2, 8, 4]

[[fig:selection_sort_trace]]

  • Initial Array
    [6, 2, 8, 4]
  • Pass 1
    • Look through the whole array [6, 2, 8, 4]. The minimum value is 2.
    • Swap the minimum value (2) with the element at the first position (6).
    • Result: [2, 6, 8, 4]. The 2 is now in its final, sorted position.
  • Pass 2
    • Look at the unsorted part: [6, 8, 4]. The minimum value is 4.
    • Swap the minimum (4) with the element at the first position of the unsorted part (6).
    • Result: [2, 4, 8, 6]. The 2 and 4 are now sorted.
  • Pass 3
    • Look at the unsorted part: [8, 6]. The minimum value is 6.
    • Swap the minimum (6) with the element at the first position of the unsorted part (8).
    • Result: [2, 4, 6, 8]. The 2, 4, and 6 are now sorted. The last element, 8, must also be in the correct place, so we're done!

[[fig:selection_sort_mistake]]

Insertion Sort: The Tidy Organizer

Insertion Sort works like organizing a hand of playing cards. You start with an empty left hand (the "sorted" part) and pick up cards one by one from the pile on the table (the "unsorted" part), inserting each new card into its correct position in your hand.

  1. You assume the first element is a "sorted list of one."
  2. You take the next element from the unsorted section.
  3. You compare it to the elements in the sorted section, moving from right to left. You shift the larger elements to the right to make space.
  4. You "insert" the element into the gap you've created.
  5. Repeat until all elements have been inserted.

Let's trace Insertion Sort with the same array: [6, 2, 8, 4]

  • Initial Array
    [6, 2, 8, 4]
  • Pass 1
    • The sorted portion is [6]. The unsorted is [2, 8, 4].
    • Take the next unsorted element: 2.
    • Compare 2 with 6. 2 is smaller, so shift 6 to the right. Insert 2 in its place.
    • Result: [2, 6, 8, 4]. The sorted portion is now [2, 6].
  • Pass 2
    • The sorted portion is [2, 6]. The next unsorted element is 8.
    • Compare 8 with 6. 8 is larger, so it's already in the correct spot relative to the sorted portion. No shifts needed.
    • Result: [2, 6, 8, 4]. The sorted portion is now [2, 6, 8].
  • Pass 3
    • The sorted portion is [2, 6, 8]. The next unsorted element is 4.
    • Compare 4 with 8. 4 is smaller, so shift 8 to the right. The array becomes [2, 6, _, 8].
    • Compare 4 with 6. 4 is smaller, so shift 6 to the right. The array becomes [2, _, 6, 8].
    • Compare 4 with 2. 4 is larger, so we've found the spot. Insert 4 into the gap.
    • Result: [2, 4, 6, 8]. The entire array is now sorted.

A critical point of confusion: With Insertion Sort, an element is placed in its correct position within the already sorted part, but this might not be its final position in the overall array until the very end. Notice in Pass 1, 6 moved to the second spot, but in Pass 3, it moved again to the third spot. This is different from Selection Sort, where each placement is final.

Both algorithms get the job done, but their internal processes are very different. On the AP exam, you'll be asked to trace these steps, so practice thinking through each pass for both methods.

See it in action

Variables
Narration
Step 0 / 0

Worked examples

Let's walk through a couple of examples to make this crystal clear. Pay close attention to the state of the array after each major step or "pass."

Example 1

Tracing Selection Sort

Problem: Show the state of the array [7, 3, 1, 9] after each pass of a Selection Sort that sorts in ascending (smallest to largest) order.

Solution: Remember, the rule for Selection Sort is: find the minimum in the unsorted portion and swap it with the first element of that portion.

  • Initial State
    [7, 3, 1, 9] The sorted portion is empty. The unsorted portion is the whole array.
  • After Pass 1
    • Thinking: We scan [7, 3, 1, 9]. The minimum value is 1.
    • Action: Swap the minimum (1) with the element at the start of the unsorted section (7).
    • Array State: [1, 3, 7, 9]
    • Status: The 1 is now locked in its final position. The sorted portion is [1].
  • After Pass 2
    • Thinking: We scan the remaining unsorted portion, [3, 7, 9]. The minimum is 3.
    • Action: Swap the minimum (3) with the first element of this section (3). A swap with itself! This can happen, and it's perfectly fine.
    • Array State: [1, 3, 7, 9] (No visible change, but the logic was executed).
    • Status: [1, 3] is now the sorted portion.
  • After Pass 3
    • Thinking: We scan the unsorted portion, [7, 9]. The minimum is 7.
    • Action: Swap 7 with itself.
    • Array State: [1, 3, 7, 9]
    • Status: [1, 3, 7] is now sorted. The last element 9 is automatically in place.

Final Sorted Array: [1, 3, 7, 9]

Example 2

Tracing Insertion Sort

Problem: Show the state of the array [7, 3, 1, 9] after each pass of an Insertion Sort that sorts in ascending order.

Solution: Remember, Insertion Sort's rule is: take the next unsorted element and insert it into the growing sorted portion by shifting larger elements over.

  • Initial State: [7, 3, 1, 9] We consider [7] as our initial sorted portion.

  • After Pass 1 (inserting 3):

    • Thinking
      Take 3. Compare it to 7. 3 is smaller.
    • Action
      Shift 7 one position to the right. Insert 3 into the created opening.
    • Array State
      [3, 7, 1, 9]
    • Status
      The sorted portion is now [3, 7].

  • After Pass 2 (inserting 1):

    • Thinking
      Take 1. Compare it to 7. 1 is smaller. Shift 7 right. Compare 1 to 3. 1 is smaller. Shift 3 right.
    • Action
      We've reached the beginning of the array. Insert 1.
    • Array State
      [1, 3, 7, 9]
    • Status
      The sorted portion is now [1, 3, 7].

  • After Pass 3 (inserting 9):

    • Thinking
      Take 9. Compare it to 7. 9 is larger.
    • Action
      No shifts are needed. 9 is already in the correct position relative to the sorted portion.
    • Array State
      [1, 3, 7, 9]
    • Status
      The sorted portion is the entire array.

Final Sorted Array: [1, 3, 7, 9]

Try it yourself

Ready to try it on your own? Grab a piece of paper and trace these out. The physical act of writing down each step helps build the muscle memory you'll need on the exam.

  1. 1
    Problem
    Your friend Marcus is tracking his daily basketball free throw percentages for a week: [75, 82, 68, 90, 85]. Show the state of this array after each of the first two passes of a Selection Sort in ascending order.
    • Hint: For Pass 1, what's the absolute lowest percentage in the whole list? Where does it go? For Pass 2, what's the lowest percentage of the remaining four values?
  2. 2
    Problem
    Now take that same initial array: [75, 82, 68, 90, 85]. Show the state of the array after each of the first two passes of an Insertion Sort in ascending order.
    • Hint: For Pass 1, you're just inserting 82 relative to 75. For Pass 2, you're taking 68 and finding its correct spot within the [75, 82] sorted portion. What needs to shift?
Back to AP Computer Science A Take a mock exam