Sorting, Searching, and Merging - Advanced Topics in Java: Core Concepts in Data Structures - page 3

6 th pass

• Find the smallest number in positions

5 to 6 ; the smallest is 65 , found in position 6 .

• Interchange the numbers in positions

5 and 6 . This gives us the following:

The array is now completely sorted. Note that once the 6 th largest (65) has been placed in its final position (5),
the largest (79) would automatically be in the last position (6).
In this example, we made six passes. We will count these passes by letting the variable h go from 0 to 5 . On each
pass, we find the smallest number from positions h to 6 . If the smallest number is in position s , we interchange the
numbers in positions h and s .
In general, for an array of size n , we make n-1 passes. In our example, we sorted 7 numbers in 6 passes.
The following is a pseudocode outline of the algorithm for sorting num[0..n-1] :

for h = 0 to n - 2
s = position of smallest number from num[h] to num[n-1]
swap num[h] and num[s]
endfor

We can implement this algorithm as follows, using the generic parameter list :

public static void selectionSort(int[] list, int lo, int hi) {
//sort list[lo] to list[hi] in ascending order
for (int h = lo; h < hi; h++) {
int s = getSmallest(list, h, hi);
swap(list, h, s);
}
}

The two statements in the for loop could be replaced by the following:

swap(list, h, getSmallest(list, h, hi));

We can write getSmallest and swap as follows:

public static int getSmallest(int list[], int lo, int hi) {
//return location of smallest from list[lo..hi]
int small = lo;
for (int h = lo + 1; h <= hi; h++)
if (list[h] < list[small]) small = h;
return small;
}
public static void swap(int list[], int i, int j) {
//swap elements list[i] and list[j]
int hold = list[i];
list[i] = list[j];
list[j] = hold;
}