C++ How to Program, Ninth Edition

20. Searching and Sorting

With sobs and tears he sorted out Those of the largest size ...

—Lewis Carroll

Attempt the end, and never stand to doubt; Nothing’s so hard, but search will find it out.

—Robert Herrick

‘Tis in my memory lock’d, And you yourself shall keep the key of it.

—William Shakespeare

Objectives

In this chapter you’ll:

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

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

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

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

Outline

20.1 Introduction

20.2 Searching Algorithms ...