Java Reference
In-Depth Information
QUICK REVIEW
1
.
A list is a set of elements of the same type.
2
.
The length of a list is the number of elements in the list.
3
.
A one-dimensional array is a convenient data structure for storing and
processing lists.
4
.
A sequential search algorithm searches the list for a given item, starting with
the first element in the list. It continues comparing this item with the
elements in the list until either the item is found, or the list has no more
elements left to compare with the search item.
5
.
On average, a sequential search searches half the list.
6
.
In a selection sort, a list is sorted by selecting elements in the list, one at a
time, and moving them to their proper positions. This algorithm finds the
location of the smallest element in the unsorted portion of the list and
moves it to the top of the unsorted portion (i.e., the whole list) of the list.
For a list of length n, selection sort makes exactly
nðn
1
Þ
7
.
key comparisons
2
and 3(n - 1) item assignments.
8
.
Insertion sort algorithm sorts the list by inserting each element in its proper
place.
For a list of length n, on average, an insertion sort makes
n
2
þ
3
n
4
9
.
key
4
comparisons and about
nðn
1
Þ
4
item assignments.
10
.
In general, binary search is much faster than a sequential search.
11
.
Binary search requires that the list elements are in order, that is, sorted.
EXERCISES
1.
Mark the following statements as true or false.
a.
A sequential search of a list assumes that the list is in ascending order.
b.
A binary search of a list assumes that the list is in sorted order.
c.
A binary search is faster on ordered lists and slower on unordered lists.
2.
Consider the following list:
63 45 32 98 46 57 28 100
Using the sequential search (given in Chapter 9), how many comparisons are
required to determine whether the following items are in the list? (Recall that
comparisons mean item comparisons, not index comparisons.)
90
57
63
120
a.
b.
c.
d.
Search WWH ::
Custom Search