C++ Programming: From Problem Analysis to Program Design, Eighth Edition 16-1
Chapter 16
Search, Sorting, and the vector Type
A Guide to this Instructor’s Manual:
We have designed this Instructor’s Manual to supplement and enhance your teaching
experience through classroom activities and a cohesive chapter summary.
This document is organized chronologically, using the same headings that you see in the
textbook. Under the headings, you will find lecture notes that summarize the section, Teacher
Tips, Classroom Activities, and Lab Activities. Pay special attention to teaching tips and
activities geared towards quizzing your students and enhancing their critical thinking skills.
In addition to this Instructor’s Manual, our Instructor’s Resources also contain PowerPoint
Presentations, Test Banks, and other supplements to aid in your teaching experience.
At a Glance
Instructor’s Manual Table of Contents
• Overview
• Objectives
• Teaching Tips
• Quick Quizzes
• Class Discussion Topics
• Additional Projects
• Additional Resources
• Key Terms
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 16-2
Lecture Notes
Overview
Chapter 16 discusses searching and sorting algorithms in detail. Students will become
familiar with implementing searching and sorting algorithms and with analyzing the
performance of each algorithm. The chapter concludes with an introduction to the
vector type.
Objectives
In this chapter, the student will:
• Learn about list processing and how to search a list using sequential search
• Explore how to sort an array using the bubble sort and insertion sort algorithms
• Learn how to implement the binary search algorithm
• Become familiar with the vector type
Teaching Tips
List Processing
1. Explain that a list is a collection of values. Review the common basic operations
performed on lists.
Searching
Bubble Sort
1. Introduce the bubble sort algorithm using the example list in Figure 16-1. The iterations
of bubble sort are shown in Figures 16-2 through 16-5 and the bubble sort
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 16-3
Insertion Sort
12.
Teaching
Tip
Compare the insertion sort, bubble sort and selection sort algorithms using these
animations: http://www.sorting-algorithms.com/
2. Examine the selection sort pseudocode, function, and performance statistics.
Teaching
Tip
Point out that there are many different sorting algorithms. Several additional
ones can be demonstrated here: https://www.toptal.com/developers/sorting-
algorithms/
Quick Quiz 1
1. Define a key comparison.
2. True or False: The sequential search algorithm requires that the list be sorted.
3. True or False: Insertion sort finds the location of the smallest element in the unsorted
portion of the list and moves it to the top of the unsorted portion of the list.
Binary Search
1. Point out that sequential search is inefficient for large lists. Binary search provides an
alternate approach, but can only be used on sorted lists. Review the example of binary
search shown in Figures 16-13 through 16-15.
Teaching
Tip
Ask students to discuss whether it would be a good idea to split the list into three
or more parts rather than two. Why or why not?
2. Review the binary search function and discuss the key comparisons that result from
using the function.
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 16-4
Performance of Binary Search
vector Type (class)
1. Introduce the vector type that can be used to implement a list of variable size in C++.
Teaching
Tip
Students may find the following vector tutorial to be useful:
http://www.dreamincode.net/forums/topic/33631-c-vector-tutorial/
2. Describe the operations on a vector object listed in Table 16-2. Uses of these
operations are provided in Examples 16-3 through 16-5.
3. Encourage students to walk through the Programming Examples at the end of this
chapter with a partner to consolidate their understanding of operations on arrays.
Initializing vector Objects during Declaration
Quick Quiz 2
1. True or False: Binary search requires a sorted list.
2. If L is a sorted list of size 1024, at most ____________________ comparisons are
needed to determine whether x is in L using binary search.
3. The ____________________ function is used to set the size of a vector object.
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 16-5
Class Discussion Topics
1. Discuss any assumptions that have been made regarding sorting or searching with
duplicate items in a list. How would the searching and sorting algorithms presented in
this chapter handle duplicates?
2. Ask the students to think about alternate searching methods to sequential and binary
search. What other search techniques exist? How do they compare with sequential and
binary search in terms of performance?
Additional Projects
1. Rewrite the birthday program from Chapter 8 using vectors.
Additional Resources
1. Vector type:
2. Searching:
3. Sorting:
Key Terms
➢ Binary search: a very fast search algorithm that uses the divide-and-conquer technique