Lesson 6: Insertion Sort

In the previous lesson, we talked about one possible sorting algorithm. As you know by now, there are many different ways to complete a single task when programming.

Group: Place students in pairs.

Do This: Have students brainstorm potential solutions for sorting the list.

There are many different ways to sort items numerically, alphabetically, or based on different characteristics. Additionally, there are many different algorithms to sort items. Today, we will explore another sorting algorithm called the insertion sort.

Do This: Review the lesson objectives.

Group: Place students in pairs.

Do This: Direct students to Level 1 on Code Studio to investigate the program with a partner. Students make the changes to the program as prompted.

Discuss: Click through the animated slide to display the prompts.

• What do you notice about the code in this program?
• What do you wonder about the code in this program?

Discussion Goal: Students notice that the insertion sort method traverses the array and compares the current element to the element before it. Students identify that if the current element is smaller than the element before it, it continues to check the elements before until it finds the correct position to insert the current element. Students may wonder why the insertion sort is more efficient than the selection sort.

Do This: Click through the animated slide to define insertion sort and explain the pseudocode for the algorithm.

We know that there are a lot of different sorts, so how does a programmer decide which to use?

Discuss: Use the Retrieve-Pair-Share strategy to discuss the prompt.

• What qualities are important when deciding whether one algorithm is better than another?

Discussion Goal: Students share possible pros and cons of different algorithms and how these are used to choose a specific algorithm for a particular scenario.

Let's compare the selection and insertion sort algorithms by first looking at the efficiency of the code. In this case, an algorithm is more efficient if it does fewer shifts.

Distribute: Give each pair a copy of the Sorting Comparison handout.

Do This: Have students complete the Sorting Comparison handout.

Do This: Have students share the number of swaps and shifts as a class. Create a table of the number of shifts for each initial condition on the board.

Emphasize that the number of shifts refers to every shift that the algorithm performs in the insertion sort, not the final shift to put an element in the correct position.

One partner can complete the insertion sort while the other completes the selection sort. Alternatively, groups can work together, choosing the same numbers. One pair of students can complete insertion sort while the other does selection.

Discuss: Click through the animated slides to display the prompts. Use the Retrieve-Pair-Share strategy to discuss the prompts.

• Which algorithm is best when we consider efficiency?
• Which algorithm is best when we consider readability?
• Which algorithm is best when we consider ease of programming?

Discussion Goal: Students notice that insertion sort works faster on a sorted list, while selection sort works faster on an inverted list. Both algorithms perform similarly on randomly sorted elements. Students realize that one algorithm may be better than the other in specific circumstances, but both are generally similar.

We just learned a lot of new information today, which may have even answered some of the Need to Know questions you wrote down about the Creative Coding Project. As we progress through the unit, it is helpful to stop and note what we have learned that is related to or useful for the project.

Do This: Have students review the questions they wrote in the "Need to Know" column on page two of their Creative Coding with the Console Project Planning Guide. Students add new questions to this column, check off any answered questions, and write answers to any questions in the "Learned" column.

Do This: Have students share what they added to their chart with a partner.

If time permits, you can also have students share as a class.

Do This: Review the concepts covered in this lesson.

Display: Key Vocabulary

Check For Understanding Question(s) and solutions can be found in each lesson on Code Studio. These questions can be used for an exit ticket.

To assign questions from the AP Classroom Question Bank that align with this lesson, create a custom quiz in AP Classroom by searching the Question Bank for the Essential Knowledge statements listed at the top of this lesson plan. You can find instructions and video demonstrations to do this on AP Central.

The following Topic Questions in AP Classroom can be assigned as a formative assessment for this lesson:

• Topic Questions 7.6

Note: Some Learning Objectives and Essential Knowledge statements in the suggested Topic Questions are covered in later units.