C++ How to Program, 10/e

20 Searching and Sorting

Objectives

In this chapter you’ll:

• Search for a given value in an array using linear search and binary search.

• Sort an array using insertion sort, selection sort and the recursive merge sort algorithms.

• Use Big O notation to express the efficiency of searching and sorting algorithms and to compare their performance.

• Understand the nature of algorithms of constant, linear and quadratic runtime.

Outline

1. 20.1 Introduction

2. 20.2 Searching Algorithms

   1. 20.2.1 Linear Search

   2. 20.2.2 Binary Search

3. 20.3 Sorting Algorithms

   1. 20.3.1 Insertion Sort

   2. 20.3.2 Selection Sort

   3. 20.3.3 Merge Sort (A Recursive Implementation)

4. 20.4 Wrap-Up

1. Summary

2. Self-Review Exercises

3. Answers to Self-Review Exercises

4. Exercises