Java™ How To Program (Early Objects), Tenth Edition

Section 19.6 Selection Sort

• Selection sort (p. 821) is a simple, but inefficient, sorting algorithm.

• The sort begins by selecting the smallest item and swaps it with the first element. The second iteration selects the second-smallest item (which is the smallest remaining item) and swaps it with the second element. The sort continues until the last iteration selects the second-largest element and swaps it with the second-to-last element, leaving the largest element in the last index. At the ith iteration of selection sort, the smallest i items of the whole array are sorted into the first i indices.

• The selection sort algorithm runs in O(n²) time (p. 824).