Searching, Sorting and Big O - Java: How to Program Early Objects - page 821

much faster than selection sort and insertion sort but harder to program . We focus on
sorting arrays of primitive-type data, namely int s. It's possible to sort arrays of class objects
as well, as we demonstrated in Section 16.7.1 by using the built-in sorting capabilities of
the Collections API.
19.6 Selection Sort
Selection sort is a simple, but inefficient, sorting algorithm. If you're sorting in increasing
order, its first iteration selects the smallest element in the array and swaps it with the first
element. The second iteration selects the second-smallest item (which is the smallest item
of the remaining elements) and swaps it with the second element. The algorithm continues
until the last iteration selects the second-largest element and swaps it with the second-to-
last index, leaving the largest element in the last index. After the i th iteration, the smallest
i items of the array will be sorted into increasing order in the first i elements of the array.
As an example, consider the array
34 56 4 10 77 51 93 30 5 52
A program that implements selection sort first determines the smallest element (4) of this
array, which is contained in index 2. The program swaps 4 with 34, resulting in
4 56 34 10 77 51 93 30 5 52
The program then determines the smallest value of the remaining elements (all elements
except 4), which is 5, contained in index 8. The program swaps 5 with 56, resulting in
4 5 34 10 77 51 93 30 56 52
On the third iteration, the program determines the next smallest value (10) and swaps it
with 34.
4 5 10 34 77 51 93 30 56 52
The process continues until the array is fully sorted.
4 5 10 30 34 51 52 56 77 93
After the first iteration, the smallest element is in the first position. After the second iter-
ation, the two smallest elements are in order in the first two positions. After the third it-
eration, the three smallest elements are in order in the first three positions.
19.6.1 Selection Sort Implementation
Class SelectionSortTest (Fig. 19.4) contains:
• static method selectionSort to sort an int array using the selection sort algo-
rithm
• static method swap to swap the values of two array elements
• static method printPass to display the array contents after each pass, and
• main to test method selectionSort .
As in the searching examples, main (lines 57-72) creates an array of int s named data and
populates it with random int s in the range 10 - 99 . Line 68 tests method selectionSort .