Of course, for any particular search, the time required will depend on where in the list the match occurs.
If the first name is a match, then it doesn??™t matter how long the list is. If the name does not occur in the list, the
search will always require comparing the search name with all the names in the list.
We say the sequential search algorithm is ??(n) because in the average case, and the worst case, its performance
slows in proportion to n, the length of the list. Sometimes algorithms are characterized for best-case performance,
but usually average performance, and particularly worst-case performance are reported. The average case is usually
better for setting expectations, and the worst case provides a boundary upon which one can rely.
Insertion sort??”An example of order of growth n2??”Q(n2)
Programmers have designed many algorithms for sorting numbers, because one needs this functionality
frequently. One sorting algorithm is called the insertion sort, and it works in a manner similar to a card player
organizing his hand. Each time the algorithm reads a number (card), it places the number in its sorted position
among the numbers (cards) it has already sorted.
On the next page we show the pseudocode for the insertion sort.
Pages:
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55