Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 801

in the first position in the array, so that the smallest value will be at the front of the
array. In this case, nums[0] and nums[2] are swapped:

0 1 2 3 4 5

1 123 12 28 183 16

sorted to be sorted

The element at index 0 now has the right value, and only the elements at indexes 1
through 5 remain to be ordered. The algorithm repeats the process of scanning the
unsorted portion of the array and looking for the smallest element. On the second
pass, it scans the remaining five elements and finds that nums[2] , which equals 12 ,is
the smallest element. The program swaps this value with nums[1] . After this swap,
the sorted area of the array consists of its first two indexes:

0 1 2 3 4 5

1 12 123 28 183 16

sorted to be sorted

Now nums[0] and nums[1] have the correct values. The third pass of the algo-
rithm scans the remaining four unsorted elements and finds that the smallest one is
nums[5] , which equals 16 . It swaps this element with nums[2] .

0 1 2 3 4 5

1 12 16 28 183 123

sorted to be sorted
The algorithm continues this process until all the elements have the proper values.
Each pass involves a scan followed by a swap. The scan/swap occurs five times to
process six elements. You don't need to perform a sixth scan/swap because, if the
first five elements have the correct values, the sixth element will be correct as well.
Here is a pseudocode description of the execution of the selection sort algorithm
over an array nums that has six elements:

for (each i from 0 to 4) {
scan nums[i] through nums[5] for the smallest value.
swap nums[i] with the smallest element found in the scan.

}

You can write pseudocode like the following for the scan:

smallest = lowest array index of interest.
for (all other index values of interest) {
if (nums[index] < nums[smallest]) {
smallest = index.

}

}