+16 votes
1.5k views

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}$)
asked
edited | 1.5k views
0
this question is asked 3 times in gate 2006 , 2009 , and  2013

## 1 Answer

+23 votes
Best answer
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)$
answered by Boss (14.4k points)
edited by
+23
(n-1) swaps to be precise
+1
I should have written it with big oh notation
0
okay :)
+1
Word swap is important!
0

But the time complexity of Selection Sort is O(n2).. There are two loops, one inside the other

0
The question asks only for the number of swaps.
0

Ok. Thanks Sir... The book from where I read has given wrong algorithm, saying it to be Selection Sort.. As per that algorithm, number of swaps are also O(n2).

+11
Then you should never open that book again
0
ha ha ha :-D
Answer:

+47 votes
5 answers
1
+12 votes
1 answer
2
+21 votes
1 answer
3
+11 votes
2 answers
4
+13 votes
2 answers
5
+12 votes
6 answers
6
+25 votes
5 answers
7