Java Reference
In-Depth Information
list[k +
1
] = currentElement;
14
15 }
16 }
17 }
insert
The
insertionSort(double[] list)
method sorts any array of
double
elements. The
method is implemented with a nested
for
loop. The outer loop (with the loop control variable
i
) (line 4) is iterated in order to obtain a sorted sublist, which ranges from
list[0]
to
list[i]
. The inner loop (with the loop control variable
k
) inserts
list[i]
into the sublist
from
list[0]
to
list[i-1]
.
To better understand this method, trace it with the following statements:
double
[] list = {
1
,
9
,
4.5
,
6.6
,
5.7
,
-4.5
};
InsertionSort.insertionSort(list);
6.19
✓
✓
Use Figure 6.10 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
}.
Check
Point
6.20
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?
6.21
Use Figure 6.12 as an example to show how to apply the selection-sort approach to
sort {
3.4
,
5
,
3
,
3.5
,
2.2
,
1.9
,
2
}.
6.22
Use Figure 6.13 as an example to show how to apply the insertion-sort approach to
sort {
3.4
,
5
,
3
,
3.5
,
2.2
,
1.9
,
2
}.
6.23
How do you modify the
selectionSort
method in Listing 6.8 to sort numbers in
decreasing order?
6.24
How do you modify the
insertionSort
method in Listing 6.9 to sort numbers in
decreasing order?
The
java.util.Arrays
class contains useful methods for common array operations
such as sorting and searching.
Key
Point
The
java.util.Arrays
class contains various static methods for sorting and searching
arrays, comparing arrays, filling array elements, and returning a string representation of the
array. These methods are overloaded for all primitive types.
You can use the
sort
method to sort a whole array or a partial array. For example, the fol-
lowing code sorts an array of numbers and an array of characters.
sort
double
[] numbers = {
6.0
,
4.4
,
1.9
,
2.9
,
3.4
,
3.5
};
// Sort the whole array
java.util.Arrays.sort(numbers);
char
[] chars = {
'a'
,
'A'
,
'4'
,
'F'
,
'D'
,
'P'
};
// Sort part of the array
java.util.Arrays.sort(chars,
1
,
3
);
Invoking
sort(numbers)
sorts the whole array
numbers
. Invoking
sort(chars, 1, 3)
sorts a partial array from
chars[1]
to
chars[ ]
.
You can use the
binarySearch
method to search for a key in an array. The array must be pre-
sorted in increasing order. If the key is not in the array, the method returns
-(insertionindex
+ 1)
. For example, the following code searches the keys in an array of integers and an array of
characters.
3-1
binarySearch
int
[] list = {
2
,
4
,
7
,
10
,
11
,
45
,
50
,
59
,
60
,
66
,
69
,
70
,
79
};
System.out.println(
"(1) Index is "
+
java.util.Arrays.binarySearch(list,
11
));
