Lesson 9: Searching and Sorting

You have made a lot of progress in developing your software engineering skills. We have seen how these skills are useful to solve a variety of problems and create programs like what we have used in our daily lives.

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

• How has your perception of software engineering changed in this unit?
• How have your software engineering skills improved in this unit?

Discussion Goal: Students share how their perception of software engineering has changed, including how software engineering involves translating everyday approaches to searching and sorting information to a programming language. Students identify the software engineering skills and characteristics they feel they improved in this unit.

We have learned a lot about searching and sorting algorithms in this unit! These searching and sorting algorithms expand our skills and capabilities to help us solve problems that software engineers work on every day. Let's review the searching and sorting algorithms we have learned.

Do This: Review the lesson objectives.

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

• How does the linear search algorithm work?
• How does the binary search algorithm work?
• Which is more efficient? Why?
• When is the binary search algorithm not the most efficient?

Discussion Goal: Students recall that the linear search algorithm checks each element in the data structure from first to last until the target is found, while the binary search algorithm splits the list in half repeatedly until the target is found. Students note that the binary search is more efficient because it has fewer execution counts but only works when the list is sorted.

Have students recall the best case, average case, and worst case for the linear search and binary search algorithms. Ask guiding questions to help students identify which is most efficient, or you can write lists of numbers on the board and have students apply each algorithm to the list to determine the execution counts.

Display: Show the video – Searching Algorithms.

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

• How does the selection sort algorithm work?
• How does the insertion sort algorithm work?
• How does the merge sort algorithm work?
• Which is more efficient? Why?

Discussion Goal: Students recall that the selection sort algorithm finds the minimum value in the list and swaps with the previous element and repeats this process until the list is in order. Students recall that the insertion sort algorithm inserts the element into the correct position and shifts the rest of the elements over. Students note that the merge sort algorithm is a recursive algorithm that repeatedly divides the list into smaller lists until each list contains only one value and then merges the elements back together into one list. Students also note that each algorithm is fairly comparable in efficiency but one might be best depending on the size of the list.

Display: Show the video – Sorting Algorithms.

Do This: Direct students to Level 1 on Code Studio to complete Levels 1, 2, and 3. Students complete a Check for Understanding on Level 1, then continue to Level 2 to complete a choice level to implement a binary search. On Level 3, students complete a choice level to implement a sorting algorithm.

Encourage students to write pseudocode first, then translate their solution to Java.

Before working towards the next benchmark, it is helpful to assess your achievement of this benchmark and get feedback on your development so far.

Do This: Click through the animated slide to have students participate in the Code Review Call and Response.

Do This: Direct students to complete a code review on Level 4.

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.

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.