Java Reference
In-Depth Information
You can then incorporate this pseudocode into your larger pseudocode as follows:
for (each i from 0 to 4) {
smallest = i.
for (each index between (i + 1) and 5) {
if (nums[index] < nums[smallest]) {
smallest = index.
}
}
swap nums[i] with nums[smallest].
}
You can translate this pseudocode almost directly into Java, except for the swap
process. In Chapter 7, we wrote a swap method to swap two elements of an array. We
can reuse it here:
public static void swap(int[] list, int i, int j) {
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
We can also modify the code to work with arrays of any size. The following code
implements the overall selection sort algorithm:
// places the elements of the given array into sorted order
// using the selection sort algorithm
// post: array is in sorted (nondecreasing) order
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
// find index of smallest element
int smallest = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[smallest]) {
smallest = j;
}
}
swap(a, i, smallest); // swap smallest to front
}
}
Since selection sort makes roughly N passes over an array of N elements, its per-
formance is O ( N 2 ). Technically, it examines N
...
( N
1)
( N
2)
3
2
1 elements, because each pass starts one index ahead of where the last one started.
Chapter 3 mentioned a mathematical identity which states that the sum of all integers
 
Search WWH ::




Custom Search