Introduction

Searching data involves determining whether a value (referred to as the search key) is present in the data and, if so, finding the value's location. Two popular search algorithms are the simple linear search (introduced in Section 7.7) and the faster but more complex binary search, which is introduced in this chapter.

Sorting places data in order, typically ascending or descending, based on one or more sort keys. A list of names could be sorted alphabetically, bank accounts could be sorted by account number, employee payroll records could be sorted by social security number, and so on. Previously, you learned about insertion sort (Section 7.8) and selection sort (Section 8.6). This chapter introduces the more efficient, but more complex merge sort. Figure 20.1 summarizes the searching and sorting algorithms discussed in the examples and exercises of this book. This chapter also introduces Big O notation, which is used to estimate the worst-case runtime for an algorithmthat is, how hard an algorithm may have to work to solve a problem.

Figure 20.1. Searching and sorting algorithms in this text.

(This item is displayed on page 977 in the print version)

Chapter	Algorithm	Location
Searching Algorithms
7	Linear search	Section 7.7
20	Binary search	Section 20.2.2
	Recursive linear search	Exercise 20.8
	Recursive binary search	Exercise 20.9
21	Binary tree search	Section 21.7
	Linear search of a linked list	Exercise 21.21
23	binary_search standard library function	Section 23.5.6
Sorting Algorithms
7	Insertion sort	Section 7.8
8	Selection sort	Section 8.6
20	Recursive merge sort	Section 20.3.3
	Bubble sort	Exercises 20.5 and 20.6
	Bucket sort	Exercise 20.7
	Recursive quicksort	Exercise 20.10
21	Binary tree sort	Section 21.7
23	sort standard library function	Section 23.5.6
	Heap sort	Section 23.5.12