www.gibmonks.com

Main Page

[Page 975]

## Chapter 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

It is an immutable law in business that words are words, explanations are explanations, promises are promises but only performance is reality.

Harold S. Green

OBJECTIVES

In this chapter you will learn:

• To search for a given value in a vector using binary search.

• To sort a vector using the recursive merge sort algorithm.

• To determine the efficiency of searching and sorting algorithms.

[Page 976]

Outline

20.1 Introduction

20.2 Searching Algorithms

20.2.1 Efficiency of Linear Search

20.2.2 Binary Search

20.3 Sorting Algorithms

20.3.1 Efficiency of Selection Sort

20.3.2 Efficiency of Insertion Sort

20.3.3 Merge Sort (A Recursive Implementation)

20.4 Wrap-Up

Summary

Terminology

Self-Review Exercises