Previous: Chapter 10
Up: Chapter 10
Previous Page: Chapter 10
Next Page: 10.1 Finding a Data Item - The Search Problem
Previous: Chapter 10
Up: Chapter 10
Previous Page: Chapter 10
Next Page: 10.1 Finding a Data Item - The Search Problem
One very common application for computers is storing and retrieving information. For example, the telephone company stores information such as the names, addresses and phone numbers of its customers. When you dial directory assistance to get the phone number for someone, the operator must look up that particular piece of information from among all of data that has been stored. Taken together, all of this information is one form of a data base which is organized as a collection of records. Each record consists of several fields, each containing one piece of information, such as the name, address, phone number, id number, social security number or part number, etc..
As the amount of information to be stored and accessed becomes very large, the computer proves to be a useful tool to assist in this task. Over the years, as computers have been applied to these types of tasks, many techniques and algorithms have been developed to efficiently maintain and process information in data bases. In this chapter, we will develop and implement some of the simpler instances of these algorithms. The processes of ``looking up'' a particular data record in the data base is called searching. We will look at two different search algorithms; one very easy to implement, but inefficient, the other much more efficient. As we will see, in order to do an efficient search in a data base, the records must be maintained in some order. For example, consider the task of finding the phone number in the phone book of someone whose name you know, as opposed to trying to find the name of someone whose phone number you know in the same book.
The process of ordering the records in a data base is called sorting. We will discuss three sorting algorithms and their implementation in this chapter, as well. Sorting and searching together constitute a major area of study in computational methods. We present some of these methods here to introduce this area of computing as well as to make use of some of the programming techniques we have developed in previous chapters.
As we develop these algorithms, we use a very simple data base
of records consisting of single integers only.
We conclude the chapter by applying the searching and sorting techniques
to our payroll data base with records consisting of multiple numeric fields.
In Chapter we will see how these same algorithms can be
applied to string data types described in Chapter
.