SEARCHING AND SORTING - Java Programming: From Problem Analysis to Program Design - page 909

with every element in the list . A sequential search is therefore not efficient for large lists.
In fact, it can be proved that, on average, the number of comparisons (that is, key
comparisons) made by a sequential search is equal to half the size of the list. So, for a list
of size 1000, on average, the sequential search makes about 500 comparisons. Similarly, for
a list of size 1,000,000, on average, the sequential search makes about 500,000 compar-
isons. (Imagine how much time it will take if you search a telephone book for ''Smith''
sequentially starting at A's and go through all the records until you find Smith.)
This search algorithm does not assume that the list is sorted. If the list is sorted, then
you can improve the search algorithm. Next, we discuss how to sort a list .

Selection Sort
Many sorting algorithms are available in the literature. This section describes the sorting
algorithm called the selection sort, to sort a list.
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. The first time we locate the smallest item in the entire list;
the second time we locate the smallest item in the list starting from the second element in
the list; and so on. For example, suppose you have the list shown in Figure 14-2.

[0] [1] [2] [3] [4] [5] [6] [7]

list 16 30 24 7 62 45 5 55

FIGURE 14-2 List of 8 elements

Figure 14-3 shows the elements of list in the first iteration.

list

16 16

30
24
7
62
45
5
55

5
30
24
7
62
45
16
55

[0]
[1]

30
24
7
62
45
5
55

[2]

unsorted
list

swap

[3]

unsorted
list

[4]
[5]

1
4

[6]

[7]

smallest

(a) (b) (c)

FIGURE 14-3 Elements of list during the first iteration