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


Introduction to Computers, the Internet and World Wide Web

Introduction to C++ Programming

Introduction to Classes and Objects

Control Statements: Part 1

Control Statements: Part 2

Functions and an Introduction to Recursion

Arrays and Vectors

Pointers and Pointer-Based Strings

Classes: A Deeper Look, Part 1

Classes: A Deeper Look, Part 2

Operator Overloading; String and Array Objects

Object-Oriented Programming: Inheritance

Object-Oriented Programming: Polymorphism

Templates

Stream Input/Output

Exception Handling

File Processing

Class string and String Stream Processing

Web Programming

Searching and Sorting

Data Structures

Bits, Characters, C-Strings and structs

Standard Template Library (STL)

Other Topics

Appendix A. Operator Precedence and Associativity Chart

Appendix B. ASCII Character Set

Appendix C. Fundamental Types

Appendix D. Number Systems

Appendix E. C Legacy Code Topics

Appendix F. Preprocessor

Appendix G. ATM Case Study Code

Appendix H. UML 2: Additional Diagram Types

Appendix I. C++ Internet and Web Resources

Appendix J. Introduction to XHTML

Appendix K. XHTML Special Characters

Appendix L. Using the Visual Studio .NET Debugger

Appendix M. Using the GNU C++ Debugger

Bibliography



C++ How to Program
C++ How to Program (5th Edition)
ISBN: 0131857576
EAN: 2147483647
Year: 2004
Pages: 627

Flylib.com © 2008-2020.
If you may any questions please contact us: flylib@qtcs.net