edited by
9,944 views
37 votes
37 votes

Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort?

  1. $O(\log n$)
  2. $O(n$)
  3. $O(n \log n$)
  4. $O(n^{2}$)
edited by

2 Answers

Best answer
40 votes
40 votes
In selection max you can do is $n$ swaps..selecting the smallest element from all the elements and replacing it correct position so $O(n)$

Correct Answer: $B$
edited by
4 votes
4 votes
Best, Average and worst case will take maximum O(n) swaps.
Selection sort time complexity O(n2) in terms of number of comparisons. Each of these scans requires one swap for n-1 elements (the final element is already in place).
Answer:

Related questions

113 votes
113 votes
8 answers
1
Arjun asked Sep 24, 2014
27,872 views
The number of elements that can be sorted in $\Theta(\log n)$ time using heap sort is$\Theta(1)$$\Theta(\sqrt{\log} n)$$\Theta(\frac{\log n}{\log \log n})$$\Theta(\log n)...
17 votes
17 votes
3 answers
2
21 votes
21 votes
2 answers
3
17 votes
17 votes
5 answers
4
Arjun asked Sep 24, 2014
5,600 views
What will be the maximum sum of $44, 42, 40, \dots$ ?$502$$504$$506$$500$