Java Reference
In-Depth Information
Initially, the entire list is unsorted. So we find the smallest item in the list. The smallest
item is at position 6, as shown in Figure 14-3(a). Because this is the smallest item, it must
be moved to position
0
. So we swap
16
(that is,
list[0]
) with
5
(that is,
list[6]
), as
shown in Figure 14-3(b). After swapping these elements, the resulting list is as shown in
Figure 14-3(c).
Figure 14-4 shows the elements of
list
in the second iteration.
list
5
30
24
7
62
45
16
55
[0]
[1]
5
30
24
7
62
45
16
55
5
7
24
30
62
45
16
55
swap
[2]
[3]
unsorted
list
[4]
[5]
unsorted
list
smallest
[6]
[7]
(b)
(a)
(c)
FIGURE 14-4
Elements of
list
during the second iteration
Now the unsorted list is
list[1]...list[7]
. So we find the smallest element in
the unsorted list. The smallest element is at position 3, as shown in Figure 14-4(a).
Because the smallest element in the unsorted list is at position 3, it must be moved to
position 1. So we swap
7
(that is,
list[3]
)with
30
(that is,
list[1]
), as shown in
Figure 14-4(b). After swapping
list[1]
with
list[3]
, the resulting list is as shown
in Figure 14-4(c).
Now the unsorted list is
list[2]...list[7]
. So we repeat the preceding process of
finding the (position of the) smallest element in the unsorted portion of the list and
moving it to the beginning of the unsorted portion of the list. The selection sort thus
involves the following steps.
In the unsorted portion of the list:
a. Find the location of the smallest element.
b. Move the smallest element to the beginning of the unsorted list.
Initially, the entire list, that is,
list[0]...list[listLength - 1]
, is the unsorted list.
After executing steps a and b, the unsorted list is
list[1]...list[listLength - 1]
.
After we execute steps a and b the second time, the unsorted list is
list[2]...list[listLength - 1]
, and so on. We can keep track of the unsorted
portion of the list and repeat steps a and b with the help of the following
for
loop:
Search WWH ::
Custom Search