How many times does Selection Sort call the swap function on an array of n records?

n-1
  • 1
  • n
  • n \log n
  • n^2
  • It depends on the order of the records

Selection Sort first finds the largest key in an unsorted list, then the second largest, and so on.

To find the next largest key value requires searching through the entire unsorted portion of the array, but the search itself needs no swaps.

Once the next largest key is found, one swap is required to put the record in place.

We don't need to check anything on the very last pass, since at that point the first record must already be in place.