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

19.6.2 Efficiency of the Selection Sort

The selection sort algorithm runs in O(n²) time. Method selectionSort (lines 9–24) contains two for loops. The outer one (lines 12–23) iterates over the first n – 1 elements in the array, swapping the smallest remaining item into its sorted position. The inner loop (lines 17–19) iterates over each item in the remaining array, searching for the smallest element. This loop executes n – 1 times during the first iteration of the outer loop, n – 2 times during the second iteration, then n – 3, ..., 3, 2, 1. This inner loop will iterate a total of n(n – 1)/2 or (n² – n)/2. In Big O notation, smaller terms drop out and constants are ignored, leaving a Big O of O(n²).