Previous: 10.6 Common Errors
Up: 10 Sorting and Searching
Next: 10.8 Exercises
Previous Page: 10.6 Common Errors
Next Page: 10.8 Exercises

10.7 Summary

In this chapter we have developed algorithms for searching a collection of data for a specific element, called the key. We saw a simple algorithm, linear search which started at the beginning of the data, and compared each element against the key until it was found, or the data was exhausted. However, linear search is not very efficient if the number of elements to search is large. In order to develop more efficient algorithms, we need to take advantage of the order of the data. Therefore, we next discussed how we can arrange the elements in an array in a specified order - a process called sorting. We developed three sorting algorithms: selection sort, bubble sort, and insertion sort. The first two of these are useful when all of the data is already stored in an array, and insertion sort can be used to sort the data as it is being read into the array.

Once we have the data sorted, we developed a more efficient searching algorithm --- binary search. This algorithm worked by dividing the data in half, and deciding in which half the key would occur. With each step, then, we can eliminate half of the data from further consideration.

These searching and sorting techniques are general and may be applied to any type of data. We used them in our payroll task to find individual payroll records in a database given an id as the key.

Finally, we discussed the use of the polymorphic data type, or generic pointers to implement a common operation that may be applied to data of different types.