Java Reference
In-Depth Information
SR 10.14 Show the sequence of changes the insertion sort algorithm makes to
the following list of numbers:
5 7 1 8 2 4 3
SR 10.15 In what way are the sort methods defined in this chapter polymorphic?
SR 10.16 Which is better: selection sort or insertion sort? Explain.
10.5 Searching
Like sorting, searching for an item is another classic computing problem, and
also lends itself to a polymorphic solution. Searching is the process of finding a
designated target element within a group of items. For example, we may need to
search for a person named Vito Andolini in a club roster.
The group of items to be searched is sometimes called the search pool . The
search pool is usually organized into a collection of objects of some kind, such
as an array.
Whenever we perform a search, we must consider the possibility that the target
is not present in the group. Furthermore, we would like to perform a search effi-
ciently. We don't want to make any more comparisons than we have to.
In this section we examine two search algorithms, linear search and binary
search. We explore versatile, polymorphic implementations of these algorithms
and compare their efficiency.
Linear Search
If the search pool can be examined one element at a time in any order, one
straightforward way to perform the search is to start at the beginning of the list
and compare each value in turn to the target element. Eventually, either the target
element will be found or we will come to the end of the list and conclude that the
target doesn't exist in the group.
This approach is called a linear search, because it begins at one end and scans
the search pool in a linear manner. This process is depicted in Figure 10.4. When
items are stored in an array, a linear search is relatively simple.
The program shown in Listing 10.11 is similar to the PhoneList program from
the previous section. It begins with the same, unsorted array of Contact objects.
It then performs a linear search for a contact and prints the result. Then it calls
the selectionSort method, which was discussed in the previous section, to sort
the contacts. It then searches for another contact using a binary search, which is
discussed later in this section.
 
Search WWH ::




Custom Search