Java Reference
In-Depth Information
7.21
✓
✓
If
high
is a very large integer such as the maximum
int
value
2147483647
,
(low
+ high) / 2
may cause overflow. How do you fix it to avoid overflow?
Check
Point
7.22
Use Figure 7.9 as an example to show how to apply the binary search approach to a
search for key
10
and key
12
in list {
2
,
4
,
7
,
10
,
11
,
45
,
50
,
59
,
60
,
66
,
69
,
70
,
79
}.
7.23
If the binary search method returns
-4
, is the key in the list? Where should the key
be inserted if you wish to insert the key into the list?
Sorting, like searching, is a common task in computer programming. Many different
algorithms have been developed for sorting. This section introduces an intuitive sort-
ing algorithm:
selection sort
.
Key
Point
Suppose that you want to sort a list in ascending order. Selection sort finds the smallest
number in the list and swaps it with the first element. It then finds the smallest number
remaining and swaps it with the second element, and so on, until only a single number
remains. Figure 7.11 shows how to sort the list {
2
,
9
,
5
,
4
,
8
,
1
,
6
} using selection sort.
VideoNote
Selection sort
selection sort
swap
Select 1 (the smallest) and swap it
with 2 (the first) in the list.
2
9
5
4
8
1
6
swap
The number 1 is now in the
correct position and thus no
longer needs to be considered.
Select 2 (the smallest) and swap it
with 9 (the first) in the remaining
list.
1
9
5
4
8
2
6
swap
Select 4 (the smallest) and swap it
with 5 (the first) in the remaining
list.
The number 2 is now in the
correct position and thus no
longer needs to be considered.
8
9
6
1
2
5
4
The number 4 is now in the
correct position and thus no
longer needs to be considered.
5 is the smallest and in the right
position. No swap is necessary.
1
2
4
5
8
9
6
swap
The number 5 is now in the
correct position and thus no
longer needs to be considered.
Select 6 (the smallest) and swap it
with 8 (the first) in the remaining
list.
1
2
4
5
8
9
6
swap
The number 6 is now in the
correct position and thus no
longer needs to be considered.
Select 8 (the smallest) and swap it
with 9 (the first) in the remaining
list.
1
2
4
5
6
9
8
The number 8 is now in the
correct position and thus no
longer needs to be considered.
Since there is only one element
remaining in the list, the sort is
completed.
1
2
4
5
6
8
9
F
IGURE
7.11
Selection sort repeatedly selects the smallest number and swaps it with the first number in the list.
You know how the selection-sort approach works. The task now is to implement it in Java.
Beginners find it difficult to develop a complete solution on the first attempt. Start by writing
the code for the first iteration to find the smallest element in the list and swap it with the first
element, and then observe what would be different for the second iteration, the third, and so
on. The insight this gives will enable you to write a loop that generalizes all the iterations.
selection sort animation on
Companion Website
Search WWH ::
Custom Search