Java Reference
In-Depth Information
Listing 6.8 implements the solution.
L
ISTING
6.8
SelectionSort.java
1
public class
SelectionSort {
2
/** The method for sorting the numbers */
3
public static void
selectionSort(
double
[] list) {
4
5
for
(
int
i =
0
; i < list.length -
1
; i++) {
// Find the minimum in the list[i..list.length-1]
6
double
currentMin = list[i];
7
int
currentMinIndex = i;
8
9
10
if
(currentMin > list[j]) {
11 currentMin = list[j];
12 currentMinIndex = j;
13 }
14 }
15
16
// Swap list[i] with list[currentMinIndex] if necessary
17
if
(currentMinIndex != i) {
18 list[currentMinIndex] = list[i];
19 list[i] = currentMin;
20 }
21 }
22 }
23 }
select
for
(
int
j = i +
1
; j < list.length; j++) {
swap
The
selectionSort(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 find the smallest element in the list, which ranges from
list[i]
to
list[list.length-1]
, and exchange it with
list[i]
.
The variable
i
is initially
0
. After each iteration of the outer loop,
list[i]
is in the right
place. Eventually, all the elements are put in the right place; therefore, the whole list is sorted.
To understand this method better, trace it with the following statements:
double
[] list = {
1
,
9
,
4.5
,
6.6
,
5.7
,
-4.5
};
SelectionSort.selectionSort(list);
6.11.2 Insertion Sort
Suppose that you want to sort a list in ascending order. The insertion-sort algorithm sorts a list
of values by repeatedly inserting a new element into a sorted sublist until the whole list is
sorted. Figure 6.13 shows how to sort the list {
2
,
9
,
5
,
4
,
8
,
1
,
6
} using insertion sort.
The algorithm can be described as follows:
insertion sort animation on
Companion Website
for (int i = 1; i < list.length; i++) {
insert list[i] into a sorted sublist list[0..i-1] so that
list[0..i] is sorted.
}
To insert
list[i]
into
list[0..i-1]
, save
list[i]
into a temporary variable, say
currentElement
. Move
list[i-1]
to
list[i]
if
list[i-1] > currentElement
,
move
list[i-2]
to
list[i-1]
if
list[i-2] > currentElement
, and so on, until
list[i-k] <= currentElement
or
k > i
(we pass the first element of the sorted list).
Assign
currentElement
to
list[i-k+1]
. For example, to insert
4
into {
2
,
5
,
9
} in Step 4
in Figure 6.14, move
list[2]
(
9
) to
list[3]
since
9 > 4
, and move
list[1]
(
5
) to
list[2]
since
5 > 4
. Finally, move
currentElement
(
4
) to
list[1]
.
