Project ForgeAlgorithms
Sorting & Searching
GATE 2013
Easy
Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
- AO(log n)
- O(n)
- CO(n log n)
- DO(n²)
Explanation
Selection sort makes exactly one swap per pass — it finds the minimum of the remaining unsorted portion and swaps it into place — across n−1 passes over an n-element array, so it performs at most n−1 swaps total: a tightest upper bound of O(n). This is much smaller than its O(n²) COMPARISON count; swaps and comparisons have different complexities in selection sort specifically.
Source: GATE CS 2013 (2013)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.